Robust B+ -Tree-Based Indexing of Moving Objects

Christian Søndergaard Jensen, Dalia Tiesyte, Nerius Tradisauskas

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

19 Citationer (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.
TitelProceedings of the Seventh International Conference on Mobile Data Management
Antal sider9
ForlagIEEE Computer Society Press
ISBN (Trykt)0769525261
StatusUdgivet - 2006
BegivenhedInternational Conference on Mobile Data Management - Nara, Japan
Varighed: 9 maj 200612 maj 2006
Konferencens nummer: 7


KonferenceInternational Conference on Mobile Data Management


Dyk ned i forskningsemnerne om 'Robust B+ -Tree-Based Indexing of Moving Objects'. Sammen danner de et unikt fingeraftryk.