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

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 R^sb-tree, R-tree with semibulk loading) for efficiently managing frequent updates from massive moving objects. The concept of semibulk loading is exploiting 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 the previous works in terms of update and query performance as well in a realistic environment. In order to further increase buffer hit ratio for the proposed approach, a new page-replacement policy that exploits the level of buffered node is proposed. Furthermore, we introduce the concept of deferring threshold ratio (dtr) that simply enables deferring CPU- and I/O-intensive operations such as node splits and removals. Extensive experimental evaluation reveals that the proposed approach is far more efficient than previous approaches for managing frequent updates under various settings.