Mindaugas Pelanis
Christian S. Jensen
Skip Abstract Section
Abstract
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 capacities continue to outperform Moore's Law, it becomes increasingly feasible to store online all the position information obtained from the moving e-service users. With the much slower advances in I/O speeds and many concurrent users, indexing techniques are of the essence in this scenario.Existing indexing techniques come in two forms. Some techniques capture the position of an object up until the time of the most recent position sample, while other techniques represent an object's position as a constant or linear function of time and capture the position from the current time and into the (near) future. This article offers an indexing technique capable of capturing the positions of moving objects at all points in time. The index substantially modifies partial persistence techniques, which support transaction time, to support valid time for monitoring applications. The performance of a timeslice query is independent of the number of past position samples stored for an object. No existing indices exist with these characteristics.
- Agarwal, P. K., Arge, L., and Erickson, J. 2000. Indexing moving points. In Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS). 175--186.]] Google Scholar
Digital Library
- Agarwal, P. K. and Har-Peled, S. 2001. Maintaining approximate extent measures of moving points. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). 148--157.]] Google ScholarDigital Library
- Basch, J., Guibas, L., and Hershberger, J. 1997. Data structures for mobile data. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 747--756.]] Google ScholarDigital Library
- Becker, B., Gschwind, S., Ohler, T., Seeger, B., and Widmayer, P. 1996. An asymptotically optimal multiversion B-tree. VLDB J. 5, 4, 264--275.]] Google ScholarDigital Library
- Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 322--331.]] Google ScholarDigital Library
- Brinkhoff, T. 2002. A framework for generating network-based moving objects. GeoInformatica 6, 2, 153--180.]] Google ScholarDigital Library
- Cai, M. and Revesz, P. Z. 2000. Parametric R-tree: An index structure for moving objects. In Proceedings of the 10th International Conference on Management of Data (COMAD).]]Google Scholar
- Chakka, V. P., Everspaugh, A., and Patel, J. M. 2003. Indexing large trajectory data sets with SETI. In Online Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR).]]Google Scholar
- Chon, H. D., Agrawal, D., and El Abbadi, A. 2002. Query processing for moving objects with space-time grid storage model. In Proceedings of the 3rd International Conference on Mobile Data Management (MDM). 121--128.]] Google ScholarDigital Library
- Čivilis, A., Jensen, C. S., Nenortaitė, J., and Pakalnis, S. 2004. Efficient tracking of moving objects with precision guarantees. In Proceedings of the 1st International Conference on Mobile and Ubiquitous Systems: Networking and Services. 164--173.]]Google Scholar
- Čivilis, A., Jensen, C. S., and Pakalnis, S. 2005. Techniques for efficient tracking of road-network-based moving objects. IEEE Trans. Knowl. Data Eng. 17, 5, 698--712.]] Google ScholarDigital Library
- Driscoll, J. R., Sarnak, N., Sleator, D. D., and Tarjan, R. E. 1989. Making data structures persistent. J. Comput. Syst. Sci. 38, 1, 86--124.]] Google ScholarDigital Library
- Hadjieleftheriou, M., Kollios, G., Tsotras, V. J., and Gunopulos, D. 2002. Efficient indexing of spatiotemporal objects. In Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 251--268.]] Google ScholarDigital Library
- Jensen, C. S., Lin, D., and Ooi, B. C. 2004. Query and update efficient B+-tree based indexing of moving objects. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 768--779.]]Google Scholar
- Johnson, T. and Shasha, D. 1993. B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half. J. Comput. Syst. Sci. 47, 1, 45--76.]] Google ScholarDigital Library
- Kollios, G., Gunopulos, D., and Tsotras, V. J. 1999. On indexing mobile objects. In Proceedings of the 18th ACM Symposium on Principles of Database Systems (PODS). 261--272.]] Google ScholarDigital Library
- Kollios, G., Tsotras, V. J., Gunopulos, D., Delis, A., and Hadjieleftheriou, M. 2001. Indexing animated objects using spatiotemporal access methods. IEEE Trans. Knowl. Data Eng. 13, 5, 758--777.]] Google ScholarDigital Library
- Kolovson, C. P. and Stonebraker, M. 1991. Segment indexes: Dynamic indexing techniques for multi-dimensional interval data. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 138--147.]] Google ScholarDigital Library
- Kumar, A., Tsotras, V. J., and Faloutsos, C. 1998. Designing access methods for bitemporal databases. IEEE Trans. Knowl. Data Eng. 10, 1, 1--20.]] Google ScholarDigital Library
- Lin, D., Jensen, C. S., Ooi, B. C., and Šaltenis, S. 2005. Efficient indexing of the historical, present, and future positions of moving objects. In Proceedings of the 6th International Conference on Mobile Data Management (MDM). 59--66.]] Google ScholarDigital Library
- Lomet, D. B. 1991. Grow and post index trees: Roles, techniques and future potential. In Proceedings of the International Symposium on Advances in Spatial Databases. 183--206.]] Google ScholarDigital Library
- Papadopoulos, D., Kollios, G., Gunopulos, D., and Tsotras, V. J. 2002. Indexing mobile objects on the plane. In Proceedings of the 5th International Workshop on Mobility in Databases and Distributed Systems (MDDS). 693--697.]] Google ScholarDigital Library
- Patel, J. M., Chen, Y., and Chakka, V. P. 2004. STRIPES: An efficient index for predicted trajectories. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 637--646.]] Google ScholarDigital Library
- Pfoser, D., Theodoridis, Y., and Jensen, C. S. 2000. Novel approaches in query processing for moving object trajectories. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). 395--406.]] Google ScholarDigital Library
- Porkaew, K., Lasaridis, I., and Mehrotra, S. 2001. Querying mobile objects in spatio-temporal databases. In Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD). 59--78.]] Google ScholarDigital Library
- Procopiuc, C. M., Agarwal, P. K., and Har-Peled, S. 2002. STAR-tree: An efficient self-adjusting index for moving objects. In Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX). 178--193.]] Google ScholarDigital Library
- Šaltenis, S., Jensen, C. S., Leutenegger, S. T., and Lopez, M. A. 2000. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 331--342.]] Google ScholarDigital Library
- Šaltenis, S. and Jensen, C. S. 2002. Indexing of moving objects for location-based services. In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). 463--472.]] Google ScholarDigital Library
- Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the 13th IEEE International Conference on Data Engineering (ICDE). 422--432.]] Google ScholarDigital Library
- Song, Z. and Roussopoulos, N. 2001. Hashing moving objects. In Proceedings of the 2nd International Conference on Mobile Data Management (MDM). 161--172.]] Google ScholarDigital Library
- Song, Z. and Roussopoulos, N. 2003. SEB-tree: An approach to index continuously moving objects. In Proceedings of the 4th International Conference on Mobile Data Management (MDM). 340--344.]] Google ScholarDigital Library
- Sun, J., Papadias, D., Tao, Y., and Liu, B. 2004. Querying about the past, the present and the future in spatio-temporal databases. In Proceedings of the 20th IEEE International Conference on Data Engineering (ICDE). 202--213.]] Google ScholarDigital Library
- Tao, Y. and Papadias, D. 2001. MV3R-tree: A spatio-temporal access method for timestamp and interval queries. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 431--440.]] Google ScholarDigital Library
- Tao. Y., Papadias, D., and Sun, J. 2003. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 790--801.]]Google Scholar
- Tao, Y., Papadias, D., and Zhang, J. 2002. Cost models for overlapping and multiversion structures. ACM Trans. Database Syst. 27, 3, 299--342.]] Google ScholarDigital Library
- Tayeb, J., Ulusoy, Ö., and Wolfson, O. 1998. A quadtree based dynamic attribute indexing method. Computer J. 41, 3, 185--200.]]Google ScholarCross Ref
- Van den Bercken, J. and Seeger, B. 1996. Query processing techniques for multiversion access methods. In Proceedings of the 22th International Conference on Very Large Data Bases (VLDB). 168--179.]] Google ScholarDigital Library
- Wolfson, O., Xu, B., Chamberlain, S., and Jiang, L. 1998. Moving objects databases: Issues and solutions. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management (SSDBM). 111--122.]] Google ScholarDigital Library
- Wolfson, O., Chamberlain, S., Dao, S., Jiang, L., and Mendez, G. 1998. Cost and imprecision in modeling the position of moving objects. In Proceedings of the 14th IEEE International Conference on Data Engineering (ICDE). 588--596.]] Google ScholarDigital Library
- Wolfson, O., Sistla, A. P., Chamberlain, S., and Yesha, Y. 1999. Updating and querying databases that track mobile units. Distrib. Parall. Datab. 7, 3, 257--387.]] Google ScholarDigital Library
- Yao, A. C.-C. 1978. On random 2-3 trees. Acta Inf. 9, 2, 159--170.]]Google ScholarDigital Library
Index Terms
- Indexing the past, present, and anticipated future positions of moving objects
Recommendations
Efficient indexing of the historical, present, and future positions of moving objects
MDM '05: Proceedings of the 6th international conference on Mobile data managementAlthough 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, ...
Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree
MDM '02: Proceedings of the Third International Conference on Mobile Data ManagementWith the rapid advances of wireless communications and positioning techniques, tracking the positions of moving objects is becoming increasingly feasible and necessary. Traditional spatial index structures are not suitable for storing these positions ...
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