Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Processing and Optimization of Multiway Spatial Joins Using R-Trees

Dimitris Papadias, Nikos Mamoulis, and Yannis Theodoridis

  View Paper (PDF)  

Return to Query Optimization

Abstract
One of the most important types of query processing in spatial databases and geographic information systems is the spatial join, an operation that selects, from two relations, all object pairs satisfying some spatial predicate. A multiway join combines data originated from more than two relations. Although several techniques have been proposed for pairwise spatial joins, only limited work has focused on multiway spatial join processing. This paper solves multiway spatial joins by applying systematic search algorithms that exploit R-trees to efficiently guide search, without building temporary indexes or materializing intermediate results. In addition to general methodologies, we propose cost models and an optimization algorithm, and evaluate them through extensive experimentation.


References

Note: References link to DBLP on the Web.

[BG95]
Fahiem Bacchus , Adam J. Grove : On the Forward Checking Algorithm. CP 1995 : 292-308
[BvR95]
Fahiem Bacchus , Paul van Run : Dynamic Variable Ordering in CSPs. CP 1995 : 258-275
[BKS+90]
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
[BKS93]
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246
[D90]
Rina Dechter : Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition. Artificial Intelligence 41(3) : 273-312(1990)
[G84]
Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57
[G93]
Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993)
[HJR97]
Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner : Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997 : 396-405
[IK91]
Yannis E. Ioannidis , Younkyung Cha Kang : Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991 : 168-177
[I96]
Yannis E. Ioannidis : Query Optimization. Computing Surveys 28(1) : 121-123(1996)
[KF92]
Ibrahim Kamel , Christos Faloutsos : Parallel R-trees. SIGMOD Conference 1992 : 195-204
[KS97]
Nick Koudas , Kenneth C. Sevcik : Size Separation Spatial Join. SIGMOD Conference 1997 : 324-335
[LR94]
Ming-Ling Lo , Chinya V. Ravishankar : Spatial Joins Using Seeded Trees. SIGMOD Conference 1994 : 209-220
[MP98]
Nikos Mamoulis , Dimitris Papadias : Constraint-Based Algorithms for Computing Clique Intersection Joins. ACM-GIS 1998 : 118-123
[MP99a]
Nikos Mamoulis , Dimitris Papadias : Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999 : 1-12
[MP99b]
...
[O86]
Jack A. Orenstein : Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986 : 326-336
[P93]
...
[PS96]
Bernd-Uwe Pagel , Hans-Werner Six : Are Window Queries Representative for Arbitrary Range Queries? PODS 1996 : 150-160
[PST+93]
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
[PMD98]
Dimitris Papadias , Nikos Mamoulis , Vasilis Delis : Algorithms for Querying by Spatial Structure. VLDB 1998 : 546-557
[PMT99]
...
[PTS97]
...
[PS85]
...
[SKS97]
Abraham Silberschatz , Henry F. Korth , S. Sudarshan : Database System Concepts, 3rd Edition. McGraw-Hill Book Company 1997, ISBN 0-07-044756-X
[TS96]
Yannis Theodoridis , Timos K. Sellis : A Model for the Prediction of R-tree Performance. PODS 1996 : 161-171
[TSS98]
Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis : Cost Models for Join Queries in Spatial Databases. ICDE 1998 : 476-483

Referenced by

  1. Nikos Mamoulis , Dimitris Papadias : Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999 : 1-12

BIBTEX

@inproceedings{DBLP:conf/pods/PapadiasMT99,
  author    = {Dimitris Papadias and
                Nikos Mamoulis and
                Yannis Theodoridis},
   title     = {Processing and Optimization of Multiway Spatial Joins Using R-Trees},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {44-55},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM