Special Issue: Computer Networks and Distributed Computing

• Articles • Previous Articles     Next Articles

Indexing Future Trajectories of Moving Objects in a Constrained Network

Ji-Dong Chen and Xiao-Feng Meng   

  1. School of Information, Renmin University of China, Beijing 100872, China Key Laboratory of Data Engineering and Knowledge Engineering, Ministry of Education, Beijing 100872, China
  • Received:2006-05-01 Revised:2007-02-02 Online:2007-03-10 Published:2007-03-10

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.

Key words: Program synthesis; very high-level language; parallelism and concurrency; formal specification; first-order logic;

[1] Saltenis S, Jensen C S. Indexing of moving objects for location-based service. In -\it Proc. 18th Int. Conf. Data Engineering}, San Jose, CA, 2002, pp.463--472.

[2] Agarwal P K, Arge L, Erickson J. Indexing moving points (extended abstract). In -\it Proc. the 19th ACM SIGMOD-SIGACT-SIGART Symp. Principles of Database Systems}, Dallas, Texas, 2000, pp.175--186.

[3] Jensen C S, Lin D, Ooi B C. Query and update efficient B$+$-tree based indexing of moving objects. In -\it Proc. 30th Int. Conf. Very Large Data Bases}, Toronto, Canada, 2004, pp.768--779.

[4] Patel M, Chen Y, Chakka V. STRIPES: An efficient index for predicted trajectories. In -\it Proc. the ACM SIGMOD Int. Conf. Management of Data}, Paris, France, 2004, pp.637--646.

[5] Kollios G, Gunopulos D, Tsotras J V. On indexing mobile objects. In -\it Proc. the 8th ACM SIGMOD-SIGACT-SIGART Symp. Principles of Database Systems}, Philadelphia, USA, 1999, pp.261--272.

[6] Saltenis S, Jensen C S, Leutenegger S T, Lopez M A. Indexing the positions of continuously moving objects. In -\it Proc. the ACM SIGMOD Int. Conf. Management of Data}, Dallas, Texas, USA, 2000, pp.331--342.

[7] Tao Y, Papadias D, Sun J. The TPR*-tree: An optimized spatiotemporal access method for predictive queries. In -\it Proc. 29th Int. Conf. Very Large Data Bases}, Berlin, Germany, 2003, pp.790--801.

[8] Almeida V T D, G\"uting R H. Indexing the trajectories of moving objects in networks. -\it GeoInformatica}, 2005, 9(1): 33--60.

[9] Frentzos E. Indexing objects moving on fixed networks. In -\it Proc. the 8th Int. Symp. Spatial and Temporal Databases}, Santorini Island, Greece, 2003, pp.289--305.

[10] Pfoser D, Jensen C S. Indexing of network constrained moving objects. In -\it Proc. 11th ACM Int. Symp. Advances in Geographic Information Systems}, New Orleans, Louisiana, USA, 2003, pp.25--32.

[11] Nascimento M A, Silva J R O. Towards historical R-trees. In -\it ACM Symposium on Applied Computing}, Atlanta, Georgia, 1998, pp.235--240.

[12] Pfoser D, Jensen C S, Theodoridis Y. Novel approaches in query processing for moving object trajectories. In -\it Proc. 26th Int. Conf. Very Large Data Bases}, Cairo, Egypt, 2000, pp.395-406.

[13] Tao Y, Papadias D. MV3R-tree: A spatio-temporal access method for timestamp and interval queries. In -\it Proc. 27th Int. Conf. Very Large Data Bases}, Roma, Italy, 2001, pp.431--440.

[14] Guttman A. R-trees: A dynamic index structure for spatial searching. In -\it Proc. the ACM SIGMOD Int. Conf. Management of Data}, Boston, USA, 1984, pp.47--57.

[15] Yiu M L, Tao Y, Mamoulis N. The $B-\rm dual\hbox--}Tree}$: Indexing moving objects by space-filling curves in the dual space. To appear in -\it Very Large Data Base Journal}, 2006.

[16] Nagel K, Schreckenberg M. A cellular automaton model for freeway traffic. -\it Journal Physique}, 1992, 2: 2221--2229.

[17] Theodoridis Y, Stefanakis E, Sellis T K. Efficient cost models for spatial queries using R-trees. -\it TKDE}, 2000, 12(1): 19--32.

[18] Brinkhoff T. A framework for generating network-based moving objects. -\it GeoInformatica}, 2002, 6(2): 153--180.
[1] Bin-Bin Liu, Wei Dong, Jia-Xin Liu, Ya-Ting Zhang, Dai-Yan Wang. ProSy: API-Based Synthesis with Probabilistic Model [J]. Journal of Computer Science and Technology, 2020, 35(6): 1234-1257.
[2] WANG Yunfeng(王云峰),PANG Jun(庞军),ZHA Ming(查鸣),YANG Zhaohui(杨朝晖)and ZHENG Guoliang(郑国梁). A Formal Software Development Approach Using Refinement Calculus [J]. , 2001, 16(3): 0-0.
[3] CHEN Haiming;. Function Definition Language FDL andIts Implementation [J]. , 1999, 14(4): 414-421.
[4] Lin Hong; Chen Guoliang;. Program Constructionby Verifying Specification [J]. , 1998, 13(6): 597-607.
[5] Zhang Yaoxue; Chen Hua; Zhang Yue; Liu Guoli;. SDL-TRAN-An Interactive Generator for Formal Description Language SDL [J]. , 1996, 11(1): 49-60.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved