nach oben

The VLDB Journal

Erschienen in:

01.02.2015 | Regular Paper

Calibrating trajectory data for spatio-temporal similarity analysis

verfasst von: Han Su, Kai Zheng, Jiamin Huang, Haozhou Wang, Xiaofang Zhou

Erschienen in: The VLDB Journal | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Due to the prevalence of GPS-enabled devices and wireless communications technologies, spatial trajectories that describe the movement history of moving objects are being generated and accumulated at an unprecedented pace. Trajectory data in a database are intrinsically heterogeneous, as they represent discrete approximations of original continuous paths derived using different sampling strategies and different sampling rates. Such heterogeneity can have a negative impact on the effectiveness of trajectory similarity measures, which are the basis of many crucial trajectory processing tasks. In this paper, we pioneer a systematic approach to trajectory calibration that is a process to transform a heterogeneous trajectory dataset to one with (almost) unified sampling strategies. Specifically, we propose an anchor-based calibration system that aligns trajectories to a set of anchor points, which are fixed locations independent of trajectory data. After examining four different types of anchor points for the purpose of building a stable reference system, we propose a spatial-only geometry-based calibration approach that considers the spatial relationship between anchor points and trajectories. Then a more advanced spatial-only model-based calibration method is presented, which exploits the power of machine learning techniques to train inference models from historical trajectory data to improve calibration effectiveness. Afterward, since trajectory has temporal information, we extend these two spatial-only trajectory calibration algorithms to incorporate the temporal information, which can infer a proper time stamp to each anchor point of a calibrated trajectory. At last, we provide a solution to reduce cost, i.e., the number of trajectories that is necessary to be re-calibrated, of the updating of the reference system. Finally, we conduct extensive experiments using real trajectory datasets to demonstrate the effectiveness and efficiency of the proposed calibration system.

Vorheriger Artikel RDF in the clouds: a survey

Nächster Artikel Conformity-aware influence maximization in online social networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Achtert, E., Böhm, C., Kröger, P., Kunath, P., Pryakhin, A., Renz, M.: Efficient reverse k-nearest neighbor search in arbitrary metric spaces. In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, pp. 515–526. ACM (2006)

Alvares, L.O., Bogorny, V., Kuijpers, B., de Macedo, J.A.F., Moelans, B., Vaisman, A.: A model for enriching trajectories with semantic geographical information. In: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, pp 22. ACM (2007)

Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of the 31st International Conference on Very Large Data Bases, pp. 853–864. VLDB Endowment (2005)

Cai, Y., Ng, R.: Indexing spatio-temporal trajectories with chebyshev polynomials. In: SIGMOD, pp. 599–610 (2004)

Cao, L., Krumm, J.: From gps traces to a routable road map. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 3–12. ACM (2009)

Chakka, V., Everspaugh, A., Patel, J.: Indexing large trajectory data sets with seti. In: CIDR (2003)

Charniak, E.: Statistical Language Learning. MIT Press, Cambridge (1996)

Chen, L., Ng, R.: On the marriage of lp-norms and edit distance. In: PVLDB, pp. 792–803 (2004)

Chen, L., Özsu, M., Oria, V.: Robust and fast similarity search for moving object trajectories. In: SIGMOD, pp. 491–502 (2005)

10.

Chen, Z., Shen, H., Zhou, X.: Discovering popular routes from trajectories. In: ICDE, pp. 900–911 (2011)

11.

Cheng, R., Kalashnikov, D., Prabhakar, S.: Querying imprecise data in moving object environments. TKDE 16(9), 1112–1127 (2004)

12.

Cudre-Mauroux, P., Wu, E., Madden, S.: Trajstore: An adaptive storage system for very large trajectory data sets. In: ICDE, pp. 109–120 (2010)

13.

Dauria, M., Nanni, M., Pedreschi, D.: Time-focused density-based clustering of trajectories of moving objects. In: Proceedings of the Workshop on Mining Spatio-temporal Data (MSTD-2005), Porto (2005)

14.

Edelkamp, S., Schrödl, S.: Route planning and map inference with global positioning traces. In: Computer Science in Perspective, pp. 128–151. Springer, Berlin (2003)

15.

Ester, M., Kriegel, H., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: KDD, pp. 226–231 (1996)

16.

Frentzos, E., Gratsias, K., Pelekis, N., Theodoridis, Y.: Nearest neighbor search on moving object trajectories. In: SSTD, pp. 328–345 (2005)

17.

Furletti, B., Cintia, P., Renso, C., Spinsanti, L.: Inferring human activities from gps tracks. In: Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing, p. 5. ACM (2013)

18.

Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory pattern mining. In: KDD, pp. 330–339 (2007)

19.

Gonzalez, H., Han, J., Li, X., Myslinska, M., Sondag, J.: Adaptive fastest path computation on a road network: a traffic mining approach. In: PVLDB, pp. 794–805 (2007)

20.

Greenfeld, J.S.: Matching gps observations to locations on a digital map. In: National Research Council (US). Transportation Research Board. Meeting (81st, 2002: Washington, DC). Preprint CD-ROM (2002)

21.

Güting, R., Schneider, M.: Realm-based spatial data types: the rose algebra. VLDB J. 4(2), 243–286 (1995)CrossRef

22.

Haklay, M., Weber, P.: Openstreetmap: User-generated street maps. IEEE Pervas. Comput. 7(4), 12–18 (2008)CrossRef

23.

Heipke, C.: Crowdsourcing geospatial data. ISPRS J. Photogramm. Remote Sens. 65(6), 550–557 (2010)CrossRef

24.

Jeung, H., Shen, H., Zhou, X.: Convoy queries in spatio-temporal databases. In: ICDE, pp. 1457–1459 (2008)

25.

Jeung, H., Yiu, M., Zhou, X., Jensen, C., Shen, H.: Discovery of convoys in trajectory databases. In: PVLDB, vol. 1, pp. 1068–1080. VLDB Endowment (2008)

26.

Kearney, J., Hansen, S.: Stream editing for animation. Technical Report, DTIC Document (1990)

27.

Kruskal, J.: An overview of sequence comparison: time warps, string edits, and macromolecules. SIAM Rev. 25, 201–237 (1983)

28.

Lee, J., Han, J., Whang, K.: Trajectory clustering: a partition-and-group framework. In: SIGMOD, p. 604 (2007)

29.

Li, X., Han, J., Lee, J., Gonzalez, H.: Traffic density-based discovery of hot routes in road networks. Adv. Spat. Tempor. Database 441–459 (2007)

30.

Li, Z., Ding, B., Han, J., Kays, R.: Swarm: Mining relaxed temporal moving object clusters. In: PVLDB volume 3, pages 723–734 (2010)

31.

Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., Huang, Y.: Map-matching for low-sampling-rate gps trajectories. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 352–361. ACM, (2009)

32.

Mamoulis, N., Cao, H., Kollios, G., Hadjieleftheriou, M., Tao, Y., Cheung, D.: Mining, indexing, and querying historical spatiotemporal data. In: KDD, pp. 236–245 (2004)

33.

Moore, A.: An introductory tutorial on kd trees. Efficient memory-based learning for robot control. PhD Thesis, Carnegie Mellon University, (1991)

34.

Ni, J., Ravishankar, C.: Indexing spatio-temporal trajectories with efficient polynomial approximations. TKDE 19(5), 663–678 (2007)

35.

OpenStreetMap. http://www.openstreetmap.org/

36.

Pfoser, D., Jensen, C.: Capturing the uncertainty of moving-object representations. In: Advances in Spatial Databases, pp. 111–131. Springer (1999)

37.

Pfoser, D., Jensen, C., Theodoridis, Y.: Novel approaches to the indexing of moving object trajectories. In: VLDB, pp. 395–406 (2000)

38.

Potamias, M., Patroumpas, K., Sellis, T.: Sampling trajectory streams with spatiotemporal criteria. In: 18th International Conference on Scientific and Statistical Database Management, 2006, pp. 275–284. IEEE (2006)

39.

Sacharidis, D., Patroumpas, K., Terrovitis, M., Kantere, V., Potamias, M., Mouratidis, K., Sellis, T.: On-line discovery of hot motion paths. In: EDBT, pp. 392–403 (2008)

40.

Schroedl, S., Wagstaff, K., Rogers, S., Langley, P., Wilson, C.: Mining gps traces for map refinement. Data Min Knowl Discov 9(1), 59–87 (2004)CrossRefMathSciNet

41.

Spaccapietra, S., Parent, C., Damiani, M.L., de Macedo, J.A., Porto, F., Vangenot, C.: A conceptual view on trajectories. Data Knowl Eng 65(1), 126–146 (2008)CrossRef

42.

Su, H., Zheng, K., Wang, H., Huang, J., Zhou, X.: Calibrating trajectory data for similarity-based analysis. In: Proceedings of the 2013 International Conference on Management of Data, pp. 833–844. ACM (2013)

43.

Syed, S., Cannon, M.: Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons. In: Proceedings of the Institute of Navigation (ION) National Technical Meeting, USA (2004)

44.

Trajcevski, G., Tamassia, R., Ding, H., Scheuermann, P., Cruz, I.: Continuous probabilistic nearest-neighbor queries for uncertain trajectories. In: EDBT, pp. 874–885 (2009)

45.

Trajcevski, G., Wolfson, O., Hinrichs, K., Chamberlain, S.: Managing uncertainty in moving objects databases. ACM Trans. Database Syst. (TODS) 29(3), 463–507 (2004)CrossRef

46.

Vlachos, M., Kollios, G., Gunopulos, D.: Discovering similar multidimensional trajectories. In: Proceedings of 18th International Conference on Data Engineering, 2002, pp. 673–684. IEEE (2002)

47.

Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: localizing global curve-matching algorithms. In: 18th International Conference on Scientific and Statistical Database Management, 2006, pp. 379–388. IEEE (2006)

48.

White, C.E., Bernstein, D., Kornhauser, A.L.: Some map matching algorithms for personal navigation assistants. Transp. Res. Part C Emerg. Technol. 8(1), 91–108 (2000)CrossRef

49.

Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th symposium on Theory of Computing, pp. 887–898. ACM (2012)

50.

Wolfson, O., Chamberlain, S., Dao, S., Jiang, L., Mendez, G.: Cost and imprecision in modeling the position of moving objects. In: ICDE, pp. 588–596. IEEE (1998)

51.

Wolfson, O., Sistla, A., Chamberlain, S., Yesha, Y.: Updating and querying databases that track mobile units. Distrib. Parallel databases 7(3), 257–387 (1999)CrossRef

52.

Zhang, M., Chen, S., Jensen, C. S., Ooi, B. C., Zhang, Z.: Effectively indexing uncertain moving objects for predictive queries. In: PVLDB, pp. 261–272 (2009)

53.

Zheng, K., Trajcevski, G., Zhou, X., Scheuermann, P.: Probabilistic range queries for uncertain trajectories on road networks. In: EDBT, pp. 283–294 (2011)

54.

Zheng, K., Zheng, Y., Xie, X., Zhou, X.: Reducing uncertainty of low-sampling-rate trajectories. In: 2012 IEEE 28th International Conference on Data Engineering (ICDE), pp. 1144–1155. IEEE (2012)

55.

Zheng, Y., Zhang, L., Xie, X., Ma, W.: Mining interesting locations and travel sequences from gps trajectories. In: WWW, pp. 791–800 (2009)

Titel: Calibrating trajectory data for spatio-temporal similarity analysis
verfasst von: Han Su
Kai Zheng
Jiamin Huang
Haozhou Wang
Xiaofang Zhou
Publikationsdatum: 01.02.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: The VLDB Journal / Ausgabe 1/2015
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI: https://doi.org/10.1007/s00778-014-0365-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2015

Continuous nearest-neighbor queries with location uncertainty

RDF in the clouds: a survey

A unified framework for approximate dictionary-based entity extraction

Scaling forecasting algorithms using clustered modeling

Conformity-aware influence maximization in online social networks

Compressive mining: fast and optimal data mining in the compressed domain

Premium Partner