相似性搜索是计算机学科中的一个基础性课题,被广泛应用于诸多研究领域中,包括信息检索,多媒体处理,机器学习等等。相似性搜索算法主要用于解决最近邻(Nearest Neighbor,NN)查询问题,由于在大部分的应用场景下,使用近似的查询结果就可以很好的满足应用的需求。因此,近年来,学术界提出了一系列近似求解最近邻查询问题的相似性搜索算法。然而,在大数据环境下,应用对搜索算法在数据维度、计算规模以及搜索性能等方面提出了更高的要求,使得高性能相似性搜索算法得到了当前学术界与工业界的普遍关注,这也是本文的主要研究内容。论文的主要成果包括:1.提出最优化子空间构建方法,提升了基于子空间聚类的一类相似性搜索算法的精度。针对基于子空间聚类的一类相似性搜索算法,本文提出了四种不同的子空间构建方案,并通过实验分析发现了子空间构建与搜索精度、搜索速度三者间的关联关系。基于这些关系,进一步提出了子空间构建的最优化方法,该方法解决了此类算法在搜索精度上不稳定的缺陷,在保持同等搜索速度的前提下能够获得26.7%的精度提升。2.提出一种新的高精度高可扩展的并行相似性搜索算法PCAF。PCAF首次采用估算排名的方式来预测数据之间相似性的大小差异,同时实现了一种开销极小的双堆数据过滤机制,并且创新性的对搜索任务内部耦合进行拆解,设计了一种细粒度的并行搜索策略。实现结果表明,与现有的五种最流行的并行相似性搜索算法相比,PCAF可扩展性最佳,速度最快,能够在最短时间内查询到高精度(>98%)最近邻结果,获得1.3倍至18.9倍的加速比,并且可在多种不同数据集上实现精准搜索的算法。3.提出一套执行优化框架,解决了相似性搜索算法在实际应用中的性能优化问题。该框架对执行优化系统的架构、各部分组成形式和逻辑结构都进行了明确且详细的定义。通过设置精度、速度和计算规模优化目标,利用二分查找原理调节算法参数,使得调优后的算法能够满足用户对实际应用中的精度和性能需求。实验结果表明,使用基于该框架设计的执行优化系统对RKD、RBC和PCAF算法调优以后,能够在达到用户所需精度(>95%)的同时获得5.87倍至70.46倍的性能提升。其中,PCAF算法能够在不到3秒的时间内,完成对包含100万条960维数据的真实大规模数据集“GIST1M”的最近邻查询,其搜索精度高达95.15%。