ABSTRACT
In this paper, we study the problem of mining for frequent trajectories, which is crucial in many application scenarios, such as vehicle traffic management, hand-off in cellular networks, supply chain management. We approach this problem as that of mining for frequent sequential patterns. Our approach consists of a partitioning strategy for incoming streams of trajectories in order to reduce the trajectory size and represent trajectories as strings. We mine frequent trajectories using a sliding windows approach combined with a counting algorithm that allows us to promptly update the frequency of patterns. In order to make counting really efficient, we represent frequent trajectories by prime numbers, whereby the Chinese reminder theorem can then be used to expedite the computation.
- R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB, 1994. Google ScholarDigital Library
- Johannes Fischer, Volker Heun, and Stefan Kramer. Optimal string mining under frequency constraints. In PKDD, pages 139--150, 2006. Google ScholarDigital Library
- Fosca Giannotti, Mirco Nanni, Fabio Pinelli, and Dino Pedreschi. Trajectory pattern mining. In KDD, pages 330--339, 2007. Google ScholarDigital Library
- J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. In SIGMOD, 2000. Google ScholarDigital Library
- H. Jeung, M. Lung Yiu, X. Zhou, C. S. Jensen, and H. T. Shen. Discovery of convoys in trajectory databases. PVLDB, 1(1): 1068--1080, 2008. Google ScholarDigital Library
- I. T. Jolliffe. Principal Component Analysis. Springer Series in Statistics, 2002.Google Scholar
- A. Kügel and E. Ohlebusch. A space efficient solution to the frequent string mining problem for many databases. Data Min. Knowl. Discov., 17(1): 24--38, 2008. Google ScholarDigital Library
- C.-H. Lee and C.-W. Chung. Efficient storage scheme and query processing for supply chain management using rfid. In SIGMOD08, pages 291--302, 2008. Google ScholarDigital Library
- J.-G. Lee, J. Han, X. Li, and H. Gonzalez. TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering. PVLDB, 1(1): 1081--1094, 2008. Google ScholarDigital Library
- J.-G. Lee, J. Han, and K-Y Whang. Trajectory clustering: a partition-and-group framework. In SIGMOD07, pages 593--604, 2007. Google ScholarDigital Library
- J. Li, D. Maier, K. Tufte, V. Papadimos, and P. A. Tucker. No pane, no gain: efficient evaluation of sliding-window aggregates over data streams. SIGMOD Rec., 34(1): 39--44, 2005. Google ScholarDigital Library
- Y. Liu, L. Chen., J. Pei, Q. Chen, and Y. Zhao. Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays. In PerCom, pages 37--46, 2007. Google ScholarDigital Library
- E. Masciari. Trajectory clustering via effective partitioning. In FQAS, pages 358--370, 2009. Google ScholarDigital Library
- Elio Masciari. Warehousing and querying trajectory data streams with error estimation. In DOLAP, pages 113--120, 2012. Google ScholarDigital Library
- B. Mozafari, H. Thakkar, and C. Zaniolo. Verifying and mining frequent patterns from large windows over data streams. In ICDE, pages 179--188, 2008. Google ScholarDigital Library
- Y. Zheng, Q. Li, Y. Chen, and X. Xie. Understanding mobility based on gps data. In UbiComp 2008, pages 312--321, 2008. Google ScholarDigital Library
- Sequential pattern mining from trajectory data
Recommendations
Trajectory Data Mining: An Overview
Survey Paper, Regular Papers and Special Section on Participatory Sensing and Crowd IntelligenceThe advances in location-acquisition and mobile computing techniques have generated massive spatial trajectory data, which represent the mobility of a diversity of moving objects, such as people, vehicles, and animals. Many techniques have been proposed ...
Mining Disjoint Sequential Pattern Pairs from Tourist Trajectory Data
Discovery ScienceAbstractRoute mining from trajectory databases, or trajectory data mining, has become an important and valuable task since the popularization of GPS devices. Sequential pattern mining based approaches are well applied to trajectory data mining, while they ...
From sequential pattern mining to structured pattern mining: A pattern-growth approach
AbstractSequential pattern mining is an important data mining problem with broad applications. However, it is also a challenging problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. ...
Comments