On Spatial Joins in MapReduce

Ibrahim Sabek, Mohamed F Mokbel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

This paper provides the first attempt for a full-fledged query optimizer for MapReduce-based spatial join algorithms. The optimizer develops its own taxonomy that covers almost all possible ways of doing a spatial join for any two input datasets. The optimizer comes in two flavors; cost-based and rule-based. Given two input data sets, the cost-based query optimizer evaluates the costs of all possible options in the developed taxonomy, and selects the one with the lowest cost. The rule-based query optimizer abstracts the developed cost models of the cost-based optimizer into a set of simple easy-to-check heuristic rules. Then, it applies its rules to select the lowest cost option. Both query optimizers are deployed and experimentally evaluated inside a widely used open-source MapReduce-based big spatial data system. Exhaustive experiments show that both query optimizers are always successful in taking the right decision for spatially joining any two datasets of up to 500GB each.

Original languageEnglish (US)
Title of host publicationGIS
Subtitle of host publicationProceedings of the ACM International Symposium on Advances in Geographic Information Systems
EditorsSiva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski
PublisherAssociation for Computing Machinery
ISBN (Print)9781450354905
DOIs
StatePublished - Nov 7 2017
Event25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2017 - Redondo Beach, United States
Duration: Nov 7 2017Nov 10 2017

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Volume2017-November

Other

Other25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2017
Country/TerritoryUnited States
CityRedondo Beach
Period11/7/1711/10/17

Bibliographical note

Funding Information:
1This work is partially supported by the National Science Foundation, USA, under Grants IIS-1525953, CNS-1512877, IIS-1218168.

Publisher Copyright:
2017 Association for Computing Machinery.

Keywords

  • Hadoop
  • MapReduce
  • Query Optimization
  • Spatial Join

Fingerprint

Dive into the research topics of 'On Spatial Joins in MapReduce'. Together they form a unique fingerprint.

Cite this