Supporting Frequent Updates in R-Trees: A Bottom-Up Approach
| dc.contributor.author | Mong Li LEE | en_US |
| dc.contributor.author | Wynne HSU | en_US |
| dc.contributor.author | Christian S. JENSEN | en_US |
| dc.contributor.author | Bin CUI | en_US |
| dc.contributor.author | Keng Lik TEO | en_US |
| dc.date.accessioned | 2004-10-21T14:28:52Z | en_US |
| dc.date.accessioned | 2017-01-23T06:59:47Z | |
| dc.date.available | 2004-10-21T14:28:52Z | en_US |
| dc.date.available | 2017-01-23T06:59:47Z | |
| dc.date.issued | 2004-04-01T00:00:00Z | en_US |
| dc.description.abstract | 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 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 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. | en_US |
| dc.format.extent | 417880 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1444 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRA4/04 | en_US |
| dc.title | Supporting Frequent Updates in R-Trees: A Bottom-Up Approach | en_US |
| dc.type | Technical Report | en_US |