ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Model for the Prediction of R-tree Performance.

Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171
@inproceedings{DBLP:conf/pods/TheodoridisS96,
  author    = {Yannis Theodoridis and
               Timos K. Sellis},
  title     = {A Model for the Prediction of R-tree Performance},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {161-171},
  ee        = {http://doi.acm.org/10.1145/237661.237705, db/conf/pods/TheodoridisS96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we present an analytical model that predicts the performance of R-trees (and its variants) when a range query needs to be answered. The cost model uses knowledge of the dataset only, i.e., the proposed formula that estimates the number of disk accesses is a function of data properties, namely, the amount of data and their density in the work space. In other words, the proposed model is applicable even before the construction of the R-tree index, a fact that makes is a useful tool for dynamic spatial databases. Several experiments on synthetic and real datasets show that the proposed analytical model is very accurate, the relative error being usually around 10%-15%, for uniform and non-uniform distributions. We belief that this error is involved with the gap between efficient R-tree variants, like the R*-tree, and an optimum, not implemented yet, method. Our work extends previous research concerning R-tree analysis and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada. ACM Press 1996, ISBN 0-89791-781-2
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 940 KB]

References

[BKSS90]
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
[Com79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[FK94]
Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13 BibTeX
[Fre87]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[FSR87]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 BibTeX
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[Gut94]
Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994) BibTeX
[HSW89]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
[KF93]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX
[KF94]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX
[Knu73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[Knu81]
Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley 1981, ISBN 0-201-03822-6
BibTeX
[NHS84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[PSTW93]
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer: Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993: 214-221 BibTeX
[PSW95]
Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94 BibTeX
[PTSE95]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer: Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees. SIGMOD Conference 1995: 92-103 BibTeX
[RKV95]
Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79 BibTeX
[RL85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[TS94]
Yannis Theodoridis, Timos K. Sellis: Optimization Issues in R-tree Construction (Extended Abstract). IGIS 1994: 270-273 BibTeX
[TP95]
Yannis Theodoridis, Dimitris Papadias: Range Queries Involving Spatial Relations: A Performance Analysis. COSIT 1995: 537-551 BibTeX
[TVS96]
...
[Vit84]
Jeffrey Scott Vitter: Faster Methods for Random Sampling. Commun. ACM 27(7): 703-718(1984) BibTeX
[Vit85]
Jeffrey Scott Vitter: Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11(1): 37-57(1985) BibTeX

Referenced by

  1. Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, Carlotta Domeniconi: Approximating Multi-Dimensional Aggregate Range Queries over Real Attributes. SIGMOD Conference 2000: 463-474
  2. Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.: Spatial Join Selectivity Using Power Laws. SIGMOD Conference 2000: 177-188
  3. Christian Böhm, Hans-Peter Kriegel: Dynamically Optimizing High-Dimensional Index Structures. EDBT 2000: 36-50
  4. Andrew U. Frank, Stéphane Grumbach, Ralf Hartmut Güting, Christian S. Jensen, Manolis Koubarakis, Nikos A. Lorentzos, Yannis Manolopoulos, Enrico Nardelli, Barbara Pernici, Hans-Jörg Schek, Michel Scholl, Timos K. Sellis, Babis Theodoulidis, Peter Widmayer: Chorochronos: A Research Network for Spatiotemporal Database Systems. SIGMOD Record 28(3): 12-21(1999)
  5. Swarup Acharya, Viswanath Poosala, Sridhar Ramaswamy: Selectivity Estimation in Spatial Databases. SIGMOD Conference 1999: 13-24
  6. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
  7. Guido Proietti, Christos Faloutsos: I/O Complexity for Range Queries on Region Data Stored Using an R-tree. ICDE 1999: 628-635
  8. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  9. M. Seetha Lakshmi, Shaoyu Zhou: Selectivity Estimation in Extensible Databases - A Neural Network Approach. VLDB 1998: 623-627
  10. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  11. Apostolos Papadopoulos, Yannis Manolopoulos: Similarity Query Processing Using Disk Arrays. SIGMOD Conference 1998: 225-236
  12. Paolo Ciaccia, Marco Patella, Pavel Zezula: A Cost Model for Similarity Queries in Metric Spaces. PODS 1998: 59-68
  13. Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis: Cost Models for Join Queries in Spatial Databases. ICDE 1998: 476-483
  14. Scott T. Leutenegger, Mario A. Lopez: The Effect of Buffering on the Performance of R-Trees. ICDE 1998: 164-171
  15. Christos Faloutsos, H. V. Jagadish, Nikolaos Sidiropoulos: Recovering Information from Summary Data. VLDB 1997: 36-45
  16. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: A Cost Model for Estimating the Performance of Spatial Joins Using R-trees. SSDBM 1997: 30-38
  17. Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:15 2009