Efficient parallel spatial skyline evaluation using MapReduce

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

研究成果: 書貢獻/報告類型會議論文篇章同行評審

14 引文 斯高帕斯(Scopus)

摘要

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.

原文???core.languages.en_GB???
主出版物標題Advances in Database Technology - EDBT 2017
主出版物子標題20th International Conference on Extending Database Technology, Proceedings
編輯Bernhard Mitschang, Volker Markl, Sebastian Bress, Periklis Andritsos, Kai-Uwe Sattler, Salvatore Orlando
發行者OpenProceedings.org
頁面426-437
頁數12
ISBN(電子)9783893180738
DOIs
出版狀態已出版 - 2017
事件20th International Conference on Extending Database Technology, EDBT 2017 - Venice, Italy
持續時間: 21 3月 201724 3月 2017

出版系列

名字Advances in Database Technology - EDBT
2017-March
ISSN(電子)2367-2005

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???20th International Conference on Extending Database Technology, EDBT 2017
國家/地區Italy
城市Venice
期間21/03/1724/03/17

指紋

深入研究「Efficient parallel spatial skyline evaluation using MapReduce」主題。共同形成了獨特的指紋。

引用此