More Web Proxy on the site http://driver.im/

article

Free access

Partition based spatial-merge join

Authors:

Jignesh M. Patel,

David J. DeWittAuthors Info & Claims

ACM SIGMOD Record, Volume 25, Issue 2

Pages 259 - 270

https://doi.org/10.1145/235968.233338

Published: 01 June 1996 Publication History

Abstract

This paper describes PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation. This algorithm is especially effective when neither of the inputs to the join have an index on the joining attribute. Such a situation could arise if both inputs to the join are intermediate results in a complex query, or in a parallel environment where the inputs must be dynamically redistributed. The PBSM algorithm partitions the inputs into manageable chunks, and joins them using a computational geometry based plane-sweeping technique. This paper also presents a performance study comparing the the traditional indexed nested loops join algorithm, a spatial join algorithm based on joining spatial indices, and the PBSM algorithm. These comparisons are based on complete implementations of these algorithms in Paradise, a database system for handling GIS applications. Using real data sets, the performance study examines the behavior of these spatial join algorithms in a variety of situations, including the cases when both, one, or none of the inputs to the join have an suitable index. The study also examines the effect of clustering the join inputs on the performance of these join algorithms. The performance comparisons demonstrates the feasibility, and applicability of the PBSM join algorithm.

References

[1]

ESRI, Redlands, CA. "ARC/INFO: The World's GIS. An ESRI White Paper", March 1995.

[2]

J. L. Bentley. "Multidimensional Binary Search Trees Used for Associative Searching". In Communication ofthe A CM, volume 18(9), September 1975.

Digital Library

[3]

J. L. Bentley. "Multidlmensionat Binary Search Trees in Database Applications". In IEEE Trat~sactions on Software Engineering, volume 5(4), 1979.

[4]

L. Becker, K. Hinnchs, and U. Finke. "'A New Algorithm for Computing Joans With Grid Files". In IEEE Transactions on Knowledge and Dam Engineering, 1993.

Digital Library

[5]

T. Brinkhoff, H. P. Kriegel, and B. Seeger. "Efficient Processing of Spatial Joins Using R-trees". In Proceedings of the 1993 A CM-SIGMOD Conference, Washington, DC, May 1993.

Digital Library

[6]

N. Beckmann, H. R Kriegel, R. Schneider, and B. Seeger. "'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles". in Proceedbtgs of the 1990 A CM-SIGMOD Conference, June 1990.

Digital Library

[7]

T. Brinkhoff, H. R Kriegel, R. Schneider, and B. Seeger. "'Multi-step Processing of Spatial Joins". In Proceedings of the 1994 A CM-SIGMOD Colference, Minneapolis, May 1994.

Digital Library

[8]

R A. Burrough. "Principles of Geographic hzformation Systems for Land Resources Assessment". Oxford University Press, 1986.

[9]

M. J. Carey, D. J. DeWitt, M. J. Franklin, N. E. Hail, M. McAuliffe, J. F. Naughton, D. T. Schuh, M. H. Solomon, C. K. Tan, O. Tsatatos, S. White, and M. J. Zwilling. "Shoring up Persistent Applications". In P~vceedings of the 1994 ACM- SIGMOD Conference, "Minneapolis, Minnesota", May 1994.

Digital Library

[10]

T. Sellis C. Faloutsos and N. Roussopoulos. "Analysis of Object Oriented Spatial Access Methods". In Proceedings of the 1987 A CM-SIGMOD Conferelzce, San Francisco, May 1987.

Digital Library

[11]

Intergraph Corporation. "GIS/AM/FM Information". "http://wwm intergraph'c~m/utihnap'shtmt ", 1995.

[12]

D. J. DeWitt, N. Kabra, J. Luo, J. M. Patel, and J, Yu. "Claent-Server Paradise". In Proceedings of the 20th VLDB Colf, Santiago, Chile, September 1994.

Digital Library

[13]

D. J. DeWitt, J. Luo, J. M. PateI, and J. Yu. "Paradise -A Parallel Geographic Information System". In Proceedings of the A CM Workshop on Advance~ in Geographic Information Systems, Arlington, Virginia, November 1993.

[14]

D. J. DeWitt, J. R Naughton, D. A. Schneider, and S. Seshadri. "'Practical Skew Handling in Parallel Joins". In Proceedbzgs of the 19th VLDB Coil, August 1992.

Digital Library

[15]

R. H. Gtiting and W. Shilling. "A Practical Diwde-and- Conquer Algorithm for the Rectangle Intersection Problem". In bzformation Sciences, volume 42, 1987.

Digital Library

[16]

O. G~nther. "Efficient Computation of Spatial Joins". In IEEE Transactions on Knowledge and Data E1zgineering, 1993.

Digital Library

[17]

A. Gutman. "R-trees: A Dynamic Index Structure for Spatial Searching". In Proceedings of the 1984 A CM-SIGMOD Conference, Boston, Mass, June 1984.

Digital Library

[18]

L. Harada, M. Nakano, M. Kitsuregawa, and M. Takagi. "Query Processing Methods for Multi-Attribute Clustered Relations". In Proceedings of the 16th VLDB Conf, Brisbane, Australia, 1990.

Digital Library

[19]

E. G. Hoel and H. Samet. "Benchmarking Spatial Join Operations with Spatial Output". In Proceedings of the 21st VLDB Conf., Zurich, Switzerland, September 1995.

Digital Library

[20]

M. Kitsuregawa, L. Harada, and M. Takagi. ~'Join Strategies on KD-Tree Indexed Relations". In IEEE Transactions on Knowledge and Data Engineering, 1989.

Digital Library

[21]

M. L. Lo and C. V. Ravishankar. "Spatial Joins Using Seeded Trees". In Proceedings of the 1994 A CM-SIGMOD Conference, Minneapolis, May 1994.

Digital Library

[22]

M.L. Lo and C. V. Ravishankar. "Generating Seeded Trees From Data Sets". In Proceedings of the Fourth International Symposium on Large Spatial Databases, Portland, ME, August 1995.

Digital Library

[23]

M.L. Lo and C. V. Ravishankar. "Spatial Hash-Joins". In Proceedings of the 1996 A CM-SIGMOD Conference, Montreal, Canada, June 1996.

Digital Library

[24]

C. Mead and L. Conway. "bTtroduction to VLSI Systems". Addison-Wesley, Reading, Mass., 1980.

Digital Library

[25]

D.J. Maguire, M. E Goodchild, and D. W. Rhind. "Geographic h~formation Systems" volume 1. Longman Scientific & Technical, copublishect in the US with John Wiley & Sons, Inc. New York, 1991.

[26]

J. Nievergelt, H. Hinterberger, and K. C. Sevcik. "The Grid File: An Adaptable, Symmetric Multikey File Structure". A CM Tra~zsactions on Database Systems, March 1984.

Digital Library

[27]

R. C. Nelson and H. Samet. "A Consistent Hierarchical Representation for Vector Data". In Computer Graphics, volume 20(4), August 1986.

Digital Library

[28]

J. A. Orenstein and T. H. Merrett. "A Class of Data Structures for Associative Searching". In Proceedings of the 3rd A CM SIGA CT-SIGMOD Symposium on Principles of Database Systems, 1984.

Digital Library

[29]

J. A. Orenstein and F. A. Manola. "PROBE Spatial Data Modeling and Query Processing in an Image Database Application". In IEEE Transactions on Software Engineering, volume 14(5), May I988.

Digital Library

[30]

J, A. Orenstein. "Spatial Query Processing in an Object- Oriented Database System". In Proceedings of the I986 ACM- SIGMOD Conference, 1986.

Digital Library

[31]

J. A. Orenstein. "'Redundancy in Spatml Databases". In Proceedings of the 1989 A CM-SIGMOD Conference, 1989.

Digital Library

[32]

J. A. Orenstein. "A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces". In Proceedings of the 1990 ACM-SIGMOD Colference, 1990.

Digital Library

[33]

J. M. Patel and D. J. DeWitt. "Partition Based Spatial-Merge Join". http://www.cs.wisc.edu/paradise/paradise.papers.html.

Digital Library

[34]

F. R Preparata and M. I. Shamos, editors. "Computational Geometry" Springer, 1988.

Digital Library

[35]

D. Rotem. "Spatial Join Indices". in IEEE Transactions on Knowledge and Data Engineering, Kobe, April 1991.

[36]

M. Stonebraker, J. Frew, K. Gardels, and J. Meredith. "The SEQUOIA 2000 Storage Benchmark". In Proceedings of the 1993 ACM-SIGMOD Conference, Washington, D.C., May 1993.

Digital Library

[37]

M. Stonebraker. "The Case for Shared Nothing". Database Engineering, 9( 1 ), 1986.

[38]

U.S. Bureau of the Census, Washington, DC. "TIGER~Line Files(TM). 1992 Technical Documentation".

[39]

K L. Tan and J. X. Yu. "A Performance Study of Declusterlng Strategies for Parallel Spatial Databases". In The 6th hzternational Conference on Database and Expert Systems Applications (DEXA), London, United Kingdom, September 1995.

Digital Library

[40]

M. Ubell. "The Montage Extensible DataBlade Architecture". In Proceedings of the 1994 A CM-SIGMOD Conference, May 1994.

Digital Library

[41]

R Valduriez. "'Join Indices". InACMTODS, volume t2(2), 1987.

Digital Library

[42]

H. Zeller and J. Gray. "An Adaptive Hash Join Algorithm for Multiuser Environments". In Proceedings of the 16th VLDB Co~, Brisbane, Australia, 1990.

Digital Library

Cited By

Belussi AMigliorini SEldawy A(2024)A Generic Machine Learning Model for Spatial Query Optimization based on Spatial EmbeddingsACM Transactions on Spatial Algorithms and Systems10.1145/365763310:4(1-33)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3657633
Gao FLu WGan LXu C(2024)A ConvNets-based approach for capturing the heterogeneity of spatial domain in parallel geoprocessingInternational Journal of Digital Earth10.1080/17538947.2024.239806617:1Online publication date: 4-Sep-2024
https://doi.org/10.1080/17538947.2024.2398066
Papamichalopoulos MPapadakis GMandilaras GSiampou MMamoulis NKoubarakis M(2024)Three-dimensional Geospatial Interlinking with JedAI-spatialJournal of Web Semantics10.1016/j.websem.2024.100817(100817)Online publication date: Mar-2024
https://doi.org/10.1016/j.websem.2024.100817
Show More Cited By

Index Terms

Partition based spatial-merge join
1. Information systems
  1. Data management systems
    1. Database design and models
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Partition based spatial-merge join
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

This paper describes PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation. This algorithm is especially effective when neither of the inputs to the join have an index on the joining attribute. Such a situation ...
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 ...
The Sort-Merge-Shrink join

One of the most common operations in analytic query processing is the application of an aggregate function to the result of a relational join. We describe an algorithm called the Sort-Merge-Shrink (SMS) Join for computing the answer to such a query over ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 25, Issue 2

June 1996

557 pages

ISSN:0163-5808

DOI:10.1145/235968

Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick

Issue’s Table of Contents

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data
June 1996
560 pages
ISBN:0897917944
DOI:10.1145/233269
Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

Copyright © 1996 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 1996

Published in SIGMOD Volume 25, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

339
Total Citations
View Citations
1,622
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)29

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Belussi AMigliorini SEldawy A(2024)A Generic Machine Learning Model for Spatial Query Optimization based on Spatial EmbeddingsACM Transactions on Spatial Algorithms and Systems10.1145/365763310:4(1-33)Online publication date: 13-Apr-2024
https://dl.acm.org/doi/10.1145/3657633
Gao FLu WGan LXu C(2024)A ConvNets-based approach for capturing the heterogeneity of spatial domain in parallel geoprocessingInternational Journal of Digital Earth10.1080/17538947.2024.239806617:1Online publication date: 4-Sep-2024
https://doi.org/10.1080/17538947.2024.2398066
Papamichalopoulos MPapadakis GMandilaras GSiampou MMamoulis NKoubarakis M(2024)Three-dimensional Geospatial Interlinking with JedAI-spatialJournal of Web Semantics10.1016/j.websem.2024.100817(100817)Online publication date: Mar-2024
https://doi.org/10.1016/j.websem.2024.100817
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
Vu TBelussi AMigliorini SEldawy A(2024)A learning-based framework for spatial join processing: estimation, optimization and tuningThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00836-133:4(1155-1177)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00778-024-00836-1
Jin PWang XXiong WWang LGao S(2024)Extracting Spatial High Utility Co-location Patterns Based on Fuzzy Feature ClustersBig Data and Social Computing10.1007/978-981-97-5803-6_13(217-236)Online publication date: 1-Aug-2024
https://doi.org/10.1007/978-981-97-5803-6_13
Guermoudi NMatallah HMesmoudi ABenkabou SHadjali A(2024)Selectivity Estimation for Spatial Filters Using Optimizer Feedback: A Machine Learning PerspectiveWeb Information Systems Engineering – WISE 202410.1007/978-981-96-0573-6_8(101-115)Online publication date: 27-Nov-2024
https://doi.org/10.1007/978-981-96-0573-6_8
Zhang XEldawy A(2023)Less is More: How Fewer Results Improve Progressive Join Query ProcessingProceedings of the 35th International Conference on Scientific and Statistical Database Management10.1145/3603719.3603728(1-12)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3603719.3603728
Lee JShim CNguyen HNguyen TChoi HKim Y(2023)Label Space Partition Selection for Multi-Object Tracking Using Two-Layer Partitioning2023 12th International Conference on Control, Automation and Information Sciences (ICCAIS)10.1109/ICCAIS59597.2023.10382268(121-126)Online publication date: 27-Nov-2023
https://doi.org/10.1109/ICCAIS59597.2023.10382268
Shehab AElashry AAboul-Fotouh ARiad A(2023)An Enhanced Partitioning Approach in SpatialHadoop for Handling Big Spatial DataInternational Journal of Computational Intelligence Systems10.1007/s44196-023-00188-816:1Online publication date: 15-Feb-2023
https://doi.org/10.1007/s44196-023-00188-8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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