Online clustering of streaming trajectories

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

References

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[15] Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. SIAM Journal on Computing. 2002, 31(6): 635–644

[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

[17] Vlachos M, Gunopulos D, Kollios G. Discovering similar multidimensional trajectories. In: Proceedings of the 18th International Conference on Data Engineering. 2002, 673–684

[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

[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

[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

[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

[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

[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

[24] Lloyd S P. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982, 28(2): 129–136

[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

[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

[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

[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

[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

[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

[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

[32] Lange R, Dürr F, Rothermel K. Efficient real-time trajectory tracking. The VLDB Journal, 2011, 20(5): 671–694

[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

[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

[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

[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

[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

[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

[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

[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

[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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature