Managing Frequent Updates in R-Trees for Update-Intensive Applications

Access this Article

Search this Article


Managing frequent updates is greatly important in many update-intensive applications, such as location-aware services,sensor networks, and stream databases. In this paper, we present an R-tree-based index structure (called Rsb-tree, R-tree withsemibulk loading) for efficiently managing frequent updates from massive moving objects. The concept of semibulk loading isexploiting a small in-memory buffer to defer, buffer, and group the incoming updates and bulk-insert these updates simultaneously.With a reasonable memory overhead (typically only 1 percent of the whole data set), the proposed approach far outperforms theprevious works in terms of update and query performance as well in a realistic environment. In order to further increase buffer hit ratiofor the proposed approach, a new page-replacement policy that exploits the level of buffered node is proposed. Furthermore, weintroduce the concept of deferring threshold ratio (dtr) that simply enables deferring CPU- and I/O-intensive operations such as nodesplits and removals. Extensive experimental evaluation reveals that the proposed approach is far more efficient than previousapproaches for managing frequent updates under various settings.


  • IEEE transactions on knowledge and data engineering

    IEEE transactions on knowledge and data engineering 21(11), 1573-1589, 2009-11

    IEEE Computer Society


  • NII Article ID (NAID)
  • Text Lang
  • Article Type
    journal article
  • ISSN
  • Data Source
Page Top