On the Difficulty of Nearest Neighbor Search
On the Difficulty of Nearest Neighbor Search
复制标题
DOI：
--
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Junfeng He;Sanjiv Kumar;Shih-Fu Chang
中科院分区：
文献类型：
--
作者：
Junfeng He;Sanjiv Kumar;Shih-Fu Chang
大型数据库中的快速近似最近邻（NN）搜索正变得流行。最近提出了几种强大的基于学习的公式。然而，人们并没有过多关注一个更基本的问题：在给定的数据集中（近似）最近邻搜索有多困难？哪些数据属性影响最近邻搜索的难度以及如何影响？本文介绍了第一个称为相对对比度的具体度量，它可用于同时评估任意赋范度量空间中几个关键数据特征（例如维数、稀疏性和数据库大小）的影响。此外，我们提出了理论分析来证明难度度量（相对对比度）如何确定/影响局部敏感哈希（一种流行的近似神经网络搜索方法）的复杂性。相对对比也为基于PCA的一系列具有良好实用性能的启发式哈希算法提供了解释。最后，我们表明，大多数先前测量 NN 搜索意义/难度的工作都可以导出为所提出的测量的稠密向量的特殊渐近情况。
Fast approximate nearest neighbor(NN) search in large databases is becoming popular. Several powerful learning-based formulations have been proposed recently. However, not much attention has been paid to a more fundamental question: how difficult is (approximate) nearest neighbor search in a given data set? And which data properties affect the difficulty of nearest neighbor search and how? This paper introduces the first concrete measure called Relative Contrast that can be used to evaluate the influence of several crucial data characteristics such as dimensionality, sparsity, and database size simultaneously in arbitrary normed metric spaces. Moreover, we present a theoretical analysis to prove how the difficulty measure (relative contrast) determines/affects the complexity of Local Sensitive Hashing, a popular approximate NN search method. Relative contrast also provides an explanation for a family of heuristic hashing algorithms with good practical performance based on PCA. Finally, we show that most of the previous works in measuring NN search meaningfulness/difficulty can be derived as special asymptotic cases for dense vectors of the proposed measure.