Dan Lin
Christian S. Jensen
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 BBx -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.
- P. K. Agarwal and C. M. Procopiuc. Advances in Indexing for Mobile Objects. IEEE Data Eng. Bull., 25(2): 25--34, 2002.Google Scholar
- B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An Asymptotically Optimal Multiversion B-Tree. VLDB Journal 5(4): 264--275, 1996. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- G. Kollios, D. Gunopulos, V. J. Tsotras. On Indexing Mobile Objects. In Proc. PODS, pp. 261--272, 1999. Google ScholarDigital Library
- M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-Temporal Access Methods. IEEE Data Eng. Bull., 26(2): 40--49, 2003.Google Scholar
- B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the Clustering Properties of the Hilbert Space-Filling Curve. IEEE TKDE, 13(1): 124--141, 2001. Google ScholarDigital Library
- M. A. Nascimento and J. R. O. Silva. Towards Historical R-trees. In Proc. ACM Symposium on Applied Computing, pp. 235--240, 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. M. Patel, Y. Chen, and V. P. Chakka. STRIPES: An Efficient Index for Predicted Trajectories. In Proc. ACM SIGMOD, pp. 637--646, 2004. Google ScholarDigital Library
- D. Pfoser, C. S. Jensen and Y. Theodoridis. Novel Approaches in Query Processing for Moving Objects. In Proc. VLDB, pp. 395--406, 2000. Google ScholarDigital Library
- S. Šaltenis and C. S. Jensen. Indexing of Moving Objects for Location-Based Services. In Proc. ICDE, pp. 463--472, 2002. Google ScholarDigital Library
- S. Šaltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the Positions of Continuously Moving Objects. In Proc. ACM SIGMOD, pp. 331--342, 2000. Google ScholarDigital Library
- J. Sun, D. Papadias, Y. Tao, and B. Liu. Querying about the Past, the Present, and the Future in Spatio-Temporal Databases. In Proc. ICDE, pp. 202--213, 2004. Google ScholarDigital Library
- J. Schiller and A. Voisard, editors. Location-Based Services. Morgan Kaufmann Publishers, 2004. Google ScholarDigital Library
- Y. Tao and D. Papadias. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In Proc. VLDB, pp. 431--440, 2001. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Efficient indexing of the historical, present, and future positions of moving objects
Recommendations
Indexing the past, present, and anticipated future positions of moving objects
With the proliferation of wireless communications and geo-positioning, e-services are envisioned that exploit the positions of a set of continuously moving users to provide context-aware functionality to each individual user. Because advances in disk ...
An Indexing Method for Answering Queries on Moving Objects
We consider the problem of indexing a set of objects moving in d -dimensional spaces along linear trajectories. A simple external-memory indexing scheme is proposed to efficiently answer general range queries. The following are examples of the queries ...
On past-time indexing of moving objects
Tracking of mobile objects trajectories is one of many modern applications supported by Spatiotemporal databases. Within the context of this application, queries about the present, future or past positions of the objects need to be answered. Several ...
Comments