Abstract
In this study, we present a novel ranking model based on learning neighborhood relationships embedded in the index space. Given a query point, conventional approximate nearest neighbor search calculates the distances to the cluster centroids, before ranking the clusters from near to far based on the distances. The data indexed in the top-ranked clusters are retrieved and treated as the nearest neighbor candidates for the query. However, the loss of quantization between the data and cluster centroids will inevitably harm the search accuracy. To address this problem, the proposed model ranks clusters based on their nearest neighbor probabilities rather than the query-centroid distances. The nearest neighbor probabilities are estimated by employing neural networks to characterize the neighborhood relationships, i.e., the density function of nearest neighbors with respect to the query. The proposed probability-based ranking can replace the conventional distance-based ranking for finding candidate clusters, and the predicted probability can be used to determine the data quantity to be retrieved from the candidate cluster. Our experimental results demonstrated that the proposed ranking model could boost the search performance effectively in billion-scale datasets.
Abstract (translated)
在这项研究中，我们提出了一个新的基于学习邻域关系的指数空间排名模型。在给定一个查询点的情况下，传统的近似最近邻搜索在根据距离对簇进行从近到远排序之前，先计算到簇形心的距离。检索排名靠前的集群中索引的数据，并将其视为查询的最近邻居候选。然而，数据与聚类中心之间的量化丢失将不可避免地影响搜索精度。为了解决这个问题，该模型基于最近邻概率而不是查询质心距离对集群进行排序。最近邻概率是通过使用神经网络来描述邻域关系来估计的，即最近邻对查询的密度函数。所提出的基于概率的排序方法可以取代传统的基于距离的排序方法来寻找候选簇，预测的概率可以用来确定从候选簇中检索到的数据量。实验结果表明，该排序模型能有效地提高亿尺度数据集的搜索性能。
URL
https://arxiv.org/abs/1807.02962
