一种基于网格索引的空间连接查询处理优化算法-论文.pdf

《一种基于网格索引的空间连接查询处理优化算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、小型微型计算机系统2014年10月第10期JournalofChineseComputerSystemsV01．35No．102014一种基于网格索引的空间连接查询处理优化算法乔百友，邓增安，王秋杰，朱红印，孔德福，王国仁’(国家海洋信息中心，天津300171)(东北大学信息科学与工程学院，沈阳110819)E—mail：qiaobaiyou@ise．rleB．edu．ca摘要：针对云环境下的空间数据连接查询处理问题，提出一种基于MapReduce框架的高效空间连接查询处理优化算法．该算法采用网格划分方法将数据空间

2、划分成大小相同的网格单元，并将其中一类数据集中的每个空间对象，按照其中心点的位置划分到所在的网格单元中，从而避免了连接对象的复制，网格单元之间根据其所包含数据对象的交叠关系构建网格索引；对另一类数据集中的对象，仅将其复制到与网格单元中数据有交叠的网格单元，从而过滤掉不可能有连接结果的数据对象，大大减少了后续的连接计算代价．合成数据和真实数据集上的大量实验表明，本文提出的空间数据连接查询处理优化算法在性能上明显优于原有SJMR查询处理算法．关键词：连接查询；MapReduce；空间数据；网格索引中图分类号：TP393

3、文献标识码：A文章编号：1000—1220(2014)10-2243-06ASpatialJoinQueryOptimizationAlgorithmBasedonGridIndexQIAOBai—you·，DENGZeng—all，WANGQiu-jiez，ZHUHong—yin，KONGDe—fuz，WANGGuo-rent。(NationalMarineDataandInformationService。StateOceanicAdministration。Tianjin300171。China)(Colle

4、geofInformationScience&Engineering，NortheasternUniversity，Shenyang110819，China)Abstract：Armingattheproblemofspatialjoinqueryprocessingincloudcomputing，aneffectivespatialjoinqueryprocessingoptimi-zafionalgorithmisproposedinthispaper。whichisbasedontheMapReducefr

5、amework．Dataspaceispartitionedintomanygridcellsbyusinggriddivisionapproach，andeachspatialobjectinonedatasetisdistributedintoagridcellaccordingtoitscen~alpointposi—tion，thisavoidstheredundantduplicationofthedataobject．Accordingtotheintersectionrelationshipofdat

6、aobjectscontainedbythesegridcells，agridindexisconstructedtofilteruselessjoinobjects．Foranotherdataset，weusethegridindextoduplicateeachda-taobjectonlytothegridcellsinwhichthereexistsonedataobjectintersectedwiththedataobject，andthusfilteringouttheuselessdataobje

7、cts，therebygreatlyreducingthecorrespondingcomputationalcost．ComparativeexperimentsonsyntheticdataandrealdatasetsshowthattheproposedspatialdatajoinqueryprocessingoptimizationalgorithmhasobviousadvantagesandbetterperformancethanSJMRalgorithm．Keywords：joinqueries

8、；MapReduce；spatialdata；gridindex1引言题进行了研究，并给出了几种优化策略．文献[6，7]研究了Mapreduce下的高效的相似性连接和Top-K相似性连接算空间连接查询是一种常用的空间查询类型，也一直是空法．文献[8，9]则主要聚焦于集合相似性连接算法的研究，并间数据库领域的研究热点之一，特别是随着对地观测技术的提出了几种优化