On discovery of traveling companions from streaming trajectories

Lu An Tang*, Yu Zheng, Jing Yuan, Jiawei Han, Alice Leung, Chih Chieh Hung, Wen-Chih Peng

*Corresponding author for this work

研究成果: Conference article同行評審

133 引文 斯高帕斯(Scopus)


The advance of object tracking technologies leads to huge volumes of spatio-temporal data collected in the form of trajectory data stream. In this study, we investigate the problem of discovering object groups that travel together (i.e., traveling companions) from trajectory stream. 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 algorithm's efficiency. We propose the models of closed companion candidates and smart intersection to accelerate data processing. A new data structure termed traveling buddy is designed to facilitate scalable and flexible companion discovery on trajectory stream. The traveling buddies are micro-groups 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 trajectory stream with low cost. Based on traveling buddies, the system can discover companions without accessing the object details. The proposed methods are evaluated with extensive experiments on both real and synthetic datasets. The buddy-based method is an order of magnitude faster than existing methods. It also outperforms other competitors with higher precision and recall in companion discovery.

頁(從 - 到)186-197
期刊Proceedings - International Conference on Data Engineering
出版狀態Published - 30 七月 2012
事件IEEE 28th International Conference on Data Engineering, ICDE 2012 - Arlington, VA, United States
持續時間: 1 四月 20125 四月 2012

指紋 深入研究「On discovery of traveling companions from streaming trajectories」主題。共同形成了獨特的指紋。