Review - The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.

Timos K. Sellis: Review - The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. ACM SIGMOD Digital Review 2: (2000) BibTeX

Review

The R*-Tree paper has been the starting point for many researchers working in the area of spatial data indexing. It adapts the well known and very influential R-Tree structure to perform more efficiently in the case of point and window queries. The paper's contribution is twofold: first it presents new algorithms for partitioning spatial data objects in order to build the nodes of the tree, and second it provides a good performance comparison that served as a model for subsequent performance studies. A major positive aspect is that in the course of deriving new partitioning algorithms, it provided a lot of insight into what are the major factors impacting the performance of the structure (e.g. the fact that the perimeter of the objects is the determinant factor and needs to be accounted for when designing partitioning algorithms). Needless to say that the R*-Tree has served as the basic implementation of R-trees since then and has influenced a lot of researchers.

References

[1]: Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

BibTeX

Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]