摘要：局部敏感哈希（LSH）及其变体是解决高维数据k近邻（k NN）搜索的有效算法.但是,随着数据规模的日趋庞大,传统的集中式LSH算法结构已经不能够满足大数据时代的需求.本文分析传统LSH方案的不足之处,拓展AND-OR结构,提出通过索引而不比较原始数据直接实现高维大数据k近邻搜索算法C2SLSH.理论分析和实验证明,C2SLSH在分布式平台下具有稳定的可扩展性,在保证同等精确率的情况下,处理速度大约是现有方法的3倍.

关键词：高维数据k近邻 局部敏感哈希 mapreduce 冲突计数排序 

单位：宁波大学信息科学与工程学院; 浙江宁波315211