Abstract
We introduce a new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them. Size Separation Spatial Join (S3J) imposes a hierarchical decomposition of the data space and, in contrast with previous approaches, requires no replication of entities from the input data sets. Thus its execution time depends only on the sizes of the joined data sets.
We describe S3J and present an analytical evaluation of its I/O and processor requirements comparing them with those of previously proposed algorithms for the same problem. We show that S3J has relatively simple cost estimation formulas that can be exploited by a query optimizer. S3J can be efficiently implemented using software already present in many relational systems. In addition, we introduce Dynamic Spatial Bitmaps (DSB), a new technique that enables S3J to dynamically or statically exploit bitmap query processing techniques.
Finally, we present experimental results for a prototype implementation of S3J involving real and synthetic data sets for a variety of data distributions. Our experimental results are consistent with our analytical observations and demonstrate the performance benefits of S3J over alternative approaches that have been proposed recently.
- Bia69 T. Bially. Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Trans. on Information Theory, IT-15(6):658- 664, November 1969.Google ScholarDigital Library
- BKS93 Thomas Brinkhoff, Hans-Peter Kriegel, and Bernhard Seeger. Efficient Processing of Spatial Joins using R-trees. Proceedings of A CM SIGMOD, pages 237-246, May 1993. Google ScholarDigital Library
- BKSS94 Thomas Brinkhoff, H.P Kriegel, Rail Schneider, and Bernhard Seeger. Multistep Processing of Spatial Joins. Proceedings o} A CM SIGMOD, pages 189-208, May 1994. Google ScholarDigital Library
- Bur91 Bureau of the Census. TIGER/Line Census Files. March 1991.Google Scholar
- Gut84 A. Guttman. R-trees : A Dynamic Index Structure for Spatial Searching. Proceedings of A CM SIG- MOD, pages 47-57, June 1984. Google ScholarDigital Library
- KS96 Nick Koudas and Kenneth C. Sevcik. Size Separation Spatial Join. Computer Systems Research Institute, CSRI-TR-352. University o} Toronto, October 1996.Google Scholar
- LR95 Ming-Ling Lo and Chinya V. Ravishankar. Generating Seeded Trees from Spatial Data Sets. Symposium on Large Spatial Data Bases, pages 328-347, August 1995. Google ScholarDigital Library
- LR96 Ming-Ling Lo and Chinya V. Ravishankar. Spatial hash-joins. Proceedings of A CM SIGMOD, pages 247-258, June 1996. Google ScholarDigital Library
- NHS84 J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The Grid File: An Adaptable, Symmetric Multikey File Structure. A CM TODS 1984, pages 38-71, May 1984. Google ScholarDigital Library
- OG95 P. O'Neil and G. Graefe. Multi-Table Joins Through Bitmapped Join Indeces. SIGMOD Record Vol. 24, No. 3, pages 8-11, September 1995. Google ScholarDigital Library
- O'N96 P. O'Neil. Query Performance. Talk Delivered at IBM Toronto, March 1996.Google Scholar
- Ore86 J. Orenstein. Spatial Query Processing in an Object-Oriented Database System. Procedings o.f A CM SIGMOD, pages 326-336, May 1986. Google ScholarDigital Library
- PD96 Jignesh M. Patel and David J. DeWitt. Partition Based Spatial-Merge Join. Proceedings o} A CM SIGMOD, pages 259-270, June 1996. Google ScholarDigital Library
- Rot93 Doron Rotem. Spatial Join Indices. Proceedings of the International Conference on Data Engineering, pages 500-509, March 1993. Google ScholarDigital Library
- SK96 Kenneth C. Sevcik and Nick Koudas. Filter Trees for Managing Spatial Data Over a Range of Size Granularities. Proceedings o} VLDB, pages 16-27, September 1996. Google ScholarDigital Library
- SM96 M. Stonebraker and D. Moore. Object Relational Databases: The Next Wave. Morgan Kauffman, June 1996. Google ScholarDigital Library
- SRF87 Timos Seilis, Nick Roussopoulos, and Christos Faloutsos. The R+-tree : A Dynamic Index for Multi-dimensional Data. Proceedings of VLDB 1987, pages 507-518, September 1987. Google ScholarDigital Library
- Val87 P. Valduriez. Join Indexes. A CM TODS, Volume 12, No 2, pages 218-246, June 1987. Google ScholarDigital Library
Index Terms
- Size separation spatial join
Recommendations
Size separation spatial join
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of dataWe introduce a new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them. Size Separation Spatial Join (S3J) imposes a hierarchical decomposition of the data space and, in contrast with previous ...
Multi-way spatial join selectivity for the ring join graph
Efficient spatial query processing is very important since the applications of the spatial DBMS (e.g. GIS, CAD/CAM, LBS) handle massive amount of data and consume much time. Many spatial queries contain the multi-way spatial join due to the fact that ...
Iterative spatial join
The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can ...
Comments