基于k-means 特征的适应性近似最近邻搜索算法

胡文洁， 杨凯祥， 谭宗元

（东华大学计算机科学与技术学院， 上海 201620）

0 引 言

随着互联网技术的快速发展，文字、图片和视频等信息呈指数式增长，给信息检索带来了巨大的挑战。 最近邻检索问题最早采用暴力搜索的方式，而暴力搜索通常采用线性扫描的方式，即计算目标点与每个数据点的相似性，从而返回与目标点最相似的结果。 针对十亿规模的高维数据，线性扫描效率过于低下的问题，研究者们开始研究海量数据中近似最近邻搜索问题，力求在数据集庞大的条件下，返回与目标最相似的K个邻居。 近似最近邻搜索在信息检索、人脸识别、文件检索、推荐系统等方面发挥着重要作用。

面对大规模的高维数据，近似最近邻搜索算法主要解决两个问题：降低内存占用和加快搜索时间。在降低内存占用方面，近似最近邻采用量化技术，将原始数据压缩为二进制编码进行存储，很大程度上降低了内存开销，其代表性算法包括乘积量化算法［1］、优化的乘积量化算法［2］和加和量化算法［3］。在加快搜索时间方面，近似最近邻搜索领域最常采用的解决措施是对数据构建索引，使用不同的方法对数据进行划分，在查找目标数据的最近邻时，仅仅搜索与目标数据最接近的一类数据，减少了数据的比对个数，降低了查询时间。 其中，基于向量量化的近似最近邻搜索算法［1-4］，根据数据构建倒排索引；而基于近邻图的近似最近邻搜索算法，是对数据构建图索引［5-6］。……