A framework of traveling companion discovery on trajectory data streams

Abstract

The advance of mobile technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data streams. In this study, we investigate the problem of discovering object groups that travel together (i.e., traveling companions) from trajectory data streams. Such technique has broad applications in the areas of scientific study, transportation management, and military surveillance. To discover traveling companions, the monitoring system should cluster the objects of each snapshot and intersect the clustering results to retrieve moving-together objects. Since both clustering and intersection steps involve high computational overhead, the key issue of companion discovery is to improve the efficiency of algorithms. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A data structure termed traveling buddy is designed to facilitate scalable and flexible companion discovery from trajectory streams. The traveling buddies are microgroups of objects that are tightly bound together. By only storing the object relationships rather than their spatial coordinates, the buddies can be dynamically maintained along the trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. In addition, we extend the proposed framework to discover companions on more complicated scenarios with spatial and temporal constraints, such as on the road network and battlefield. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. Experimental results show that our proposed buddy-based approach is an order of magnitude faster than the baselines and achieves higher accuracy in companion discovery.

References

1. Aung, H.-H. 2008. Discovering moving groups of tagged objects. Tech. rep., National University of Singapore. http://www.nus.edu.sg/.
2. Bakalov, P., Hadjieleftheriou, M., and Tsotras, V. J. 2005. Time relaxed spatiotemporal trajectory joins. In Proceedings of the 13^th Annual ACM International Workshop on Geographic Information Systems (GIS'05). 182--191.
3. Benkert, M., Guddmundsson, J., Hubner, F., and Wolle, T. 2008. Reporting flock patterns. Comput. Geom. Theory Appl. 41, 3, 111--125.
4. Cadez, I. V., Gaffney, S., and Smyth, P. 2000. A general probabilistic framework for clustering individuals and objects. In Proceedings of the 6^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'00). 140--149.
5. Ester, M., Kriegel, H.-P., Sander, J.,Wimmer, M., and Xu, X. 1998. Incremental clustering for mining in a data warehousing environment. In Proceedings of the 24^th International Conference on Very Large Data Bases (VLDB'98). 323--333.
6. Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2^nd International Conference on Knowledge Discovery and Data Mining (KDD'96). 226--231.
7. Gaffney, S. and Smyth, P. 1999. Trajectory clustering with mixtures of regression models. In Proceedings of the 5^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'99). 63--72
8. Giannotti, F., Nanni, M., Pedreschi, D., and Pinelli, F. 2007. Trajectory pattern mining. In Proceedings of the 13^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'07). 330--339.
9. Gonzalez, T. 1985. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293--306.
10. Gudmundsson, J. and Kreveld, M. V. 2006. Computing longest duration flocks in trajectory data. In Proceedings of the 14^th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS'06). 35--42.
11. Gudmundsson, J., Kreveld, M. V., and Speckmann, B. 2004. Efficient detection of motion patterns in spatio-temporal data sets. In Proceedings of the 12^th Annual ACM International Workshop on Geographic Information Systems (GIS'04). 250--257.
12. Gunopoulos, D. 2002. Discovering similar multidimensional trajectories. In Proceedings of the 18^th International Conference on Data Engineering (ICDE'02). 673--684.
13. Han, J. and Kamber, M. 2006. Data Mining: Concepts and Techniques 2^nd Ed. Morgan Kaufmann.
14. Har-Peled, S. 2003. Clustering motion. Discr. Comput. Geom. 31, 4, 545--565.
15. Horvitz, E., Apacible, J., Sarin, R., and Liao, L. 2005. Prediction, expectation, and surprise: Methods, designs, and study of a deployed traffic forecasting service. In Proceedings of the 21^st Conference on Uncertainty in Artificial Intelligence (UAI'05).
16. Jensen, C. S., Lin, D., and Ooi, B. C. 2007. Continuous clustering of moving objects. IEEE Trans. Knowl. Data Engin. 19, 9, 1161--1174.
17. Jeung, H., Yiu, M. L., Zhou, X., Jensen, C. S., and Shen, H. T. 2008. Discovery of convoys in trajectory databases. Proc. VLDB Endow. 1, 1, 1068--1080.
18. Kalnis, P., Mamoulis, N., and Bakiras, S. 2005. On discovering moving clusters in spatial-temporal data. In Proceedings of the 9^th International Conference on Advances in Spatial and Temporal Databases (SSTD'05). 364--381.
19. Krout, T. 2007. Cb manet scenario data distribution. Tech. rep., BBN.
20. Lee, J.-G., Han, J., and Whang, K.-Y. 2007. Trajectory clustering: A partition-and-group framework. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'07). 593--604.
21. Lee, M., Hsu, W., Jensen, C. S., Cui, B., and Teo, K. 2003. Supporting frequent updates in r-trees: A bottom-up approach. The VLDB J. 18, 3, 719--738.
22. Li, X., Han, J., Lee, J.-G., and Gonzalez, H. 2007. Traffic density based discovery of hot routes in road networks. In Proceedings of the 10^th International Conference on Advances in Spatial and Temporal Databases (SSTD'07). 441--459.
23. Li, Y., Han, J., and Yang, J. 2004. Clustering moving objects. In Proceedings of the 10^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'04). 617--622.
24. Li, Z., Ding, B., Han, J., and Kays, R. 2010. Swarm: Mining relaxed temporal moving object clusters accurate discovery of valid convoys from moving object trajectories. Proc. VLDB Endow. 3, 723--734.
25. Liu, L. and Wong, R. C.-W. 2011. Finding shortest path on land surface. In Proceedings of the ACM SIGMOD International Conference on Management of data (SIGMOD'11). 433--444.
26. Liu, Y., Chen, L., Pei, J., Chen, Q., and Zhao, Y. 2007. Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays. In Proceedings of the 5^th IEEE International Conference on Pervasive Computing and Communications (PerCom'07).
27. Nutanong, S., Zhang, R., Tanin, E., and Kulik, L. 2008. The v*-diagram: A query dependent approach to moving knn queries. Proc. VLDB Endow. 1, 1, 1095--1106.
28. Nutanong, S., Zhang, R., Tanin, E., and Kulik, L. 2010. Analysis and evaluation of v*-knn: An efficient algorithm for moving knn queries. VLDB J. 19, 3, 307--332.
29. Pearl, J. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co.
30. Shahabi, C., Tang, L. A., and Xing, S. 2008. Indexing land surface for efficient knn query. Proc. VLDB Endow. 1, 1, 1020--1031.
31. Tang, L.-A., Yu, X., Kim, S., Han, J., Hung, C.-C., and Peng, W.-C. 2010. Tru-alarm: Trustworthiness analysis of sensor networks in cyber-physical systems. In Proceedings of the IEEE International Conference on Data Mining (ICDM'10). 1079--1084.
32. Tang, L.-A., Zheng, Y., Xie, X., Yuan, J., Yu, X., and Han, J. 2011. Retrieving k-nearest neighboring trajectories by a set of point locations. In Proceedings of the 12^th International Conference on Advances in Spatial and Temporal Databases (SSTD'11). 223--241.
33. Tang, L.-A., Zheng, Y., Yuan, J., Han, J., Leung, A., Hung, C.-C., and Peng, W.-C. 2012. On discovery of traveling companions from streaming trajectories. In Proceedings of the 28^th IEEE International Conference on Data Engineering (ICDE'12). 186--197.
34. Tao, Y., Kollios, G., Considine, J., Li, F., and Papadias, D. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the 20^th IEEE International Conference on Data Engineering (ICDE'04). 214.
35. Tao, Y., Sheng, C., and Pei, J. 2011. On k-skip shortest paths. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'11). 421--432.
36. Xing, S. and Shahabi, C. 2010. Scalable shortest paths browsing on land surface. In Proceedings of the 18^th SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'10). 89--98.
37. Xing, S., Shahabi, C., and Pan, B. 2009. Continuous monitoring of nearest neighbors on land surface. Proc. VLDB Endow. 2, 1, 1114--1125.
38. Yang, D., Rundensteiner, E. A., and Ward, M. O. 2009. Neighbor-based pattern detection for windows over streaming data. In Proceedings of the 12^th International Conference on Extending Database Technology: Advances in Database Technology (EDBT'09). 529--540.
39. Yi, B., Jagadish, H. V., and Faloutsos, C. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the 14^th International Conference on Data Engineering (ICDE'98). 201--208.
40. Yoo, J. S. and Shekhar, S. 2004. A partial join approach for mining co-location patterns. In Proceedings of the 12^th Annual ACM International Workshop on Geographic Information Systems (GIS'04). 241--249.
41. Yuan, J., Zheng, Y., Xie, X., and Sun, G. 2011. Driving with knowledge from the physical world. In Proceedings of the 17^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'11). 316--324.
42. Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., and Huang, Y. 2010. T-drive: Driving directions based on taxi trajectories. In Proceedings of the 18^th SIGSPATIAL International Conference on Advances on Geographical Information Systems (GIS'10). 99--108.
43. Zhang, Q. and Lin, X. 2004. Clustering moving objects for spatial-temporal selectivity estimation. In Proceedings of the 15^th Australasian Database Conference (ADC'04). 123--130.
44. Zhang, R., Lin, D., Ramamohanarao, K., and Bertino, E. 2008. Continuous intersection joins over moving objects. In Proceedings of the 24^th International Conference on Data Engineering (ICDE'08). 863--872.
45. Zhang, R., Qi, J., Lin, D., Wang, W., and Wong, R. C.-W. 2011. A highly optimized algorithm for continuous intersection join queries over moving objects. VLDB J. 21, 4, 561--586.
46. Zheng, K., Zheng, Y., Xie, X., and Zhou, X. 2012. Reducing uncertainty of low-sampling-rate trajectories. In Proceedings of the 28^th IEEE International Conference on Data Engineering (ICDE'12). 1144--1155.
47. Zheng, Y., Xie, X., and Ma, W. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Engin. Bull. 33, 2, 32--40.
48. Zheng, Y. and Zhou, X. 2011. Computing with Spatial Trajectories. Springer.
49. Zhu, F., Yan, X., Han, J., Yu, P. S., and Cheng, H. 2007. Mining colossal frequent patterns by core pattern fusion. In Proceedings of the 23^rd International Conference on Data Engineering (ICDE'07). 706--715.

Index Terms

• Information systems

  • Information systems applications