Query and update efficient B⁺-tree based indexing of moving objects

ABSTRACT

A number of emerging applications of data management technology involve the monitoring and querying of large quantities of continuous variables, e.g., the positions of mobile service users, termed moving objects. In such applications, large quantities of state samples obtained via sensors are streamed to a database. Indexes for moving objects must support queries efficiently, but must also support frequent updates. Indexes based on minimum bounding regions (MBRs) such as the R-tree exhibit high concurrency overheads during node splitting, and each individual update is known to be quite costly. This motivates the design of a solution that enables the B⁺ -tree to manage moving objects. We represent moving-object locations as vectors that are timestamped based on their update time. By applying a novel linearization technique to these values, it is possible to index the resulting values using a single B⁺-tree that partitions values according to their timestamp and otherwise preserves spatial proximity. We develop algorithms for range and k nearest neighbor queries, as well as continuous queries. The proposal can be grafted into existing database systems cost effectively. An extensive experimental study explores the performance characteristics of the proposal and also shows that it is capable of substantially outperforming the R-tree based TPR-tree for both single and concurrent access scenarios.

References

1. {1} N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R^*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In Proc. ACM SIGMOD, pp. 322-331, 1990.
2. {2} R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In Proc. IDEAS, pp. 44-53, 2002.
3. {3} A. Civilis, C. S. Jensen, J. Nenortaite, and S. Pakalnis. Efficient Tracking of Moving Objects with Precision Guarantees. In Proc. MobiQuitous, 2004, 10 pages, to appear.
4. {4} C. Faloutsos and S. Roseman. Fractals for Secondary Key Retrieval. In Proc. PODS, pp. 247-252, 1989.
5. {5} A. Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. In Proc. ACM SIGMOD, pp. 47-57, 1984.
6. {6} C. S. Jensen and S. Saltenis. Towards Increasingly Update Efficient Moving-Object Indexing. IEEE Data Eng. Bull., 25(2): 35-40, 2002.
7. {7} G. Kollios, D. Gunopulos, V. J. Tsotras. On Indexing Mobile Objects. In Proc. PODS, pp. 261-272, 1999.
8. {8} M. Kornacker and D. Banks. High-Concurrency Locking in R-Trees. In Proc. VLDB, pp. 134-145, 1995.
9. {9} D. Kwon, S. Lee, and S. Lee. Indexing the Current Positions of Moving Objects Using the Lazy Update R-Tree. In Proc. MDM, pp. 113-120, 2002.
10. {10} M. L. Lee, W. Hsu, C. S. Jensen, B. Cui, and K. L. Teo. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In Proc. VLDB, pp. 608-619, 2003.
11. {11} M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-Temporal Access Methods. IEEE Data Eng. Bull., 26(2): 40-49, 2003.
12. {12} 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.
13. {13} 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.
14. {14} J. M. Patel, Y. Chen and V. P. Chakka. STRIPES: An Efficient Index for Predicted Trajectories. In Proc. ACM SIGMOD , 2004, to appear.
15. {15} D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel Approaches in Query Processing for Moving Objects. In Proc. VLDB, pp. 395-406, 2000.
16. {16} C. M. Procopiuc, P. K. Agarwal, and S. Har-Peled. Star-Tree: An Efficient Self-Adjusting Index for Moving Objects. In Proc. ALENEX, pp. 178-193, 2002.
17. {17} F. Ramsak, V. Markl, R. Fenk, M. Zirkel, K. Elhardt, and R. Bayer. Integrating the UB-Tree Into a Database System Kernel. In Proc. VLDB, pp. 263-272, 2000.
18. {18} N. Roussopoulos and D. Leifker. Direct Spatial Search on Pictorial Databases Using Packed R-Trees. In Proc. ACM SIGMOD, pp. 17-31, 1985.
19. {19} S. Saltenis, 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.
20. {20} H. Samet. The Quadtree and Related Hierarchical Data Structures. ACM Comp. Surv., 16(2): 187-260, 1984.
21. {21} V. Srinivasan and M. J. Carey. Performance of B-Tree Concurrency Control Algorithms. In the Proc. ACM SIGMOD, pp. 416-425, 1991.
22. {22} 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.
23. {23} Y. Tao, J. Zhang, D. Papadias, and N. Mamoulis. An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces. IEEE TKDE, to appear.
24. {24} J. Tayeb, O. Ulusoy, and O. Wolfson. A Quadtree Based Dynamic Attribute Indexing Method. The Computer Journal, 41(3): 185-200, 1998.
25. {25} C. Yu, B. C. Ooi, K. L. Tan and H. V. Jagadish. Indexing the Distance: An Efficient Method to KNN Processing. In Proc. VLDB, pp. 421-430, 2001.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

  • Information retrieval

    • Document representation

    • Evaluation of retrieval results

    • Search engine architectures and scalability

      • Search engine indexing

  • Information storage systems

    • Record storage systems

      • Directory structures

        • B-trees

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)