Main-Memory Operation Buffering for Efficient R-Tree Update

Studenteropgave: Kandidatspeciale og HD afgangsprojekt

  • Laurynas Biveinis
Emerging communication and sensor technologies enable new applications of database technology that require database systems to efficiently support very high rates of spatial-index updates. Previous works in this area exhibit one or more of the following drawbacks: they require the availability of large amounts of main memory, they do not exploit all the main memory that is indeed available, or they fail to support some of the standard index operations.
Assuming a setting where the index updates need not be written to disk immediately, we propose an R-tree-based indexing technique that does not exhibit any of these drawbacks. This technique exploits the buffering of update operations in main memory as well as the grouping of operations to reduce disk I/O. In particular, operations are performed in bulk so that multiple operations are able to share I/O. The emptying of buffers is controlled by means of an analytical cost model.
The thesis reports on empirical studies that demonstrate that the cost model is effective in controlling the buffer emptying. The studies also show that, in terms of update I/O performance, the proposed technique improves on state of the art in settings with frequent updates: it is significantly more efficient than an LRU-cached R-tree and a previous proposal for an update-efficient R-tree.
Udgivelsesdatojun. 2007
ID: 61070854