MapReduce框架下基于B+树的高维索引

作者：梁俊杰; 肖瑶; 余敦辉

来源：计算机应用研究, 2016, 33(03): 706-715.

DOI：10.3969/j.issn.1001-3695.2016.03.016

• 大数据
• MapReduce
• KNN查询
• 高维索引

针对MapReduce数据块处理机制、高维数据分布特征和KNN查询需求,设计一种基于B+树的高维索引结构(i Partition),创新性提出基于主成分区分度的优化数据划分策略和邻接数据域分散存储等原则,将数据均匀划分到不同的slave节点,使尽可能多的数据域对计算共同贡献,提升MapReduce任务处理并行性;利用B+树构造分布式的双层索引实现查询时数据范围快速过滤,降低高维计算代价。实验表明,i Partition在高维数据近似查询环境下,具有良好的性能和扩展性。