Indexing Future Trajectories of Moving Objects in a Constrained Network  

作　　者：陈继东 孟小峰 

机构地区：[1]School of Information, Renmin University of China, Beijing 100872, China [2]Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education, Beijing 100872, China

出　　处：《Journal of Computer Science & Technology》2007年第2期245-251,共7页计算机科学技术学报（英文版）

基　　金：Partly supported by the National Natural Science Foundation of China （Grant No. 60573091）, the Key Project of Ministry of Education of China （Grant No. 03044）, Program for New Century Excellent Talents in University （NCET）, Program for Creative Ph.D. Thesis in University. Acknowledgments The authors would like to thank Hai-Xun Wang from IBM T. J. Watson Research, Karine Zeitouni from PRISM, Versailles Saint- Quentin University in France and Stephane Grumbach from CNRS, LIAMA China for many helpful advices.

摘　　要：Advances in wireless sensor networks and positioning technologies enable new applications monitoring moving objects. Some of these applications, such as traffic management, require the possibility to query the future trajectories of the objects. In this paper, we propose an original data access method, the ANR-tree, which supports predictive queries. We focus on real life environments, where the objects move within constrained networks, such as vehicles on roads. We introduce a simulation-based prediction model based on graphs of cellular automata, which makes full use of the network constraints and the stochastic traffic behavior. Our technique differs strongly from the linear prediction model, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changing frequently. The data structure extends the R-tree with adaptive units which group neighbor objects moving in the similar moving patterns. The predicted movement of the adaptive unit is not given by a single trajectory, but instead by two trajectory bounds based on different assumptions on the traffic conditions and obtained from the simulation. Our experiments, carried on two different datasets, show that the ANR-tree is essentially one order of magnitude more efficient than the TPR-tree, and is much more scalable.Advances in wireless sensor networks and positioning technologies enable new applications monitoring moving objects. Some of these applications, such as traffic management, require the possibility to query the future trajectories of the objects. In this paper, we propose an original data access method, the ANR-tree, which supports predictive queries. We focus on real life environments, where the objects move within constrained networks, such as vehicles on roads. We introduce a simulation-based prediction model based on graphs of cellular automata, which makes full use of the network constraints and the stochastic traffic behavior. Our technique differs strongly from the linear prediction model, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changing frequently. The data structure extends the R-tree with adaptive units which group neighbor objects moving in the similar moving patterns. The predicted movement of the adaptive unit is not given by a single trajectory, but instead by two trajectory bounds based on different assumptions on the traffic conditions and obtained from the simulation. Our experiments, carried on two different datasets, show that the ANR-tree is essentially one order of magnitude more efficient than the TPR-tree, and is much more scalable.

关 键 词：DATABASE spatial database access methods moving objects 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]