Article

Data-Parallel Spatial Join Algorithms

Authors:

Erik G. Hoel,

Hanan SametAuthors Info & Claims

ICPP '94: Proceedings of the 1994 International Conference on Parallel Processing - Volume 03

Pages 227 - 234

https://doi.org/10.1109/ICPP.1994.82

Published: 15 August 1994 Publication History

Publisher Site

Abstract

Efficient data-parallel spatial join algorithms for bucket PMR quadtrees and R-trees, common spatial data structures, are given. The domain consists of planar line segment data (i.e., Bureau of the Census TIGER/Line files). Parallel algorithms for map intersection and a spatial range query are described. The algorithms are implemented using the scan model of parallel computation on the hypercube architecture of the Connection Machine.

Cited By

View all

Whitman RMarsh BPark MHoel E(2019)Distributed Spatial and Spatio-Temporal Join on Apache SparkACM Transactions on Spatial Algorithms and Systems10.1145/33251355:1(1-28)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/3325135
Whitman RPark MMarsh BHoel E(2017)Spatio-Temporal Join on Apache SparkProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139963(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139963
Ogden PThomas DPietzuch PÖzcan FKoutrika GMadden S(2016)AT-GISProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882962(1041-1054)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882962
Show More Cited By

Data-Parallel Spatial Join Algorithms

Recommendations

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 ...
Integration of spatial join algorithms for processing multiple inputs

Several techniques that compute the join between two spatial datasets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, providing solutions for ...
Parallel Spatial Join Algorithms Using Grid Files
DANTE '99: Proceedings of the 1999 International Symposium on Database Applications in Non-Traditional Environments

The most costly spatial operation in spatial databases is a spatial join, which combines objects from two data sets based on spatial predicates such as, intersects or contains. Even if the execution time of sequential spatial join processing has ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICPP '94: Proceedings of the 1994 International Conference on Parallel Processing - Volume 03

August 1994

297 pages

ISBN:0849324939

Publisher

IEEE Computer Society

United States

Publication History

Published: 15 August 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Whitman RMarsh BPark MHoel E(2019)Distributed Spatial and Spatio-Temporal Join on Apache SparkACM Transactions on Spatial Algorithms and Systems10.1145/33251355:1(1-28)Online publication date: 27-Jun-2019
https://dl.acm.org/doi/10.1145/3325135
Whitman RPark MMarsh BHoel E(2017)Spatio-Temporal Join on Apache SparkProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139963(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139963
Ogden PThomas DPietzuch PÖzcan FKoutrika GMadden S(2016)AT-GISProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882962(1041-1054)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882962
Zhang CLi FJestes J(2012)Efficient parallel kNN joins for large data in MapReduceProceedings of the 15th International Conference on Extending Database Technology10.1145/2247596.2247602(38-49)Online publication date: 27-Mar-2012
https://dl.acm.org/doi/10.1145/2247596.2247602
Jacox ESamet H(2007)Spatial join techniquesACM Transactions on Database Systems10.1145/1206049.120605632:1(7-es)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1145/1206049.1206056
Ferro AGiugno RMongioví MPigola GPulvirenti A(2006)Distributed antipole clustering for efficient data search and management in Euclidean and metric spacesProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899009(76-76)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899009
Hastings SLangella SOster SKurc TPan TCatalyurek UJanies DSaltz JHaddad HOmicini AWainwright R(2005)Grid-based management of biomedical data using an XML-based distributed data management systemProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1066707(105-109)Online publication date: 13-Mar-2005
https://dl.acm.org/doi/10.1145/1066677.1066707
Hjaltason GSamet H(1998)Incremental distance join algorithms for spatial databasesACM SIGMOD Record10.1145/276305.27632627:2(237-248)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1145/276305.276326
Hjaltason GSamet HHaas LDrew P(1998)Incremental distance join algorithms for spatial databasesProceedings of the 1998 ACM SIGMOD international conference on Management of data10.1145/276304.276326(237-248)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1145/276304.276326
Shekhar SRavada SKumar VChubb DTurner G(1998)Declustering and Load-Balancing Methods for Parallelizing Geographic Information SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/69.70606110:4(632-655)Online publication date: 1-Jul-1998
https://dl.acm.org/doi/10.1109/69.706061
Show More Cited By

Abstract

Cited By

Recommendations

Multi-way spatial join selectivity for the ring join graph

Integration of spatial join algorithms for processing multiple inputs

Parallel Spatial Join Algorithms Using Grid Files

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations