RUM+-tree: A new multidimensional index supporting frequent updates

Update-intensive applications, such as location-aware services, sensor networks, and stream databases, face with the problem of frequent updating. R-tree and its variants are dominant indexing structures for multi-dimensional object. An update in R-tree traditionally consists of a deletion and an insertion, which is sometimes inefficient. In this paper, we present an R-tree-based index structure called RUM+-tree for enabling efficient frequent updates. In RUM+-tree, compared to R-tree, two additional data structures are maintained: an Update Memo and a hash table. An object's leaf node can be accessed directly through the hash table and the Update Memo records the versioning information of the most recent data. The idea of RUM+-Tree is to deal with updates locally in a bottom-up manner as often as possible. Only when the update involves multiple MBRs, a multi-version solution is utilized for acceleration. Compared to RUM-tree [1], RUM+-tree can reduce the new version to be created. Thus, it can accelerate the garbage clean and update procedure. Compared to LUR-tree [5], RUM+-tree eliminates traditional updates like used by R-tree completely. Our experimental results show that our technique outperforms RUM-tree and LUR-tree significantly.