Supporting Frequent Updates in R-Trees: A Bottom-Up Approach Mong-Li Lee, Wynne Hsu, Christian S. Jensen, Bin Cui, and Keng Lik Teo   View Paper (PDF)   Return to Access Methods & Temporal Data (Session B7) Abstract Advances in hardware-related technologies promise to enable new data management applica- tions 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 in- efficient. We present a bottom-up update strategy for R-trees that generalizes existing update tech- niques 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 indicate that the bottom-up strategy outperforms the traditional top-down technique, leads to indices with better query performance, achieves higher throughput, and is scalable. ©2004 Association for Computing Machinery