Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Integration of Spatial Join Algorithms for Processing Multiple Inputs

Nikos Mamoulis and Dimitris Papadias

  View Paper (PDF)  

Return to Spatial Databases

Abstract
Several techniques that compute the join between two spatial data sets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, thus providing solutions for the case where at least one input comes as an intermediate result of another database operator. In this paper we analyse previous work on spatial joins and propose a novel algorithm, called slot index spatial join (SISJ), that efficiently computes the spatial join between two inputs, only one of which is indexed by an R-tree. Going one step further, we show how SISJ and other spatial join algorithms can be implemented as operators in a database environment that joins more than two spatial inputs. We study the differences between relational and spatial multi-way joins and propose a dynamic programming algorithm that optimizes the execution of complex spatial queries.


References

Note: References link to DBLP on the Web.

[APR+98]
Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter : Scalable Sweeping-Based Spatial Join. VLDB 1998 : 570-581
[BC81]
Philip A. Bernstein , Dah-Ming W. Chiu : Using Semi-Joins to Solve Relational Queries. JACM 28(1) : 25-40(1981)
[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
[BKS93]
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246
[BKS96]
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Parallel Processing of Spartial Joins Using R-trees. ICDE 1996 : 258-265
[Bur89]
...
[Gra93]
Goetz Graefe : Query Evaluation Techniques for Large Databases. Computing Surveys 25(2) : 73-170(1993)
[Gü93]
Oliver Günther : Efficient Computation of Spatial Joins. ICDE 1993 : 50-59
[Gut84]
Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57
[GG98]
Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998)
[HJR97a]
Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner : Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997 : 396-405
[HJR97b]
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
[IK90]
Yannis E. Ioannidis , Younkyung Cha Kang : Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990 : 312-321
[JK84]
Matthias Jarke , Jürgen Koch : Query Optimization in Database Systems. Computing Surveys 16(2) : 111-152(1984)
[KC98]
Kihong Kim , Sang K. Cha : Sibling Clustering of Tree-Based Spatial Indexes for Efficient Spatial Query Processing. CIKM 1998 : 398-405
[KF93]
Ibrahim Kamel , Christos Faloutsos : On Packing R-trees. CIKM 1993 : 490-499
[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
[LR96]
Ming-Ling Lo , Chinya V. Ravishankar : Spatial Hash-Joins. SIGMOD Conf. 1996 : 247-258
[MP99]
...
[Ore86]
Jack A. Orenstein : Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986 : 326-336
[PD96]
Jignesh M. Patel , David J. DeWitt : Partition Based Spatial-Merge Join. SIGMOD Conf. 1996 : 259-270
[PM98]
Apostolos Papadopoulos , Yannis Manolopoulos : Similarity Query Processing Using Disk Arrays. SIGMOD Conference 1998 : 225-236
[PMD98]
Dimitris Papadias , Nikos Mamoulis , Vasilis Delis : Algorithms for Querying by Spatial Structure. VLDB 1998 : 546-557
[PMT99]
Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis : Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999 : 44-55
[PS85]
...
[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
[PYK+97]
Jignesh M. Patel , Jie-Bing Yu , Navin Kabra , Kristin Tufte , Biswadeep Nag , Josef Burger , Nancy E. Hall , Karthikeyan Ramasamy , Roger Lueder , Curt Ellman , Jim Kupsch , Shelly Guo , David J. DeWitt , Jeffrey F. Naughton : Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation. SIGMOD Conference 1997 : 336-347
[Rot91]
Doron Rotem : Spatial Join Indices. ICDE 1991 : 500-509
[RKV95]
Nick Roussopoulos , Stephen Kelley , Frédéic Vincent : Nearest Neighbor Queries. SIGMOD Conference 1995 : 71-79
[RL85]
Nick Roussopoulos , Daniel Leifker : Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985 : 17-31
[SKS97]
Abraham Silberschatz , Henry F. Korth , S. Sudarshan : Database System Concepts, 3rd Edition. McGraw-Hill Book Company 1997, ISBN 0-07-044756-X
[TSS98]
Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis : Cost Models for Join Queries in Spatial Databases. ICDE 1998 : 476-483
[vdBSW97]
Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer : A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997 : 406-415

Referenced by

  1. Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis : Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999 : 44-55

BIBTEX

@inproceedings{DBLP:conf/sigmod/MamoulisP99,
  author    = {Nikos Mamoulis and
                Dimitris Papadias},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Integration of Spatial Join Algorithms for Processing Multiple
                Inputs},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {1-12},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM