Supporting Frequent Updates in R-Trees: A Bottom-Up Approach

Mong Li Lee, Wynne Hsu, Christian Søndergaard Jensen, Bin Cui, Keng Lik Teo

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskning

145 Citationer (Scopus)


Advances in hardware-related technologies promise to enable new data management applications that monitor continuous processes. In these applications, enormous amounts of state samples are obtained via sensors and are streamed to a database. Further, updates are very frequent and may exhibit locality. While the R-tree is the index of choice for multi-dimensional data with low dimensionality, and is thus relevant to these applications, R-tree updates are also relatively inefficient. We present a generalized bottom-up update strategy for R-trees that generalizes existing update techniques and aims to improve update performance. It has different levels of reorganization—ranging from global to local—during updates, avoiding expensive top-down updates. A compact main-memory summary structure that allows direct access to the R-tree index nodes is used together with efficient bottom-up algorithms. Empirical studies show that the bottom-up strategy outperforms the traditional top-down technique, leads to indices with better query performance, achieves higher throughput, and is scalable.
TitelProceedings of the Twentynineth International Conference on Very Large Data Bases, Berlin, Germany, September 9–11
StatusUdgivet - 2003
BegivenhedSupporting Frequent Updates in R-Trees: A Bottom-Up Approach - Busan, Sydkorea
Varighed: 17 nov. 200317 nov. 2003


KonferenceSupporting Frequent Updates in R-Trees: A Bottom-Up Approach

Bibliografisk note

ISSN ; -