Efficient indexing of the historical, present, and future positions of moving objects

ABSTRACT

Although significant effort has been put into the development of efficient spatio-temporal indexing techniques for moving objects, little attention has been given to the development of techniques that efficiently support queries about the past, present, and future positions of objects. The provisioning of such techniques is challenging, both because of the nature of the data, which reflects continuous movement, and because of the types of queries to be supported. This paper proposes the BB^x -index structure, which indexes the positions of moving objects, given as linear functions of time, at any time. The index stores linearized moving-object locations in a forest of B⁺ -trees. The index supports queries that select objects based on temporal and spatial constraints, such as queries that retrieve all objects whose positions fall within a spatial range during a set of time intervals. Empirical experiments are reported that offer insight into the query and update performance of the proposed technique.

REFERENCES

• 1: P. K. Agarwal and C. M. Procopiuc. Advances in Indexing for Mobile Objects. IEEE Data Eng. Bull., 25(2): 25--34, 2002.
• 2: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 3: A. Civilis, C. S. Jensen, J. Nenortaite, and S. Pakalnis. Efficient Tracking of Moving Objects with Precision Guarantees. In Proc. MobiQuitous, pp. 164--173, 2004.
• 4: C. S. Jensen, D. Lin, and B. C. Ooi. Query and Update Efficient B+-Tree Based Indexing of Moving Objects. Proc. VLDB, pp. 768--779, 2004.
• 5: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 6: M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-Temporal Access Methods. IEEE Data Eng. Bull., 26(2): 40--49, 2003.
• 7: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 8: Mario A. Nascimento , Jefferson R. O. Silva, Towards historical R-trees, Proceedings of the 1998 ACM symposium on Applied Computing, p.235-240, February 27-March 01, 1998, Atlanta, Georgia, United States [doi>10.1145/330560.330692]
• 9: B. C. Ooi, K. L. Tan, and C. Yu. Fast Update and Efficient Retrieval: an Oxymoron on Moving Object Indexes. In Proc. of Int. Web GIS Workshop, Keynote, 2002.
• 10: Jignesh M. Patel , Yun Chen , V. Prasad Chakka, STRIPES: an efficient index for predicted trajectories, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007639]
• 11: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 12: Indexing of Moving Objects for Location-Based Services, Proceedings of the 18th International Conference on Data Engineering, p.463, February 26-March 01, 2002
• 13: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 14: Jimeng Sun , Dimitris Papadias , Yufei Tao , Bin Liu, Querying about the Past, the Present, and the Future in Spatio-Temporal Databases, Proceedings of the 20th International Conference on Data Engineering, p.202, March 30-April 02, 2004
• 15: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 16: Yufei Tao , Dimitris Papadias, MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.431-440, September 11-14, 2001
• 17: Y. Tao, D. Papadias, and J. Sun. The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. In Proc. VLDB, pp. 790--801, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms, Performance

Keywords:
B-tree, indexing, mobile objects