Efficient and Lightweight In-Memory Implementation of R*-Tree

File:"RTree 2D.svg." Wikipedia, the Free Encyclopedia. Web. 25 June 2011.

This package provides an efficient and lightweight in-memory C++ implementation of the R*-tree [1]. Initially, the code has been developed by our group to be used in their experiments. The following papers has benefited from the package:

Supporting Location-Based Approximate-Keyword Queries, Sattam Alsubaiee, Alexander Behm, and Chen Li, ACM SIGSPATIAL GIS 2010.
Location-Based Instant Search, Shengyue Ji and Chen Li, SSDBM 2011.

The package works with 2D objects and supports the following operations:

Insert objects
Delete objects
Range search
Nearest neighbor search

Main contributors

Sattam Alsubaiee, PhD student
Chen Li, Faculty

Download source code

rstartree.tar.gz

Acknowledgement

We thank Shengyue Ji for writing the R*-tree storage manager.

References

[1] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles', Proceedings of the ACM SIGMOD, 1990