Abstract
Driven by the advance of positioning technology and the popularity of location-sharing services, semantic-enriched trajectory data have become unprecedentedly available. The sequential patterns hidden in such data, when properly defined and extracted, can greatly benefit tasks like targeted advertising and urban planning. Unfortunately, classic sequential pattern mining algorithms developed for transactional data cannot effectively mine patterns in semantic trajectories, mainly because the places in the continuous space cannot be regarded as independent "items". Instead, similar places need to be grouped to collaboratively form frequent sequential patterns. That said, it remains a challenging task to mine what we call fine-grained sequential patterns, which must satisfy spatial compactness, semantic consistency and temporal continuity simultaneously. We propose Splitter to effectively mine such fine-grained sequential patterns in two steps. In the first step, it retrieves a set of spatially coarse patterns, each attached with a set of trajectory snippets that precisely record the pattern's occurrences in the database. In the second step, Splitter breaks each coarse pattern into fine-grained ones in a top-down manner, by progressively detecting dense and compact clusters in a higher-dimensional space spanned by the snippets. Splitter uses an effective algorithm called weighted snippet shift to detect such clusters, and leverages a divide-and-conquer strategy to speed up the top-down pattern splitting process. Our experiments on both real and synthetic data sets demonstrate the effectiveness and efficiency of Splitter.
- R. Agrawal and R. Srikant. Mining sequential patterns. In ICDE, pages 3--14, 1995. Google ScholarDigital Library
- L. O. Alvares, V. Bogorny, B. Kuijpers, B. Moelans, J. A. Fern, E. D. Macedo, and A. T. Palma. Towards semantic trajectory knowledge discovery. Data Mining and Knowledge Discovery, 2007.Google Scholar
- D. Comaniciu and P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell., 24(5):603--619, 2002. Google ScholarDigital Library
- B. Georgescu, I. Shimshoni, and P. Meer. Mean shift based clustering in high dimensions: A texture classification example. In ICCV, pages 456--463, 2003. Google ScholarDigital Library
- F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In KDD, pages 330--339, 2007. Google ScholarDigital Library
- H. Jeung, M. L. 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
- P. Laube and S. Imfeld. Analyzing relative motion within groups of trackable moving point objects. In GIScience, pages 132--144, 2002. Google ScholarDigital Library
- Z. Li, B. Ding, J. Han, and R. Kays. Swarm: Mining relaxed temporal moving object clusters. PVLDB, 3(1):723--734, 2010. Google ScholarDigital Library
- W. Luo, H. Tan, L. Chen, and L. M. Ni. Finding time period-based most frequent path in big trajectory data. In SIGMOD, pages 713--724, 2013. Google ScholarDigital Library
- J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Prefixspan: Mining sequential patterns by prefix-projected growth. In ICDE, pages 215--224, 2001. Google ScholarDigital Library
- I. Tsoukatos and D. Gunopulos. Efficient mining of spatiotemporal patterns. In SSTD, pages 425--442, 2001. Google ScholarDigital Library
- J. Wang, W. Hsu, M.-L. Lee, and J. T.-L. Wang. Flowminer: Finding flow patterns in spatio-temporal databases. In ICTAI, 2004. Google ScholarDigital Library
- Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. Semitri: a framework for semantic annotation of heterogeneous trajectories. In EDBT, pages 259--270, 2011. Google ScholarDigital Library
- G. Yang. The complexity of mining maximal frequent itemsets and maximal frequent patterns. In KDD, pages 344--353, 2004. Google ScholarDigital Library
- J. J.-C. Ying, W.-C. Lee, T.-C. Weng, and V. S. Tseng. Semantic trajectory mining for location prediction. In GIS, pages 34--43, 2011. Google ScholarDigital Library
- M. J. Zaki. Spade: An efficient algorithm for mining frequent sequences. Machine Learning, 42(1/2):31--60, 2001. Google ScholarDigital Library
- K. Zheng, Y. Zheng, N. J. Yuan, and S. Shang. On discovery of gathering patterns from trajectories. In ICDE, pages 242--253, 2013. Google ScholarDigital Library
- Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from gps trajectories. In WWW, pages 791--800, 2009. Google ScholarDigital Library
Index Terms
- Splitter: mining fine-grained sequential patterns in semantic trajectories
Recommendations
Splitter Placement Problem on Directed Fiber Trees
PDCAT '05: Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and TechnologiesWavelength division multiplexing technique can greatly increase the bandwidth of all-optical networks without the reconstruction of physical infrastructure. Optical power splitters can reduce the number of required wavelengths for multicast requests by ...
Improving Performance of Handwork-Fused 1x3 Polymer Optical Fiber Splitter through Progressed Fusion Technique
ICCTD '09: Proceedings of the 2009 International Conference on Computer Technology and Development - Volume 01As demands for Plastic Optical Fiber (POF) rise up in optical data communication system, POF are now being applied as base material for passive optical splitter. In order to produce the economical passive device, optical 1x3 splitters have been ...
Fabrication of a polymeric photonic crystal wavelength splitter using ultra violet embossing technology
We present the design concept and the possibility of UV embossing technology for polymeric photonic crystal functional devices. Our design concept for polymeric photonic crystal devices is to utilize quasi self-collimating effect of photonic crystal, ...
Comments