海量空间数据的并行Top-k连接查询  

Parallel Top-k Spatial Join Query Processing on Massive Spatial Data

作　　者：刘义[1] 陈荦[1] 景宁[1] 刘露[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,长沙410073

出　　处：《计算机研究与发展》2011年第S3期163-172,共10页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2008AA12A211;2011AA120306);国家自然科学基金项目(40801160;60902036)

摘　　要：在许多空间应用领域中,Top-k空间连接查询是一种十分重要的操作,指定两个空间关系R和S,Top-k空间连接查询从R或S中返回k个与其他空间关系具有最大交叠数的结果.不同于Top-k查询,Top-k空间连接查询先执行空间连接操作,然后才执行Top-k查询.由于空间数据的海量特性和复杂性,传统的单机串行处理需要很长时间甚至不能完成.提出了一种新颖的基于MapReduce的Top-k空间连接查询处理算法TKSJMR.该算法在并行空间连接阶段执行部分聚集操作,减少数据写入和数据传输;在Top-k结果获取阶段提出一种Top-k结果获取算法,将结果聚集和Top-k结果获取缩减为一个阶段,减少MapReduce执行步骤.实验结果表明,该算法不仅在有效时间内解决单机上难以解决的海量空间数据的Top-k连接查询问题,并且TKSJMR在Top-k查询处理阶段性能提升了约50%.在许多空间应用领域中,Top-k空间连接查询是一种十分重要的操作,指定两个空间关系R和S,Top-k空间连接查询从R或S中返回k个与其他空间关系具有最大交叠数的结果.不同于Top-k查询,Top-k空间连接查询先执行空间连接操作,然后才执行Top-k查询.由于空间数据的海量特性和复杂性,传统的单机串行处理需要很长时间甚至不能完成.提出了一种新颖的基于MapReduce的Top-k空间连接查询处理算法TKSJMR.该算法在并行空间连接阶段执行部分聚集操作,减少数据写入和数据传输;在Top-k结果获取阶段提出一种Top-k结果获取算法,将结果聚集和Top-k结果获取缩减为一个阶段,减少MapReduce执行步骤.实验结果表明,该算法不仅在有效时间内解决单机上难以解决的海量空间数据的Top-k连接查询问题,并且TKSJMR在Top-k查询处理阶段性能提升了约50%.

关 键 词：Top-k空间连接 MAPREDUCE 冗余避免 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]