MapReduce框架下基于R-树的k-近邻连接算法

被引：116

作者：

刘义

景宁

陈荦

熊伟

机构：

[1] 国防科学技术大学电子科学与工程学院

来源：

软件学报 | 2013年 / 24卷 / 08期

基金：

高等学校博士学科点专项科研基金;

关键词：

云计算; MapReduce; k-近邻连接; 空间查询; R-树;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

摘要：

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速构建算法和基于R-树的并行k-近邻连接算法.在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达.在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用R-树索引进行k-近邻连接查询,提高了查询效率.从理论上分析了所提出算法的通信和计算代价.实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值.

引用

页码：1836 / 1851

页数：16