A top-k spatial join querying processing algorithm based on spark
A top-k spatial join querying processing algorithm based on spark
复制标题
一种基于spark的top-k空间连接查询处理算法
DOI：
10.1016/j.is.2019.101419
复制
发表时间：
2020
影响因子：
3.7
通讯作者：
Wang Guoren
中科院分区：
文献类型：
--
作者：
Qiao Baiyou;Hu Bing;Zhu Junhai;Wu Gang;Giraud-Carrier Christophe;Wang Guoren
针对云计算系统中top-k空间连接查询处理问题，提出了一种基于Spark的top-k空间连接查询处理算法STKSJ.该算法通过网格划分方法将整个数据空间划分为大小相同的网格单元，并将一个数据集中的每个空间对象投影到一个网格单元中。计算每个网格单元中所有空间对象的最小边界矩形（MBR）。与另一空间数据集中的这些MBR重叠的空间对象被复制到相应的网格单元，从而过滤掉没有连接结果的空间对象，从而降低了后续空间连接处理的成本。提出了一种改进的平面扫描算法，该算法加快了扫描速度并采用了阈值过滤，从而大大降低了后续top-k聚合操作中中间连接结果的通信和计算开销。在合成数据集和真实的数据集上的实验结果表明，该算法具有明显的优势，性能优于现有的top-k空间连接查询处理算法. (C)2019爱思唯尔有限公司版权所有。
Aiming at the problem of top-k spatial join query processing in cloud computing systems, a Spark-based top-k spatial join (STKSJ) query processing algorithm is proposed. In this algorithm, the whole data space is divided into grid cells of the same size by a grid partitioning method, and each spatial object in one data set is projected into a grid cell. The Minimum Bounding Rectangle (MBR) of all spatial objects in each grid cell is computed. The spatial objects overlapping with these MBRs in another spatial data set are replicated to the corresponding grid cells, thereby filtering out spatial objects for which there are no join results, thus reducing the cost of subsequent spatial join processing. An improved plane sweeping algorithm is also proposed that speeds up the scanning mode and applies threshold filtering, thus greatly reducing the communication and computation costs of intermediate join results in subsequent top-k aggregation operations. Experimental results on synthetic and real data sets show that the proposed algorithm has clear advantages, and better performance than existing top-k spatial join query processing algorithms. (C) 2019 Elsevier Ltd. All rights reserved.
登录
查看更多内容
影响因子：
8.9
作者：
Leong Hou U;N. Mamoulis;Man Lung Yiu
通讯作者：
Leong Hou U;N. Mamoulis;Man Lung Yiu
DOI：
--
发表时间：
2010-06
期刊：
--
影响因子：
--
作者：
M. Zaharia;Mosharaf Chowdhury;Michael J. Franklin;S. Shenker;I. Stoica
通讯作者：
M. Zaharia;Mosharaf Chowdhury;Michael J. Franklin;S. Shenker;I. Stoica
DOI：
10.1145/543613.543629
发表时间：
2002-06
期刊：
Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
Donghui Zhang;V. Tsotras;D. Gunopulos
通讯作者：
Donghui Zhang;V. Tsotras;D. Gunopulos
DOI：
10.1007/978-3-642-40235-7_1
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Shuyao Qi;Panagiotis Bouros;N. Mamoulis
通讯作者：
Shuyao Qi;Panagiotis Bouros;N. Mamoulis
DOI：
10.1109/icde.2012.87
发表时间：
2012-04
期刊：
2012 IEEE 28th International Conference on Data Engineering
影响因子：
--
作者：
Younghoon Kim;Kyuseok Shim
通讯作者：
Younghoon Kim;Kyuseok Shim