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

A Cost Model for Estimating the Performance of Spatial Joins Using R-trees.

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
@inproceedings{DBLP:conf/ssdbm/HuangJR97,
  author    = {Yun-Wu Huang and
               Ning Jing and
               Elke A. Rundensteiner},
  editor    = {Yannis E. Ioannidis and
               David M. Hansen},
  title     = {A Cost Model for Estimating the Performance of Spatial Joins
               Using R-trees},
  booktitle = {Ninth International Conference on Scientific and Statistical
               Database Management, Proceedings, August 11-13, 1997, Olympia,
               Washington, USA},
  publisher = {IEEE Computer Society},
  year      = {1997},
  isbn      = {0-8186-7952-2},
  pages     = {30-38},
  ee        = {db/conf/ssdbm/HuangJR97.html},
  crossref  = {DBLP:conf/ssdbm/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The development of a cost model for predicting the performance of spatial joins has been identified in the literature as an important and difficult problem. In this paper, we present the first cost model that can predict the performance of spatial joins using R-trees. Based on two existing R-trees (join targets), our model first estimates the number of expected I/Os for the join process by assuming a zero buffer size. Our method for this estimation extends the cost model for R-tree window queries (developed by Kamel and Faloutsos and by Pagel et al.) to also handle spatial joins (which are more complex). In the context of spatial join processing, this number of zero-buffer expected I/Os is not practical for performance prediction in a buffered environment. To model the buffer impact, we use an (exponential) distribution function to measure the probability that a buffer-less I/O would cause a page fault in a buffered environment. Based on this probability and the zero-buffer expected I/O cost, the estimated number of I/Os for an R-tree join can then be computed. The comparisons between the predictions from our cost model and the actual results from our experiments based on real GIS maps show that the average relative error ratio is about 10% with a maximum of about 20% for a wide range of buffer sizes. Therefore, our model is a useful tool for the query optimization of spatial join queries.

Copyright © 1997 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 5, SSDBM, DBPL, KRDB, ADBIS, COOPIS, SIGBDP" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Online Edition: IEEE Computer Society DL

Citation Page

Printed Edition

Yannis E. Ioannidis, David M. Hansen (Eds.): Ninth International Conference on Scientific and Statistical Database Management, Proceedings, August 11-13, 1997, Olympia, Washington, USA. IEEE Computer Society 1997, ISBN 0-8186-7952-2
Contents BibTeX

References

[1]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[2]
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
[3]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX
[4]
...
[5]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 BibTeX
[6]
Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13 BibTeX
[7]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 BibTeX
[8]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[9]
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 BibTeX
[10]
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486 BibTeX
[11]
Yun-Wu Huang, Matthew C. Jones, Elke A. Rundensteiner: Improving Spatial Intersect Joins Using Symbolic Intersect Detection. SSD 1997: 165-177 BibTeX
[12]
...
[13]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX
[14]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220 BibTeX
[15]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258 BibTeX
[16]
Wei Lu, Jiawei Han: Distance-Associated Join Indices for Spatial Range Search. ICDE 1992: 284-292 BibTeX
[17]
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
[18]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[19]
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
[20]
Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270 BibTeX
[21]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 BibTeX
[22]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[23]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX
[24]
Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990) BibTeX
[25]
...
[26]
Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171 BibTeX
[27]
Michael Ubell: The Montage Extensible DataBlade Achitecture. SIGMOD Conference 1994: 482 BibTeX

Referenced by

  1. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  2. Gísli R. Hjaltason, Hanan Samet: Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998: 237-248
  3. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
SSDBM 1997: Copyright © by IEEE,
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:42:53 2009