Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Adaptive Access Path Selection for Hardware-Accelerated DRAM Loads Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Trajectory Set Similarity Measure: An EMD-Based Approach

Authors : Dan He, Boyu Ruan, Bolong Zheng, Xiaofang Zhou

Published in: Databases Theory and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

To address the trajectory sparsity issue concerning Origin-Destination (OD) pairs, in general, most existing studies strive to reconstruct trajectories by concatenating the sub-trajectories along the specific paths and filling up the sparsity with conceptual trajectories. However, none of them gives the robustness validation for their reconstructed trajectories. By intuition, the reconstructed trajectories are more qualified if they are more similar to the exact ones traversing directly from the origin to the destination, which indicates the effectiveness of the corresponding trajectory augmentation algorithms. Nevertheless, to our knowledge, no existing work has studied the similarity of trajectory sets. Motivated by this, we propose a novel similarity measure to evaluate the similarity between two set of trajectories, borrowing the idea of the Earth Mover’s Distance. Empirical studies on a large real trajectory dataset show that our proposed similarity measure is effective and robust.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Privacy Preservation for Trajectory Data Publishing by Look-Up Table Generalization
next chapter Histogram Construction for Difference Analysis of Spatio-Temporal Data on Array DBMS
Literature
1.
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pp. 491–502. ACM (2005)
2.
Chen, Z., Shen, H.T., Zhou, X.: Discovering popular routes from trajectories. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 900–911. IEEE (2011)
3.
Chen, Z., Shen, H.T., Zhou, X., Zheng, Y., Xie, X.: Searching trajectories by locations: an efficiency study. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 255–266. ACM (2010)
4.
Dai, J., Yang, B., Guo, C., Ding, Z.: Personalized route recommendation using big trajectory data. In: 2015 IEEE 31st International Conference on Data Engineering (ICDE), pp. 543–554. IEEE (2015)
5.
Kassidas, A., MacGregor, J.F., Taylor, P.A.: Synchronization of batch trajectories using dynamic time warping. AIChE J. 44(4), 864–875 (1998)CrossRef
6.
Kruskal, J.B.: An overview of sequence comparison: time warps, string edits, and macromolecules. SIAM Rev. 25(2), 201–237 (1983)MathSciNetCrossRef
7.
Kullback, S.: Information Theory and Statistics. Courier Corporation, North Chelmsford (1997)MATH
8.
Lin, B., Su, J.: Shapes based trajectory queries for moving objects. In: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems, pp. 21–30. ACM (2005)
9.
Newson, P., Krumm, J.: Hidden Markov map matching through noise and sparseness. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 336–343. ACM (2009)
10.
Pele, O., Werman, M.: Fast and robust earth mover’s distances. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 460–467. IEEE (2009)
11.
Pelekis, N., Kopanakis, I., Marketos, G., Ntoutsi, I., Andrienko, G., Theodoridis, Y.: Similarity search in trajectory databases. In: 14th International Symposium on Temporal Representation and Reasoning, pp. 129–140. IEEE (2007)
12.
Puzicha, J., Hofmann, T., Buhmann, J.M.: Non-parametric similarity measures for unsupervised texture segmentation and image retrieval. In: Proceedings of the 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 267–272. IEEE (1997)
13.
Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99–121 (2000)CrossRef
14.
Sanderson, A.C., Wong, A.K.: Pattern trajectory analysis of nonstationary multivariate data. IEEE Trans. Syst. Man Cybern. 10(7), 384–392 (1980)CrossRef
15.
Swain, M.J., Ballard, D.H.: Color indexing. Int. J. Comput. Vis. 7(1), 11–32 (1991)CrossRef
16.
Vlachos, M., Kollios, G., Gunopulos, D.: Discovering similar multidimensional trajectories. In: Proceedings of the 18th International Conference on Data Engineering, pp. 673–684. IEEE (2002)
17.
Xue, A.Y., Zhang, R., Zheng, Y., Xie, X., Huang, J., Xu, Z.: Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 254–265. IEEE (2013)
18.
Yi, B.-K., Jagadish, H., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: Proceedings of the 14th International Conference on Data Engineering, pp. 201–208. IEEE (1998)
Metadata
Title
Trajectory Set Similarity Measure: An EMD-Based Approach
Authors
Dan He
Boyu Ruan
Bolong Zheng
Xiaofang Zhou
Copyright Year
2018
Book
Databases Theory and Applications

Print ISBN: 978-3-319-92012-2

Electronic ISBN: 978-3-319-92013-9

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-92013-9_3

Premium Partner

    Image Credits