MapReduce框架下的优化高维索引与KNN查询  

Optimized High-Dimensional Index and KNN Query in MapReduce

作　　者：梁俊杰[1] 李凤华[2,3] 刘琼妮[1] 尹利[1] 

机构地区：[1]湖北大学计算机与信息工程学院,湖北武汉430062 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [3]北京电子科技学院,北京100070

出　　处：《电子学报》2016年第8期1873-1880,共8页Acta Electronica Sinica

基　　金：国家发改委2012年信息安全专项(No.发改办高技[2013]1309);国家自然科学基金(No.61170251);湖北省自然科学基金重点项目(No.2013CFA115);武汉市科技攻关计划(No.2013012401010851)

摘　　要：针对大规模高维数据近似查询效率低下的问题,利用MapReduce编程模型在大规模集群上的数据与任务的并行计算与处理优势,提出MapReduce框架下大规模高维数据索引及KNN查询方法(i PBM),重点突破MapReduce数据块(block)的优化划分与各数据块对计算的共同贡献两大难题,利用两阶段数据划分策略并依据相关性与并行性原则将数据均匀分配到各数据块中,设计分布式的双层空间索引结构与并行KNN查询算法,检索时利用全局索引、局部索引与二维位码索引实现三层数据过滤,大幅缩小搜索范围并降低高维向量计算代价,实验表明i PBM对大规模高维数据的近似查询具有准确性、高效性和扩展性.To address the low efficiency problem caused by the approximate large-scale high-dimensional data query, we propose a novel high-dimensional index and KNN query method,called iPBM,which exploits two main problems,inclu-ding the optimal division on the MapReduce’s data block and their contributions to the computing.Specifically,based on the principles of relativity and parallelity,iPBM employs a two-phase partitioning scheme of clustering and zoning to equally split the data to the available blocks,then we design a distributed two-layer index structure and parallel KNN query algo-rithm.With fully considering the global index,local index and two-dimensional bitcode property,iPBM achieves triple-layers filtering,and thus the number of queried area and the computing cost on the high-dimensional data is minimized.The accura-cy,efficiency and scalability of the proposed iPBM are thoroughly evaluated via detailed simulations.

关 键 词：云计算 MAPREDUCE KNN查询 高维索引 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]