Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations.

@inproceedings{DBLP:conf/vldb/HuangJR97,
  author    = {Yun-Wu Huang and
               Ning Jing and
               Elke A. Rundensteiner},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Spatial Joins Using R-trees: Breadth-First Traversal with Global
               Optimizations},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {396-405},
  ee        = {db/conf/vldb/HuangJR97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1997 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Electronic Edition

• Postscript file, via HTTP
• Postscript file, via FTP

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]

Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX

[6]

Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 BibTeX

[7]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[8]

...

[9]

Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486 BibTeX

[10]

Yun-Wu Huang, Matthew C. Jones, Elke A. Rundensteiner: Improving Spatial Intersect Joins Using Symbolic Intersect Detection. SSD 1997: 165-177 BibTeX

[11]

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 BibTeX

[12]

Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258 BibTeX

[13]

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

[14]

Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX

[15]

Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270 BibTeX

[16]

Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 BibTeX

[17]

...

[18]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

Referenced by

1. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter: A Unified Approach for Indexed and Non-Indexed Spatial Joins. EDBT 2000: 413-429
2. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
3. Kothuri Venkata Ravi Kanth, Siva Ravada, Jayant Sharma, Jay Banerjee: Indexing Medium-dimensionality Data in Oracle. SIGMOD Conference 1999: 521-522
4. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
5. Hongjun Zhu, Jianwen Su, Oscar H. Ibarra: An Index Structure for Spatial Joins in Linear Constraint Databases. ICDE 1999: 636-643
6. Ho-Hyun Park, Chan-Gun Lee, Yong-Ju Lee, Chin-Wan Chung: Early Separation of Filter and Refinement Steps in Spatial Query Optimization. DASFAA 1999: 161-168
7. Geraldo Zimbrao, Jano Moreira de Souza: A Raster Approximation For Processing of Spatial Joins. VLDB 1998: 558-569
8. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
9. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
10. Gísli R. Hjaltason, Hanan Samet: Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998: 237-248
11. 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