The R*-tree: an efficient and robust access method for points and rectangles Export

@article{citeulike:343069, abstract = {The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R * -tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R * -tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R * -tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R * -tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.}, address = {New York, NY, USA}, author = {Beckmann, Norbert and Kriegel, Hans P. and Schneider, Ralf and Seeger, Bernhard}, booktitle = {SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data}, citeulike-article-id = {343069}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=98741}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/93597.98741}, doi = {10.1145/93597.98741}, isbn = {0-89791-365-5}, issn = {0163-5808}, journal = {SIGMOD Rec.}, keywords = {data-structure, database}, location = {Atlantic City, New Jersey, United States}, month = {June}, number = {2}, pages = {322--331}, posted-at = {2007-05-24 14:07:17}, priority = {0}, publisher = {ACM}, title = {The R*-tree: an efficient and robust access method for points and rectangles}, url = {http://dx.doi.org/10.1145/93597.98741}, volume = {19}, year = {1990} }

TY - JOUR ID - citeulike:343069 L3 - citeulike-article-id:343069 JF - SIGMOD Rec. N2 - The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R * -tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R * -tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R * -tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R * -tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees. VL - 19 PB - ACM IS - 2 CY - Atlantic City, New Jersey, United States T2 - SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data SN - 0-89791-365-5 SP - 322 TI - The R*-tree: an efficient and robust access method for points and rectangles EP - 331 AD - New York, NY, USA KW - data-structure KW - database AU - Beckmann, Norbert AU - Kriegel, Hans AU - Schneider, Ralf AU - Seeger, Bernhard PY - 1990/06// UR - http://dx.doi.org/10.1145/93597.98741 ER -