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

Efficient Processing of Spatial Joins Using R-Trees.

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
@inproceedings{DBLP:conf/sigmod/BrinkhoffKS93,
  author    = {Thomas Brinkhoff and
               Hans-Peter Kriegel and
               Bernhard Seeger},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Efficient Processing of Spatial Joins Using R-Trees},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {237-246},
  ee        = {http://doi.acm.org/10.1145/170035.170075, db/conf/sigmod/BrinkhoffKS93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Spatial joins are one of the most important operations for combining spatial objects of several relations. The efficient processing of a spatial join is extremely important since its execution time is super-linear in the number of spatial objects of the participating relations, and this number of objects may be very high. In this paper, we present a first detailed study of spatial join processing using R-trees, particularly R*-trees. R-trees are very suitable for supporting spatial queries and the R*-tree is one of the most efficient members of the R-tree family. Starting from a straightforward approach, we present several techniques for improving its execution time with respect to both, CPU- and I/O-time. Eventually, we end up with an algorithm whose total execution time is improved over the first approach by an order of magnitude. Using a buffer of reasonable size, I/O-time is almost optimal, i.e. it almost corresponds to the time for reading each required page of the relations exactly once. The performance of the various approaches is investigated in an experimental performance comparison where several large data sets from real applications are used.

Copyright © 1993 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

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

References

[1]
...
[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]
...
[4]
...
[5]
...
[6]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
[7]
Farshad Fotouhi, Sakti Pramanik: Optimal Secondary Storage Access Sequence for Performing Relational Join. IEEE Trans. Knowl. Data Eng. 1(3): 318-328(1989) BibTeX
[8]
Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982) BibTeX
[9]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 BibTeX
[10]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[11]
Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70 BibTeX
[12]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 BibTeX
[13]
...
[14]
Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204 BibTeX
[15]
Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992) BibTeX
[16]
T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498 BibTeX
[17]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[18]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[19]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
[20]
...
[21]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 BibTeX
[22]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX
[23]
Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990) BibTeX
[24]
...

Referenced by

  1. Timos K. Sellis: Review - Efficient Processing of Spatial Joins Using R-Trees. ACM SIGMOD Digital Review 2: (2000)
  2. Hyoseop Shin, Bongki Moon, Sukho Lee: Adaptive Multi-Stage Distance Join Processing. SIGMOD Conference 2000: 343-354
  3. Flip Korn, S. Muthukrishnan: Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD Conference 2000: 201-212
  4. Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.: Spatial Join Selectivity Using Power Laws. SIGMOD Conference 2000: 177-188
  5. Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, Michael Vassilakopoulos: Closest Pair Queries in Spatial Databases. SIGMOD Conference 2000: 189-200
  6. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
  7. 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
  8. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  9. Kothuri Venkata Ravi Kanth, Siva Ravada, Jayant Sharma, Jay Banerjee: Indexing Medium-dimensionality Data in Oracle. SIGMOD Conference 1999: 521-522
  10. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
  11. Hongjun Zhu, Jianwen Su, Oscar H. Ibarra: An Index Structure for Spatial Joins in Linear Constraint Databases. ICDE 1999: 636-643
  12. 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
  13. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  14. Ming-Ling Lo, Chinya V. Ravishankar: The Design and Implementation of Seeded Trees: An Efficient Method for Spatial Joins. IEEE Trans. Knowl. Data Eng. 10(1): 136-152(1998)
  15. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  16. Geraldo Zimbrao, Jano Moreira de Souza: A Raster Approximation For Processing of Spatial Joins. VLDB 1998: 558-569
  17. Dimitris Papadias, Nikos Mamoulis, Vasilis Delis: Algorithms for Querying by Spatial Structure. VLDB 1998: 546-557
  18. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
  19. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  20. Oliver Günther, Vincent Oria, Philippe Picouet, Jean-Marc Saglio, Michel Scholl: Benchmarking Spatial Joins À La Carte. SSDBM 1998: 32-41
  21. Gísli R. Hjaltason, Hanan Samet: Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998: 237-248
  22. Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis: Cost Models for Join Queries in Spatial Databases. ICDE 1998: 476-483
  23. Nick Koudas, Kenneth C. Sevcik: High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998: 466-475
  24. Hiroyuki Horinokuchi, Botao Wang, Susumu Kuroki, Akifumi Makinouchi: A Spatiotemporal Query Processor Based on Simplicial Representation. ER Workshops 1998: 520-531
  25. John C. Shafer, Rakesh Agrawal: Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications. VLDB 1997: 176-185
  26. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405
  27. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
  28. 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
  29. Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335
  30. Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408
  31. Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486
  32. Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27
  33. Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
  34. Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258
  35. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265
  36. Nick Koudas, Christos Faloutsos, Ibrahim Kamel: Declustering Spatial Databases on a Multi-Computer Architecture. EDBT 1996: 592-614
  37. Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618
  38. Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, Kyuseok Shim: Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases. VLDB 1995: 490-501
  39. Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79
  40. Christos Faloutsos, King-Ip Lin: FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets. SIGMOD Conference 1995: 163-174
  41. M. G. Martynov: Spatial Joins and R-trees. ADBIS 1995: 295-304
  42. King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB J. 3(4): 517-542(1994)
  43. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
  44. Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155
  45. Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167
  46. Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179
  47. Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220
  48. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: GENESYS: A System for Efficient Spatial Query Processing. SIGMOD Conference 1994: 519
  49. Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208
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:40:15 2009