Efficient Parallel Spatial Skyline Evaluation Using MapReduce
Efficient Parallel Spatial Skyline Evaluation Using MapReduce
复制标题
DOI：
10.5441/002/edbt.2017.38
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Wenlu Wang;Ji Zhang;Min-Te Sun;Wei-Shinn Ku
中科院分区：
文献类型：
--
作者：
Wenlu Wang;Ji Zhang;Min-Te Sun;Wei-Shinn Ku
这项研究提出了一种先进的基于 MapReduce 的并行解决方案，可以有效地解决大型数据集上的空间天际线查询。特别是，给定一组数据点和一组查询点，我们首先在第一个 MapReduce 阶段生成查询点的凸包。然后，我们提出了一个称为独立区域的新概念，用于并行空间天际线评估过程。独立区域中的候选空间天际线不依赖于其他独立区域中的任何数据点。因此，我们在第二阶段根据输入数据点和查询点的凸包计算独立区域。对于独立区域，在第三阶段并行评估空间天际线，其中数据点由映射函数中关联的独立区域划分，并通过reduce函数计算候选空间天际线。空间天际线查询的结果是来自reduce 函数的输出的并集。由于空间优势测试的成本很高，需要比较数据点到所有凸点的距离，我们提出了在独立区域中剪枝区域的概念。剪枝区域中的所有数据点都可以被丢弃，而无需进行显性测试。我们的实验结果表明了所提出的并行空间天际线解决方案在大规模现实世界和合成数据集上利用 MapReduce 的效率和有效性。
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.