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

针对大规模高维数据近似查询效率低下的问题，利用MapReduce编程模型在大规模集群上的数据与任务的并行计算与处理优势，提出MapReduce框架下大规模高维数据索引及KNN查询方法（iPBM），重点突破MapReduce数据块（block）的优化划分与各数据块对计算的共同贡献两大难题，利用两阶段数据划分策略并依据相关性与并行性原则将数据均匀分配到各数据块中，设计分布式的双层空间索引结构与并行KNN查询算法，检索时利用全局索引、局部索引与二维位码索引实现三层数据过滤，大幅缩小搜索范围并降低高维向量计算代价，实验表明iPBM对大规模高维数据的近似查询具有准确性、高效性和扩展性.

Optimized High-Dimensional Index and KNN Query in MapReduce

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.