EN中文

PROGRESS IN GEOGRAPHY >

2011 , Vol. 30 >Issue 5: 522 - 534

DOI: https://doi.org/10.11820/dlkxjz.2011.05.002

Original Articles

Review of the Research Progresses in Trajectory Clustering Methods

Expand
  • 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;
    2. Yantai Institute of Coastal Zone Research, CAS, Yantai 264003, Shandong,China;
    3. Graduate University of Chinese Academy of Sciences, Beijing 100049, China;
    4. Department of Geography and Resource Management, The Chinese University of Hong Kong, Hong Kong, China

Received date: 2010-10-01

  Revised date: 2011-02-01

  Online published: 2011-05-25

Fold

Abstract

A trajectory is a sequence of the location and timestamp of a moving object. It is not only an important type of spatio-temporal data, but also a critical source of information. Extracting patterns from different trajectory data can help people understand the drives and outcomes of individual and collective spatial dynamics, such as human behavior patterns, transport and logistics, emergency evacuation management, animal behavior, and marketing. Recently, a larger number of trajectory data are available for analyzing the temporal and spatial pattern, as the result of the improvements of tracking facilities and sensor networks. Therefore, clustering analysis needs to be used to find the implicit patterns in it. Based on the characteristics and the similarity measurements of trajectory data, this paper reviewed the research progresses in trajectory clustering methods. Firstly, the significance of research on trajectory data and its clustering methods was presented. Then the definition, models as well as several visualization methods of trajectories were summarized. After that, the authors classified the existing trajectory clustering methods into 6 main categories according to the similarity measurement of them, and analyzed each of the trajectory clustering methods, along with their respective pros and cons by category. Finally, some research challenges and future directions were discussed.

Key words： clustering; research progress; similarity measurement; spatio-temporal data mining; trajectory

Cite this article

GONG Xi, PEI Tao, SUN Jia, LUO Ming . Review of the Research Progresses in Trajectory Clustering Methods[J]. PROGRESS IN GEOGRAPHY, 2011 , 30(5) : 522 -534 . DOI: 10.11820/dlkxjz.2011.05.002

References

[1] 王家耀, 魏海平, 成毅, 等. 时空GIS的研究与进展. 海洋测绘, 2004, 24(5): 1-4.

[2] Han J, Kamber M, Tung A K H. Spatial clustering methodsin data mining//Miller H J, Han J. Geographic DataMining and Knowledge Discovery. London: Taylor &Francis, 2001: 188 - 217.

[3] Han J, Kamber M. Data Mining: Concepts and Techniques.2th ed. San Francisco: Morgan Kaufmann, 2006:383.

[4] Li X, Han J, Kim S, et al. Roam: Rule- and motif-basedanomaly detection in massive moving object data sets//Proceedings of the Seventh SIAM International Conferenceon Data Mining. Philadelphia: SIAM, 2007.

[5] Nanni M. Clustering methods for spatio-temporal data. Pisa,Italy: University of Pisa[D], 2002.

[6] Theodoridis Y, Silva J R O, Nascimento MA. On the generationof spatiotemporal datasets. Advances in SpatialDatabases, 1999, 1651/1999: 147-164.

[7] Giannotti F, Mazzoni A, Puntoni S, et al. Synthetic generationof cellular network positioning data//Proceedings ofthe 13th annual ACM International Workshop on GeographicInformation Systems. New York, NY, USA:ACM, 2005: 12-20.

[8] Tzouramanis T, Vassilakopoulos M, Manolopoulos Y. Onthe generation of time-evolving regional data. Geoinformatica,2002, 6(3): 207-231.

[9] Saglio J M, Moreira J. Oporto: A realistic scenario generatorfor moving objects. Geoinformatica, 2001, 5(1):71-93.

[10] Saltenis S, Jensen C S, Leutenegger S T, et al. Indexingthe positions of continuously moving objects. Sigmod Record,2000, 29(2): 331-342.

[11] Tao Y, Papadias D. Time-parameterized queries in spatio-temporal databases//Proceedings of the 2002 ACMSIGMOD International Conference on Management ofdata. New York, NY, USA: ACM, 2002: 334-345.

[12] Li Y, Han J, Yang J. Clustering moving objects//Proceedingsof the tenth ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining. NewYork, NY, USA: ACM, 2004: 617-622.

[13] Hägerstrand T. What about people in regional science?Papers in Regional Science, 1970, 24(1): 6-21.

[14] Lenntorp B. Paths in space-time environments: Atime-geographic study of movement possibilities of individuals.Environment and Planning A, 1977, 9: 961-972.

[15] Miller H J. Modelling accessibility using space-timeprism concepts within geographical information systems.International Journal of Geographical Information Systems,1991, 5(3): 287-301.

[16] Kwan M, Hong X. Network-based constraints-orientedchoice set formation using GIS. Geographical Systems,1998, 5: 139-162.

[17] Yu H, Shaw S L. Exploring potential human activities inphysical and virtual spaces: A spatio-temporal GIS approach.International Journal of Geographical InformationScience, 2008, 22(4): 409-430.

[18] Shaw S L, Yu H B. A GIS-based time-geographic approachof studying individual activities and interactionsin a hybrid physical-virtual space. Journal of TransportGeography, 2009, 17(2): 141-149.

[19] Berezansky M, Greenspan H, Cohen-Or D, et al. Segmentationand tracking of human sperm cells using spa-tio-temporal representation and clustering. Medical Imaging2007: Image Processing, 2007, 6512: 65122M.1-65122M.12.

[20] Erez K, Goldberger J, Sosnik R, et al. Analyzing movementtrajectories using a markov bi-clustering method.Journal of Computational Neuroscience, 2009, 27(3):543-552.

[21] Gabarro-Arpa J, Revilla R. Clustering of a molecular dynamicstrajectory with a hamming distance. Computersand Chemistry, 2000, 24(6): 693-698.

[22] Cape J N, Methven J, Hudson L E. The use of trajectorycluster analysis to interpret trace gas measurements atMace Head, Ireland. Atmospheric Environment, 2000, 34(22): 3651-3663.

[23] Camargo S J, Robertson A W, Gaffney S J, et al. ClusterAanalysis of typhoon tracks. Part I: General properties.Journal of Climate, 2007, 20(14): 3635-3653.

[24] Camargo S J, Robertson A W, Gaffney S J, et al. Clusteranalysis of typhoon tracks. Part II: Large-scale circulationand Enso. Journal of Climate, 2007, 20(14):3654-3676.

[25] Kang C H, Hwang J R, Li K J. Trajectory analysis for soccerplayers//Proceedings of the Sixth IEEE InternationalConference on Data Mining Workshops. Washington,DC, USA: IEEE Computer Society, 2006: 377-381.

[26] Laube P, Imfeld S, Weibel R. Discovering relative motionpatterns in groups of moving point objects. InternationalJournal of Geographical Information Science, 2005, 19(6): 639-668.

[27] 蔡元龙. 模式识别. 西安: 西北电讯工程学院出版社,1986: 18.

[28] Tan P N, Steinbach M, Kumar V. Introduction to DataMining. Boston: Pearson Addison-Wesley, 2006: 60-65.

[29] Agrawal R, Faloutsos C, Swami A. Efficient similaritysearch in sequence databases. Foundations of Data Organizationand Algorithms, 1993, 730: 69-84.

[30] Chen L, Özsu M, Oria V. Robust and fast similaritysearch for moving object trajectories//Proceedings of the2005 ACM SIGMOD International Conference on Managementof Data. New York, NY, USA: ACM, 2005:491-502.

[31] Lee S, Chun S, Kim D, et al. Similarity search for multidimensionaldata sequences//Proceedings of the 16th InternationalConference on Data Engineering. Washington D.C. USA: IEEE Computer Society, 2000: 599-608.

[32] Elnekave S, Last M, Maitnon O. Incremental clusteringof mobile objects//Proceedings of the 2007 IEEE 23rd InternationalConference on Data Engineering Workshop.Washington, DC, USA: IEEE Computer Society, 2007:585-592.

[33] Sankoff D, Kruskal J. Time Warps, String Edits, and Macromolecules:The Theory and Practice of Sequence Comparison.MA, USA: Addison-Wesley, 1983.

[34] Agrawal R, Lin K I, Sawhney H S, et al. Fast similaritySsearch in the presence of noise, scaling, and translationin time-series databases//Proceedings of the 21th InternationalConference on Very Large Data Bases. San Francisco,CA, USA: Morgan Kaufmann Publishers Inc., 1995:490-501.

[35] Crochemore M, Rytter W. Text Algorithms. New York,NY, USA: Oxford University Press, 1994.

[36] Lee J G, Han J, Whang K Y. Trajectory clustering: A partition-and-group framework//Proceedings of the 2007ACM SIGMOD International Conference on Managementof Data. New York, NY, USA: ACM, 2007:593-604.

[37] Nanni M, Pedreschi D. Time-focused clustering of trajectoriesof moving objects. Journal of Intelligent InformationSystems, 2006, 27(3): 267-289.

[38] Kalnis P, Mamoulis N, Bakiras S. On discovering movingclusters in spatio-temporal data//Medeiros C B,EgenhoferM, Bertino E. Proceedings of the 9th InternationalSymposium on Advances in Spatial and Temporal Databases.Berlin: Springer-Verlag, 2005: 364-381.

[39] Gao Y, Zheng B, Chen G, et al. Algorithms for constrainedK-nearest neighbor queries over moving objecttrajectories. Geoinformatica, 2010, 14(2): 241-276.

[40] Alt H, Godau M. Computing the fréchet distance betweentwo polygonal curves. International Journal of ComputationalGeometry and Applications, 1995, 5(1): 75-91.

[41] Lin B, Su J. One way distance: For shape based similaritysearch of moving object trajectories. Geoinformatica,2008, 12(2): 117-142.

[42] Perng C S, Wang H, Zhang S R, et al. Landmarks: A newmodel for similarity-based pattern querying in time seriesdatabases//Proceedings of the 16th International Conferenceon Data Engineering, 2000: 33-42.

[43] Faloutsos C, Jagadish H, Mendelzon A, et al. A signaturetechnique for similarity-based queries//Proceedings ofthe Compression and Complexity of Sequences 1997.Washington, DC, USA: IEEE Computer Society, 1997:2-20.

[44] Pelekis N, Kopanakis l, Ntoutsi I, et al. Mining trajectorydatabases via a suite of distance operators//Proceedingsof the 2007 IEEE 23rd International Conference on DataEngineering Workshop. Washington, DC, USA: IEEEComputer Society, 2007: 575-584.

[45] Faloutsos C, Ranganathan M, Manolopoulos Y. Fast sub-sequence matching in time-series databases. ACM SIGMODRecord, 1994, 23(2): 419-429.

[46] Chan K. Efficient time series matching by wavelets//Proceedingsof the 15th International Conference on DataEngineering. Washington, DC, USA: IEEE Computer Society,1999: 126-133.

[47] Chakrabarti K, Keogh E, Mehrotra S, et al. Locally adaptivedimensionality reduction for indexing large time seriesdatabases. ACM Transactions on Database Systems(TODS), 2002, 27(2): 188-228.

[48] Yanagisawa Y, Akahani J, Satoh T. Shape-based similarityquery for trajectory of mobile objects//Proceedings ofthe 4th International Conference on Mobile Data Management.London, UK: Springer-Verlag, 2003: 63-77.

[49] Keogh E, Palpanas T, Zordan V, et al. Indexing large human-motion databases//Proceedings of the Thirtieth InternationalConference on Very Large Data Bases. VLDBEndowment, 2004: 780-791.

[50] Berndt D, Clifford J. Using dynamic time warping to findpatterns in time series//Proceedings of KDD-94 Work-Shop, 1994: 359-370.

[51] Sakurai Y, Yoshikawa M, Faloutsos C. FTW: Fast similaritysearch under the time warping distance//Proceedingsof the Twenty-fourth ACM SIGMOD-SIGACT-SIGARTSymposium on Principles of Database Systems. NewYork, NY, USA: ACM, 2005: 326-337.

[52] Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexingmulti-dimensional time-series with support formultiple distance measures//Proceedings of the NinthACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining. New York, NY, USA: ACM,2003: 216-225.

[53] Little J, Gu Z. Video retrieval by spatial and temporalstructure of trajectories//Proceedings of SPIE, the InternationalSociety for Optical Engineering SPIE, 2001:545-552.

[54] Vlachos M, Gunopulos D, Das G. Rotation invariant distancemeasures for trajectories//Proceedings of the TenthACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining. New York, NY, USA: ACM,2004: 707-712.

[55] Vlachos M, Kollios G, Gunopulos D. Discovering similarmultidimensional trajectories//Agrawal R, Dittrich K,Ngu A H H. Proceedings of the 18th International Conferenceon Data Engineering. Washington, DC, USA: IEEEComputer Society, 2002: 673-684.

[56] Bozkaya T, Yazdani N, Özsoyoglu M. Matching and indexingsequences of different lengths//Proceedings of theSixth International Conference on Information andKnowledge Management. New York, NY, USA: ACM,1997: 128-135.

[57] Chen L, Ng R. On the marriage of lp-norms and edit distance//Proceedings of the Thirtieth International Conferenceon Very Large Data Bases. VLDB Endowment,2004: 792-803.

[58] Liu J P, Zhang Y L, Liu G. Partition and density-basedclustering for moving objects Trajectories//Proceedingsof the Third International Conference on Computer Science& Education. Xiamen: Xiamen University Press,2008: 182-187.

[59] Lee J G, Han J, Li X, et al. Traclass: Trajectory classificationusing hierarchical region-based and trajectory-Basedclustering//Proceedings of International Conference onVery Large Data Base(VLDB'08). VLDB Endowment,2008: 1081-1094.

[60] Ankerst M, Breunig M M, Kriegel H P, et al. Optics: Orderingpoints to identify the clustering structure//Proceedingsof the 1999 ACM SIGMOD International Conferenceon Management of Data. New York, NY, USA:ACM, 1999: 49-60.

[61] Zhang T, Ramakrishnan R, Livny M. Birch: An efficientdata clustering method for very large databases. ACMSIGMOD Record, 1996, 25(2): 103-114.

[62] Nanni M, Kuijpers B, Körner C, et al. Spatiotemporal datamining//Giannotti F,Pedreschi D. Mobility, Data Mining,and Privacy: Geographic Knoweledge Discovery.Berlin: Springer-Verlag, 2008: 267-296.

[63] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matchingvehicle tracking data//Proceedings of the 31st InternationalConference on Very Large Data Bases. VLDB Endowment,2005: 853-864.

[64] Schreck T, Bernard J, Tekusova T, et al. Visual clusteranalysis of trajectory data with interactive kohonen maps.Information Visualization, 2009, 8: 14-29.

[65] Yu W, Gertz M. Constraint-based learning of distancefunctions for object trajectories//Proceedings of the 21stInternational Conference on Scientific and Statistical DatabaseManagement. Berlin, Heidelberg: Springer-Verlag,2009: 627-645.

[66] Gaffney S, Smyth P. Trajectory clustering with mixturesof regression models//Proceedings of the Fifth ACM SIGKDDInternational Conference on Knowledge Discoveryand Data Mining. New York, NY, USA: ACM, 1999:63-72.

[67] Chudova D, Gaffney S, Mjolsness E, et al. Translation-invariantmixture models for curve clustering//Proceedingsof the Ninth ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. New York, NY,USA: ACM, 2003: 79-88.

[68] Alon J, Sclaroff S, Kollios G, et al. Discovering clustersin motion time-series data//Proceedings of IEEE ComputerSociety Conference on Computer Vision and PatternRecognition (CVPR'03). Washington, DC, USA: IEEEComputer Society, 2003: 375-381.

[69] Ketterlin A. Clustering sequences of complex objects//Proceeding of the 3rd Interernational Conference onKnowledge Discovery and Data Mining (KDD-97).AAAI Press, 1997: 215-218.

[70] Agrawal R, Psaila G, Wimmers E L, et al. Queryingshapes of histories//Proceedings of the 21th InternationalConference on Very Large Data Bases. San Francisco,CA, USA: Morgan Kaufmann Publishers Inc., 1995:502-514.

[71] Kim S W, Yoon J, Park S, et al. Shape-based retrieval ofsimilar subsequences in time-series databases//Proceedingsof the 2002 ACM Symposium on Applied Computing.New York, NY, USA: ACM, 2002: 438-445.
Options
Outlines

/

〈 〉