Robust B+ -Tree-Based Indexing of Moving Objects

Christian Søndergaard Jensen, Dalia Tiesyte, Nerius Tradisauskas

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

19 Citations (Scopus)


With the emergence of an infrastructure that enables the geo-positioning of on-line, mobile users, the management of so-called moving objects has emerged as an active area of research. Among the indexing techniques for efficiently answering predictive queries on moving-object positions, the recent Bx-tree is based on the B+-tree and is relatively easy to integrate into an existing DBMS. However, the Bx-tree is sensitive to data skew. This paper proposes a new query processing algorithm for the Bx-tree that fully exploits the available data statistics to reduce the query enlargement that is needed to guarantee perfect recall, thus significantly improving robustness. The new technique is empirically evaluated and compared with four other approaches and with the TPR-tree, a competitor that is based on the R*-tree. The results indicate that the new index is indeed more robust than its predecessor?it significantly reduces the number of I/O operations per query for the workloads considered. In many settings, the TPR-tree is outperformed as well.
Original languageEnglish
Title of host publicationProceedings of the Seventh International Conference on Mobile Data Management
Number of pages9
PublisherIEEE Computer Society Press
Publication date2006
ISBN (Print)0769525261
Publication statusPublished - 2006
EventInternational Conference on Mobile Data Management - Nara, Japan
Duration: 9 May 200612 May 2006
Conference number: 7


ConferenceInternational Conference on Mobile Data Management

Fingerprint Dive into the research topics of 'Robust B+ -Tree-Based Indexing of Moving Objects'. Together they form a unique fingerprint.

Cite this