Efficient parallel spatial skyline evaluation using MapReduce

Wenlu Wang, Ji Zhang, Min Te Sun, Wei Shinn Ku

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Scopus citations

Abstract

This research presents an advanced MapReduce-based parallel solution to efficiently address spatial skyline queries on large datasets. In particular, given a set of data points and a set of query points, we first generate the convex hull of the query points in the first MapReduce phase. Then, we propose a novel concept called independent regions, for parallelizing the process of spatial skyline evaluation. Spatial skyline candidates in an independent region do not depend on any data point in other independent regions. Thus, we calculate the independent regions based on the input data points and the convex hull of the query points in the second phase. With the independent regions, spatial skylines are evaluated in parallel in the third phase, in which data points are partitioned by their associated independent regions in the map functions, and spatial skyline candidates are calculated by reduce functions. The results of the spatial skyline queries are the union of outputs from the reduce functions. Due to high cost of the spatial dominance test, which requires comparing the distance from data points to all convex points, we propose a concept of pruning regions in independent regions. All data points in pruning regions can be discarded without the dominance test. Our experimental results show the efficiency and effectiveness of the proposed parallel spatial skyline solution utilizing MapReduce on large-scale real-world and synthetic datasets.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2017
Subtitle of host publication20th International Conference on Extending Database Technology, Proceedings
EditorsBernhard Mitschang, Volker Markl, Sebastian Bress, Periklis Andritsos, Kai-Uwe Sattler, Salvatore Orlando
PublisherOpenProceedings.org
Pages426-437
Number of pages12
ISBN (Electronic)9783893180738
DOIs
StatePublished - 2017
Event20th International Conference on Extending Database Technology, EDBT 2017 - Venice, Italy
Duration: 21 Mar 201724 Mar 2017

Publication series

NameAdvances in Database Technology - EDBT
Volume2017-March
ISSN (Electronic)2367-2005

Conference

Conference20th International Conference on Extending Database Technology, EDBT 2017
Country/TerritoryItaly
CityVenice
Period21/03/1724/03/17

Keywords

  • MapReduce
  • Parallel computation
  • Spatial skyline query

Fingerprint

Dive into the research topics of 'Efficient parallel spatial skyline evaluation using MapReduce'. Together they form a unique fingerprint.

Cite this