MapReduce框架下的优化高维索引与KNN查询
2016-11-17梁俊杰李凤华刘琼妮
梁俊杰,李凤华,刘琼妮,尹 利
(1.湖北大学计算机与信息工程学院,湖北武汉 430062;2.中国科学院信息工程研究所信息安全国家重点实验室,北京 100093;3.北京电子科技学院,北京 100070)
MapReduce框架下的优化高维索引与KNN查询
梁俊杰1,李凤华2,3,刘琼妮1,尹 利1
(1.湖北大学计算机与信息工程学院,湖北武汉 430062;2.中国科学院信息工程研究所信息安全国家重点实验室,北京 100093;3.北京电子科技学院,北京 100070)
针对大规模高维数据近似查询效率低下的问题,利用MapReduce编程模型在大规模集群上的数据与任务的并行计算与处理优势,提出MapReduce框架下大规模高维数据索引及KNN查询方法(iPBM),重点突破MapReduce数据块(block)的优化划分与各数据块对计算的共同贡献两大难题,利用两阶段数据划分策略并依据相关性与并行性原则将数据均匀分配到各数据块中,设计分布式的双层空间索引结构与并行KNN查询算法,检索时利用全局索引、局部索引与二维位码索引实现三层数据过滤,大幅缩小搜索范围并降低高维向量计算代价,实验表明iPBM对大规模高维数据的近似查询具有准确性、高效性和扩展性.
云计算;MapReduce;KNN查询;高维索引
电子学报URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.015
1 引言
随着下一代互联网、物联网和云计算[1]等信息技术的创新发展和重点应用,用户面临海量数据或大数据诸多挑战,很多领域数据呈现高维表现形态,如金融交易数据、多媒体数据、航天数据、生物数据等,维度高达几十维甚至上百维.高维空间数据应用常见以近似查询(similarity query)为主,如何提高……
