article

Free access

Size separation spatial join

Authors:

Kenneth C. SevcikAuthors Info & Claims

ACM SIGMOD Record, Volume 26, Issue 2

Pages 324 - 335

https://doi.org/10.1145/253262.253340

Published: 01 June 1997 Publication History

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 (S³J) 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 S³J 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 S³J has relatively simple cost estimation formulas that can be exploited by a query optimizer. S³J 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 S³J to dynamically or statically exploit bitmap query processing techniques.

Finally, we present experimental results for a prototype implementation of S³J 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 S³J over alternative approaches that have been proposed recently.

References

[1]

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.

Digital Library

[2]

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.

Digital Library

[3]

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.

Digital Library

[4]

Bureau of the Census. TIGER/Line Census Files. March 1991.

[5]

A. Guttman. R-trees : A Dynamic Index Structure for Spatial Searching. Proceedings of A CM SIG- MOD, pages 47-57, June 1984.

Digital Library

[6]

Nick Koudas and Kenneth C. Sevcik. Size Separation Spatial Join. Computer Systems Research Institute, CSRI-TR-352. University o} Toronto, October 1996.

[7]

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.

Digital Library

[8]

Ming-Ling Lo and Chinya V. Ravishankar. Spatial hash-joins. Proceedings of A CM SIGMOD, pages 247-258, June 1996.

Digital Library

[9]

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.

Digital Library

[10]

P. O'Neil and G. Graefe. Multi-Table Joins Through Bitmapped Join Indeces. SIGMOD Record Vol. 24, No. 3, pages 8-11, September 1995.

Digital Library

[11]

P. O'Neil. Query Performance. Talk Delivered at IBM Toronto, March 1996.

[12]

J. Orenstein. Spatial Query Processing in an Object-Oriented Database System. Procedings o.f A CM SIGMOD, pages 326-336, May 1986.

Digital Library

[13]

Jignesh M. Patel and David J. DeWitt. Partition Based Spatial-Merge Join. Proceedings o} A CM SIGMOD, pages 259-270, June 1996.

Digital Library

[14]

Doron Rotem. Spatial Join Indices. Proceedings of the International Conference on Data Engineering, pages 500-509, March 1993.

Digital Library

[15]

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.

Digital Library

[16]

M. Stonebraker and D. Moore. Object Relational Databases: The Next Wave. Morgan Kauffman, June 1996.

Digital Library

[17]

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.

Digital Library

[18]

P. Valduriez. Join Indexes. A CM TODS, Volume 12, No 2, pages 218-246, June 1987.

Digital Library

Cited By

Lee CKang DSong H(2024)Fast Knowledge Graph Completion using Graphics Processing UnitsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104885(104885)Online publication date: Mar-2024
https://doi.org/10.1016/j.jpdc.2024.104885
Li TXu J(2023)Block-Join: A Partition-Based Method for Processing Spatio-Temporal JoinsWeb and Big Data10.1007/978-3-031-25201-3_30(397-411)Online publication date: 10-Feb-2023
https://doi.org/10.1007/978-3-031-25201-3_30
Singla SEldawy ADiao TMukhopadhyay AScudiero E(2021)Experimental Study of Big Raster and Vector Database Systems2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00231(2243-2248)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00231
Show More Cited By

Index Terms

Size separation spatial join
1. Information systems
  1. Data management systems
    1. Database design and models
2. Mathematics of computing
  1. Mathematical software

Recommendations

Size separation spatial join
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data

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 (S³J) 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 26, Issue 2

June 1997

583 pages

ISSN:0163-5808

DOI:10.1145/253262

Chairman:
Sudha Ram
Univ. of Arizona, Tucson
,
Editor:
Joan M. Peckham
Univ. of Rhode Island, Kingston

Issue’s Table of Contents

SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data
June 1997
594 pages
ISBN:0897919114
DOI:10.1145/253260
Editors:
Joan M. Peckman
Univ. of Rhode Island, Kingston
,
Sudha Ram
Univ. of Arizona, Tucson
,
Michael Franklin

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1997

Published in SIGMOD Volume 26, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

117
Total Citations
View Citations
740
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)16

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee CKang DSong H(2024)Fast Knowledge Graph Completion using Graphics Processing UnitsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104885(104885)Online publication date: Mar-2024
https://doi.org/10.1016/j.jpdc.2024.104885
Li TXu J(2023)Block-Join: A Partition-Based Method for Processing Spatio-Temporal JoinsWeb and Big Data10.1007/978-3-031-25201-3_30(397-411)Online publication date: 10-Feb-2023
https://doi.org/10.1007/978-3-031-25201-3_30
Singla SEldawy ADiao TMukhopadhyay AScudiero E(2021)Experimental Study of Big Raster and Vector Database Systems2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00231(2243-2248)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00231
Bouros PMamoulis N(2019)Spatial joinsSIGSPATIAL Special10.1145/3355491.335549411:1(13-21)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3355491.3355494
Amagata DHara T(2019)Identifying the Most Interactive Object in Spatial Databases2019 IEEE 35th International Conference on Data Engineering (ICDE)10.1109/ICDE.2019.00117(1286-1297)Online publication date: Apr-2019
https://doi.org/10.1109/ICDE.2019.00117
LE HTAKASU A(2018)G-HBase: A High Performance Geographical Database Based on HBaseIEICE Transactions on Information and Systems10.1587/transinf.2017DAP0017E101.D:4(1053-1065)Online publication date: 2018
https://doi.org/10.1587/transinf.2017DAP0017
Luo JShi SYang GWang HLi J(2018)O2iJoin: An Efficient Index-Based Algorithm for Overlap Interval JoinJournal of Computer Science and Technology10.1007/s11390-018-1872-x33:5(1023-1038)Online publication date: 12-Sep-2018
https://doi.org/10.1007/s11390-018-1872-x
Mamoulis N(2018)Spatial JoinEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_356(3598-3606)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_356
Mamoulis N(2017)Spatial JoinEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_356-2(1-9)Online publication date: 13-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_356-2
Zhang RQi JStradling MHuang J(2014)Towards a Painless Index for Spatial ObjectsACM Transactions on Database Systems10.1145/262933339:3(1-42)Online publication date: 7-Oct-2014
https://dl.acm.org/doi/10.1145/2629333
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents