Handling frequent updates of moving objects

ABSTRACT

A critical issue in moving object databases is to develop appropriate indexing structures for continuously moving object locations so that queries can still be performed efficiently. However, such location changes typically cause a high volume of updates, which in turn poses serious problems on maintaining index structures. In this paper we propose a Lazy Group Update (LGU) algorithm for disk-based index structures of moving objects. LGU contains two key additional structures to group ``similar'' updates so that they can be performed together: a disk-based insertion buffer (I-Buffer) for each internal node, and a memory-based deletion table (D-Table) for the entire tree. Different strategies of ``pushing down'' an overflow I-Buffer to the next level are studied. Comprehensive empirical studies over uniform and skewed datasets, as well as simulated street traffic data show that LGU achieves a significant improvement on update throughput while allowing a reasonable performance for queries.

REFERENCES

• 1: Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
• 2: L. Arge. Private communications, 2004.
• 3: Lars Arge , Klaus Hinrichs , Jan Vahrenhold , Jeffrey Scott Vitter, Efficient Bulk Operations on Dynamic R-trees, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.328-348, January 15-16, 1999
• 4: 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]
• 5: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 6: T. Brinkhoff. Generating traffic data. Bulletin on Data Engineering, IEEE Computer Society, 26(2):19--25, 2003.
• 7: Rupesh Choubey , Li Chen , Elke A. Rundensteiner, GBI: A Generalized R-Tree Bulk-Insertion Strategy, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.91-108, July 20-23, 1999
• 8: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 9: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: George Kollios , Dimitris Papadopoulos , Dimitrios Gunopulos , J. Tsotras, Indexing mobile objects using dual transformations, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.238-256, April 2005 [doi>10.1007/s00778-004-0139-z]
• 11: 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]
• 12: Anil Kumar , Vassilis J. Tsotras , Christos Faloutsos, Designing Access Methods for Bitemporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.1-20, January 1998 [doi>10.1109/69.667079 ]
• 13: Dongseop Kwon , Sangjun Lee , Sukho Lee, Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree, Proceedings of the Third International Conference on Mobile Data Management, p.113-120, January 08-11, 2002
• 14: Kim S. Larsen, Relaxed multi-way trees with group updates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.93-101, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375566]
• 15: M. L. Lee, W. Hsu, C. S. Jensen, and K. L. Teo. Supporting frequent updates in R-trees: a bottom-up approach. In Proc. VLDB, 2003.
• 16: Lauri Malmi , Eljas Soisalon-Soininen, Group updates for relaxed height-balanced trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.358-367, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304011]
• 17: Hoda Mokhtar , Jianwen Su , Oscar Ibarra, On moving object queries: (extended abstract), Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543638]
• 18: Spencer W. Ng, Advances in Disk Technology: Performance Issues, Computer, v.31 n.5, p.75-81, May 1998 [doi>10.1109/2.675641 ]
• 19: Dimitris Papadopoulos , George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Indexing Mobile Objects on the Plane, Proceedings of the 13th International Workshop on Database and Expert Systems Applications, p.693-697, September 02-06, 2002
• 20: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 21: ACM SIGMOD Record staff, Science of design for information systems: report of the NSF workshop, Seattle, 2003, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974145]
• 22: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 23: J. Zhou and Ke. A. Ross. Buffering Accesses to Memory-Resident Index Structures. VLDB, 2003.
• 24: S. Saltenis. http://www.cs.auc.dk/ simas/tpr/tpr.tar.gz.
• 25: 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
• 26: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 27: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 28: Zhexuan Song , Nick Roussopoulos, Hashing Moving Objects, Proceedings of the Second International Conference on Mobile Data Management, p.161-172, January 08-10, 2001
• 29: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 30: Y. Tao, D. Papadias, and J. Sun. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In VLDB, 2003.
• 31: J. Tayeb, O. Ulusoy, and O. Wolfson. A quadtree based dynamic attribute indexing method. The Computer Journal, 41(3), 1998.
• 32: Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
• 33: Yannis Theodoridis , Jefferson R. O. Silva , Mario A. Nascimento, On the Generation of Spatiotemporal Datasets, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.147-164, July 20-23, 1999
• 34: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998
• 35: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, Trajectory queries and octagons in moving object databases, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584860]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance

Keywords:
TPR-tree, lazy group update, moving objects database