近邻搜索方法与系统

摘要

本发明公开了一种近邻搜索方法与系统，包括线下学和线上搜索两部分，通过最小化哈希超平面两侧小区域内数据点个数的学函数，使哈希超平面穿过数据的稀疏区域，从而保证近邻搜索的高准确率，通过近似均衡桶条件，给学函数加上近似均衡桶正则项，使哈希超平面对数据点划分得更均衡，从而保证近邻搜索的高搜索速度。无论是对于少量还是海量数据，本方法与系统都能进行高准确率和高速度的近邻搜索。

主权项

一种近邻搜索方法，其特征在于，包括线下学习和线上搜索，所述线下学习包括如下步骤：随机均匀选取数据集中的预定数目的数据点作为锚点，通过计算数据点与所述锚点之间的距离得到核矩阵，并中心化该核矩阵；学习预定数目的二进制位的投影和阈值，每一个二进制位的学习包括：计算密度和均衡互补信息，使用中心化后的核矩阵及所述密度和均衡互补信息学习出投影和阈值，目标函数是最小化哈希超平面两侧小区域内数据点的个数，并保证桶是近似均衡的；通过中心化后的核矩阵，以及学习出的预定数目的二进制位的投影和阈值，将数据集中的数据点转换成二进制串，将相同二进制串的数据点放置到对应的桶中，建立哈希表；所述线上搜索包括如下步骤：对于每个查询数据点使用相同的所述锚点和核矩阵的均值得到查询数据点中心化后的核矩阵。使用查询数据点中心化后的核矩阵，以及学习出的投影和阈值，将每个查询数据点转换成二进制串。根据查询数据点转换的二进制串，在所述哈希表的对应桶中查找出预定数目的数据点，作为查询数据点的近邻。