随着以互联网技术为代表的计算机技术的普及,世界步入了大数据时代。相似性查询是日常生活中是人们获取信息的常见手段,更是大数据时代至关重要的需求。大数据在给人们带来丰富资讯和高质量体验的同时,也对很多传统领域产生了挑战。维度灾难使得基于空间划分和数据划分的索引方式不再能有效解决查询问题,为此研究者提出近似相似性查询的理念,以少量查询精度为代价大大减少查询耗时。局部敏感哈希技术(Locality Sensitive Hashing,LSH)作为近似相似性查询的最新技术,逐渐成为研究热点,其基本思想可以概括为过滤-验证框架(Filter-and-Refine Framework),即先过滤掉低概率相似的数据对象,然后精确计算候选数据对象和查询项之间的相似度,这就大大减少了查询所需的精确计算,从而可以快速得出查询结果。局部敏感哈希使用大量哈希表以高概率保证计算的准确性,这造成了基于LSH的算法空间开销过大的缺陷。本文提出一种分布式和集中式的LSH近似近邻查找算法,即基于Multi-probe的分布式LSH近似近邻查找方案和基于海明距离的LSH近似近邻查找算法。分布式方案侧重于通过Multi-probe技术,在Chord环上构建分布式索引的方法,在保证召回率的情况下显著减少哈希表数量;集中式算法利用哈希结果产生的特征指纹,用随机抽取的方式产生指纹子串并构建索引表,通过比较查询项和数据项的项指纹子串的海明距离,对数据项赋予权值以减少候选数据集大小。总之,通过分布式和集中式两种方法,分别对应不同的应用背景,在减少哈希表占用空间过大的同时,有效地提高了近邻查找的性能。