|
|
Online clustering of streaming trajectories |
Jiali MAO1,2(), Qiuge SONG1, Cheqing JIN1, Zhigang ZHANG1, Aoying ZHOU1 |
1. School of Data Science and Engineering, East China Normal University, Shanghai 200062, China 2. School of Computing, China West Normal University, Nanchong 637009, China |
|
|
Abstract With the increasing availability of modern mobile devices and location acquisition technologies, massive trajectory data of moving objects are collected continuously in a streaming manner. Clustering streaming trajectories facilitates finding the representative paths or common moving trends shared by different objects in real time. Although data stream clustering has been studied extensively in the past decade, little effort has been devoted to dealing with streaming trajectories. The main challenge lies in the strict space and time complexities of processing the continuously arriving trajectory data, combined with the difficulty of concept drift. To address this issue, we present two novel synopsis structures to extract the clustering characteristics of trajectories, and develop an incremental algorithm for the online clustering of streaming trajectories (called OCluST). It contains a micro-clustering component to cluster and summarize the most recent sets of trajectory line segments at each time instant, and a macro-clustering component to build large macro-clusters based on micro-clusters over a specified time horizon. Finally, we conduct extensive experiments on four real data sets to evaluate the effectiveness and efficiency of OCluST, and compare it with other congeneric algorithms. Experimental results show that OCluST can achieve superior peformance in clustering streaming trajectories.
|
Keywords
streaming trajectory
synopsis data structure
concept drift
sliding window
|
Corresponding Author(s):
Jiali MAO
|
Just Accepted Date: 29 September 2017
Online First Date: 20 December 2017
Issue Date: 23 March 2018
|
|
1 |
Pan B, Zheng Y, Wilkie D, Shahabi C. Crowd sensing of traffic anomalies based on human mobility and social media. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2013, 334–343
https://doi.org/10.1145/2525314.2525343
|
2 |
Liu H P, Jin C Q, Zhou A Y. Popular route planning with travel cost estimation. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2016, 403–418
https://doi.org/10.1007/978-3-319-32049-6_25
|
3 |
Chen C, Chen X, Wang Z, Wang Y S, Zhang D Q. ScenicPlanner: planning scenic travel routes leveraging heterogeneous user-generated digital footprints. Frontiers of Computer Science, 2017, 11(1): 61–74
https://doi.org/10.1007/s11704-016-5550-2
|
4 |
Duan X Y, Jin C Q, Wang X L, Zhou A Y, Yue K. Real-time personalized taxi-sharing. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2016, 451–465
https://doi.org/10.1007/978-3-319-32049-6_28
|
5 |
Wu H, Tu C C, Sun W W, Zheng B H, Su H, Wang W. GLUE: a parameter-tuning- free map updating system. In: Proceedings of the 24th ACM International Conference on Information and Knowledge Management. 2015, 683–692
https://doi.org/10.1145/2806416.2806425
|
6 |
Lee J G, Han J W, Whang K Y. Trajectory clustering: a partition-andgroup framework. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2007, 593–604
https://doi.org/10.1145/1247480.1247546
|
7 |
Ester M, Kriegel H P, Sander J, Xu XW. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. 1996, 226–231
|
8 |
Gaffney S, Smyth P. Trajectory clustering with mixtures of regression models. In: Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1999, 63–72
https://doi.org/10.1145/312129.312198
|
9 |
Wang W, Yang J, Muntz R R. STING: a statistical information grid approach to spatial data mining. In: Proceedings of the 23rd International Conference on Very Large Data Bases. 1997, 186–195
|
10 |
Jensen C S, Lin D, Ooi B C. Continuous clustering of moving objects. IEEE Transactions on Knowledge & Data Engineering, 2007, 19(9): 1161–1174
https://doi.org/10.1109/TKDE.2007.1054
|
11 |
Li Y F, Han J W, Yang J. Clustering moving objects. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2004, 617–622
https://doi.org/10.1145/1014052.1014129
|
12 |
Li Z H, Lee J G, Li X L, Han J W. Incremental clustering for trajectories. In: Proceedings of the 15th International Conference on Database Systems for Advanced Applications. 2010, 32–46
https://doi.org/10.1007/978-3-642-12098-5_3
|
13 |
Aggarwal C C, Han J W, Wang J Y, Yu P S. A framework for clustering evolving data streams. In: Proceedings of the 29th International Conference on Very Large Data Bases. 2003, 81–92
https://doi.org/10.1016/B978-012722442-8/50016-1
|
14 |
Hönle N, Großmann M, Reimann S, Mitschang B. Usability analysis of compression algorithms for position data streams. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2010, 240–249
https://doi.org/10.1145/1869790.1869825
|
15 |
Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. SIAM Journal on Computing. 2002, 31(6): 635–644
https://doi.org/10.1137/S0097539701398363
|
16 |
Chu S, Keogh E J, Hart D M, Pazzani M J. Iterative deepening dynamic time warping for time series. In: Proceedings of the 2nd SIAM International Conference on Data Mining. 2002, 195–212
https://doi.org/10.1137/1.9781611972726.12
|
17 |
Vlachos M, Gunopulos D, Kollios G. Discovering similar multidimensional trajectories. In: Proceedings of the 18th International Conference on Data Engineering. 2002, 673–684
https://doi.org/10.1109/ICDE.2002.994784
|
18 |
Chen L, Ng R T. On the marriage of Lp-norms and edit distance. In: Proceedings of the 30th International Conference on Very Large Data Bases. 2004, 792–803
https://doi.org/10.1016/B978-012088469-8.50070-X
|
19 |
Chen L, Özsu M T, Oria V. Robust and fast similarity search for moving object trajectories. In: Proceedings of ACMSIGMOD International Conference on Management of Data. 2005, 491–502
https://doi.org/10.1145/1066157.1066213
|
20 |
Roh G, Hwang S. NNCluster: an efficient clustering algorithm for road network trajectories. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2010, 47–61
https://doi.org/10.1007/978-3-642-12098-5_4
|
21 |
Mao J L, Song Q G, Jin C Q, Zhang Z G, Zhou A Y. TSCluWin: trajectory stream clustering over sliding window. In: Proceedings of International Conference on Database Systems for Advanced Applications. 2016, 133–148
https://doi.org/10.1007/978-3-319-32049-6_9
|
22 |
Zhang J, Xu J, Liao S S. Aggregating and sampling methods for processing GPS data streams for traffic state estimation. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(4): 1629–1641
https://doi.org/10.1109/TITS.2013.2264753
|
23 |
Castro P S, Zhang D Q, Li S J. Urban traffic modelling and prediction using large scale taxi GPS traces. In: Proceedings of International Conference on Pervasive Computing. 2012, 57–72
https://doi.org/10.1007/978-3-642-31205-2_4
|
24 |
Lloyd S P. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982, 28(2): 129–136
https://doi.org/10.1109/TIT.1982.1056489
|
25 |
Zhang T, Ramakrishnan R, Livny M. BIRCH: an efficient data clustering method for very large databases. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 1996, 103–114
https://doi.org/10.1145/233269.233324
|
26 |
Babcock B, Datar M, Motwani R, O’Callaghan L. Maintaining variance and k-medians over data stream windows. In: Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2003, 234–243
https://doi.org/10.1145/773153.773176
|
27 |
Aggarwal C C, Yu P S. A framework for clustering uncertain data streams. In: Proceedings of IEEE International Conference on Data Engineering. 2008, 150–159
https://doi.org/10.1109/ICDE.2008.4497423
|
28 |
Zhou A Y, Cao F, Qian W N, Jin C Q. Tracking clusters in evolving data streams over sliding windows. Knowledge and Information Systems, 2008, 15(2): 181–214
https://doi.org/10.1007/s10115-007-0070-x
|
29 |
Jin C Q, Yu J X, Zhou A Y, Cao F. Efficient clustering of uncertain data streams. Knowledge and Information Systems, 2014, 40(3): 509–539
https://doi.org/10.1007/s10115-013-0657-3
|
30 |
Won J I, Kim S W, Baek J H, Lee J. Trajectory clustering in road network environment. In: Proceedings of IEEE Symposium on Computational Intelligence and Data Mining. 2009, 299–305
https://doi.org/10.1109/CIDM.2009.4938663
|
31 |
Han B, Liu L, Omiecinski E. Road-network aware trajectory clustering: integrating locality, flow, and density. IEEE Transactions on Mobile Computing, 2015, 14(2): 416–429
https://doi.org/10.1109/TMC.2013.119
|
32 |
Lange R, Dürr F, Rothermel K. Efficient real-time trajectory tracking. The VLDB Journal, 2011, 20(5): 671–694
https://doi.org/10.1007/s00778-011-0237-7
|
33 |
Nehme R V, Rundensteiner E A. SCUBA: scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects. In: Proceedings of the 10th International Conference on Advances in Database Technology. 2006, 1001–1019
https://doi.org/10.1007/11687238_58
|
34 |
Sacharidis D, Patroumpas K, Terrovitis M, Kantere V, Potamias M, Mouratidis K, Sellis T. On-line discovery of hot motion paths. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology. 2008, 392–403
https://doi.org/10.1145/1353343.1353392
|
35 |
Zheng Y, Yuan N J, Zheng K, Shang S. On discovery of gathering patterns from trajectories. In: Proceedings of IEEE International Conference on Data Engineering. 2013, 242–253
https://doi.org/10.1109/ICDE.2013.6544829
|
36 |
Tang L A, Zheng Y, Yuan J, Han J W, Leung A, Hung C C, Peng W C. On discovery of traveling companions from streaming trajectories. In: Proceedings of the 28th IEEE International Conference on Data Engineering. 2012, 186–197
https://doi.org/10.1109/ICDE.2012.33
|
37 |
Li X H, Ceikute V, Jensen C S, Tan K L. Effective online group discovery in trajectory databases. IEEE Transactions on Knowledge & Data Engineering, 2013, 25(12): 2752–2766
https://doi.org/10.1109/TKDE.2012.193
|
38 |
Deng Z, Hu Y Y, Zhu M, Huang X H, Du B. A scalable and fast OPTICS for clustering trajectory big data. Cluster Computing, 2015, 18(2): 549–562
https://doi.org/10.1007/s10586-014-0413-9
|
39 |
Costa G, Manco G, Masciari E. Dealing with trajectory streams by clustering and mathematical transforms. Journal of Intelligent Information Systems, 2014, 42(1): 155–177
https://doi.org/10.1007/s10844-013-0267-2
|
40 |
Yu Y W, Wang Q, Wang X D, Wang H, He J. Online clustering for trajectory data stream of moving objects. Computer Science & Information Systems, 2013, 10(3): 1293–1317
https://doi.org/10.2298/CSIS120723049Y
|
41 |
Jeung H, Yiu M L, Zhou X F, Jensen C S, Shen H T. Discovery of convoys in trajectory databases. Proceedings of the VLDB Endowment, 2008, 1(1): 1068–1080
https://doi.org/10.14778/1453856.1453971
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|