Abstract.
With the recent advances in wireless networks, embedded systems, and GPS technology, databases that manage the location of moving objects have received increased interest. In this paper, we present indexing techniques for moving object databases. In particular, we propose methods to index moving objects in order to efficiently answer range queries about their current and future positions. This problem appears in real-life applications such as predicting future congestion areas in a highway system or allocating more bandwidth for areas where a high concentration of mobile phones is imminent. We address the problem in external memory and present dynamic solutions, both for the one-dimensional and the two-dimensional cases. Our approach transforms the problem into a dual space that is easier to index. Important in this dynamic environment is not only query performance but also the update processing, given the large number of moving objects that issue updates. We compare the dual-transformation approach with the TPR-tree, an efficient method for indexing moving objects that is based on time-parameterized index nodes. An experimental evaluation shows that the dual-transformation approach provides comparable query performance but has much faster update processing. Moreover, the dual method does not require establishing a predefined query horizon.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal PK, Arge L, Erickson J (2000) Indexing moving points. In: Proceedings of the 19th ACM symposium on principles of database systems, pp 175-186
Agarwal PK, Arge L, Erickson J, Franciosa PG, Vitter JS (1998) Efficient searching with linear constraints. In: Proceedings of the 17th ACM symposium on principles of database systems, pp 169-178
Agarwal PK, Har-Peled S (2001) Maintaining approximate exten measures of moving points. In: Proceedings of the 12th ACM-SIAM symposium on discrete algorithms, pp 148-157
Aggarwal A, Vitter JS (1988) The input/output complexity of sorting and related problems. Commun ACM 31(9):1116-1127
Arge L, Samoladas V, Vitter JS (1999) On two-dimensional indexability and optimal range search indexing. In: Proceedings of the 18th ACM PODS, pp 346-357
Arge L, Vitter JS (1996) Optimal dynamic interval management in external memory. In: Proceedings of the 37th annual symposium on foundations of computer science, pp 560-569
Basch J, Guibas L, Hershberger J (1997) Data structures for mobile data. In: Proceedings of the 8th ACM-SIAM symposium on discrete algorithms, pp 747-756
Beckmann N, Kriegel H, Schneider R, Seeger B (1998) The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of ACM SIGMOD, Atlantic City, NJ, pp 322-331
Chazelle B, Rosenberg B (1992) Lower bounds on the complexity of simplex range reporting on a pointer machine. In: Proceedings of the 19th international colloquium on automata, languages and programming. Lecture notes in computer science, vol 623. Springer, Berlin Heidelberg New York, pp 439-449
Choi Y-J, Chung C-W (2002) Selectivity estimation for spatio-temporal queries to moving objects. In: Proceedings of ACM SIGMOD, Madison, WI, pp 440-451
Chomicki J, Revesz P (1999) A geometric framework for specifying spatiotemporal objects. In: Proceedings of the 6th international workshop on time representation and reasoning, pp 41-46
Chon HD, Agrawal D, 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, pp 121-126
Cole R (1986) Searching and storing similar lists. J Algorithms 7(2):202-220
Driscoll J, Sarnak N, Sleator D, Tarjan RE (1989) Making data structures persistent. J Comput Sys Sci 38(1):86-124
http://europa.eu.int/eur-lex/pri/en/oj/dat/ 2002/l\_201/l\_20120020731en00370047.pdf (2002)
Elbassioni KM, Elmasry A, Kamel I (2003) An efficient indexing scheme for multi-dimensional moving objects. In: Proceedings of the 9th international conference on database theory (ICDT), pp 425-439
Gaede V, Günther O (1998) Multidimensional access methods. ACM Comput Surv 30(2):170-231
Goldstein J, Ramakrishnan R, Shaft U, Yu JB (1997) Processing queries by linear constraints. In: Proceedings of the 16th ACM PODS symposium on principles of database systems, Tucson, AZ, pp 257-267
Günther O (1989) The design of the cell tree: an object-oriented index structure for geometric databases. In: Proceedings of the 5th IEEE international conference on data engineering, Los Angeles, pp 598-605
Güting RH, Böhlen MH, Erwing M, Jensen CS, Lorentzos NA, Schneider M, Vazirgiannis M (2000) A foundation for representing and querying moving objects. ACM Trans Database Sys 26(1):1-42
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM SIGMOD, Boston, pp 47-57
Hadjieleftheriou M, Kollios G, Gunopulos D, Tsotras V (2003) On-line discovery of dense areas in spatio-temporal databases. In: Proceedings of the 8th SSTD, pp 306-324
Hadjieleftheriou M, Kollios G, Tsotras V (2003) Performance evaluation of spatio-temporal selectivity estimation techniques. In: Proceedings of the 15th international conference on scientific and statistical database management, pp 202-211
Jagadish HV(1990) On indexing line segments. In: Proceedings of the 16th international conference on very large data bases, Brisbane, Queensland, Australia, pp 614-625
Kalashnikov DV, Prabhakar S, Hambrusch SE, Aref WG (2002) Efficient evaluation of continuous range queries on moving objects. In: Proceedings of the 13th international conference DEXA, pp 731-740
Kollios G, Gunopulos D, Tsotras V (1999) Nearest neighbor queries in a mobile environment. In: Proceedings of the 1st workshop on spatio-temporal database management, Edinburgh, UK, pp 119-134
Kollios G, Gunopulos D, Tsotras V (1999) On indexing mobile objects. In: Proceedings of the 18th ACM symposium on principles of database systems, pp 261-272
Lazaridis I, Porkaew K, Mehrotra S (2002) Dynamic queries over mobile objects. In: Proceedings of the 8th international conference on extending database technology, pp 269-286
Matousek J (1992) Efficient partition trees. Discrete Comput Geom 8:432-448
Mokhtar H, Su J, Ibarra OH (2002) On moving object queries. In: Proceedings of the 21st ACM PODS, pp 188-198
Overmars MH (1983) The design of dynamic data structures. Lecture notes in computer science, vol 156. Springer, Berlin Heidelberg New York
Papadias D, Tao Y, Kalnis P, Zhang J (2002) Indexing spatio-temporal data warehouses. In: Proceedings of the 18th international conference on data engineering, pp 166-175
Papadopoulos D, Kollios G, Gunopulos D, Tsotras VJ (2002) Indexing mobile objects on the plane. In: Proceedings of the 5th international workshop on mobility in databases and distributed systems (DEXA), Aix-en-Provence, France, pp 693-697
Patel J, Chen Y, Chakka VP (2004) STRIPES: an efficient index for predicted trajectories. In: Proceedings of ACM SIGMOD
Pfoser D, Jensen C, Theodoridis Y (2000) Novel approaches in query proceedings for moving objects. In: Proceedings of the 26th international conference on very large data bases, pp 395-406
Porkaew K, Lazaridis I, Mehrotra S (2001) Querying mobile objects in spatio-temporal databases. In: Proceedings of the 7th SSTD, pp 59-78
Prabhakar S, Xia Y, Kalashnikov DV, Aref W, Hambrusch S (2002) Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. In: IEEE Trans Comput 51(10):1124-1140
Procopiuc CM, Agarwal PK, Har-Peled S (2002) Star-tree: an efficient self-adjusting index for moving objects. In: Proceedings of the 4th workshop on algorithm engineering and experiments, pp 178-193
Saltenis S, Jensen C, Leutenegger S, Lopez MA (1999) Indexing the positions of continuously moving objects. Time-Center Technical Report TR-44. http://www.cs.auc.dk/research/DP/tdb/ TimeCenter/TimeCenterPublications/TR-44.pdf
Saltenis S, Jensen C, Leutenegger S, Lopez MA (2000) Indexing the positions of continuously moving objects. In: Proceedings of ACM SIGMOD, pp 331-342
Saltenis S, Jensen CS (2002) Indexing of moving objects for location-based services. In: Proceedings of the 18th international conference on data engineering, San Jose, CA, pp 463-472
Samet H (1990) The design and analysis of spatial data structures. Addison-Wesley, Reading, MA
Sellis T, Roussopoulos N, Faloutsos C (1987) The R+-tree: a dynamic index for multi-dimensional objects. In: Proceedings of the 13th international conference on very large data bases, Brighton, UK, pp 507-518
Sistla AP, Wolfson O, Chamberlain S, Dao S (1997) Modeling and querying moving objects. In: Proceedings of the 13th international conference on data engineering, pp 422-432
Song Z, Roussopoulos N (2001) K-nearest neighbor search for moving query points. In: Proceedings of the 7th SSTD, Redondo Beach, CA, pp 79-96
Subramanian S, Ramaswamy S (1995) The P-range tree: a new data structure for range searching in secondary memory. In: Proceedings of the 6th annual symposium on discrete algorithms, New York, pp 378-387
Tao Y, Kollios G, Considine J, Li F, Papadias D (2004) Spatio-temporal aggregation using sketches. In: Proceedings of the 20th international conference on data engineering, pp 214-226
Tao Y, Papadias D (2002) Time-parameterized queries in spatio-temporal databases. In: Proceedings of ACM SIGMOD, Madison, WI, pp 334-345
Tao Y, Papadias D, Qiongmao S (2002) Continuous nearest neighbor search. In: Proceedings of the 28th international conference on very large data bases, pp 287-298
Tao Y, Papadias D, 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, pp 790-801
Tao Y, Sun J, Papadias D (2003) Selectivity estimation for predictive spatio-temporal queries. In: Proceedings of the 19th international conference on data engineering, Bangalore, India, pp 417-428
Tayeb J, Olusoy O, Wolfson O (1998) A quadtree-based dynamic attribute indexing method. Comput J 41(3):185-200
Wolfson O, Chamberlain S, Dao S, Jiang L, Mendez G (1998) Cost and imprecision in modeling the position of moving objects. In: Proceedings of the 14th international conference on data engineering, Orlando, FL, pp 588-596
Wolfson O, Xu B, Chamberlain S, Jiang L (1998) Moving objects databases: issues and solutions. In: Proceedings of the 11th international conference on scientific and statistical database management, Capri, Italy, pp 111-122
Zhu H, Su J, Ibarra OH (2002) Trajectory queries and octagons in moving object databases. In: Proceedings of the 11th ACM international conference on information and knowledge management, pp 413-421
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 27 April 2003, Accepted: 11 May 2004, Published online: 14 September 2004
Edited by: J. Veijalainen
George Kollios: Supported by NSF CAREER Award 0133825.
Dimitrios Gunopulos: Supported by NSF ITR 0220148, NSF CAREER Award 9984729, NSF IIS-9907477, and NRDRP.
Vassilis J. Tsotras: Supported by NSF IIS-9907477, NSF EIA-9983445 and the DoD.
Rights and permissions
About this article
Cite this article
Kollios, G., Papadopoulos, D., Gunopulos, D. et al. Indexing mobile objects using dual transformations. The VLDB Journal 14, 238–256 (2005). https://doi.org/10.1007/s00778-004-0139-z
Issue Date:
DOI: https://doi.org/10.1007/s00778-004-0139-z