Fast spectral analysis for approximate nearest neighbor search
Fast spectral analysis for approximate nearest neighbor search
复制标题
DOI：
10.1007/s10994-021-06124-1
复制
发表时间：
2022-01
期刊：
影响因子：
7.5
通讯作者：
Jing Wang;Jie Shen
中科院分区：
文献类型：
--
作者：
Jing Wang;Jie Shen
在大规模机器学习中，最感兴趣的是近似最近邻（ANN）搜索问题，其目标是查询在特定度量下接近给定对象的特定点。在本文中，我们开发了一种新的数据驱动的人工神经网络搜索算法，其中的数据结构是学习的快速谱技术的基础上选择的近似岭杠杆得分的landmarks。我们表明，以压倒性的概率，我们的算法返回任何近似参数的人工神经网络。我们的算法的一个显着特点是，它是计算效率。具体来说，学习k长度的哈希码需要运行时间和额外的空间，返回查询的ANN需要运行时间。在计算机视觉和自然语言理解任务上的实验结果表明，与最先进的方法相比，我们的算法具有显着的优势。
In large-scale machine learning, of central interest is the problem of approximate nearest neighbor (ANN) search, where the goal is to query particular points that are close to a given object under certain metric. In this paper, we develop a novel data-driven ANN search algorithm where the data structure is learned by fast spectral technique based onslandmarks selected by approximate ridge leverage scores. We show that with overwhelming probability, our algorithm returns the-ANN for any approximation parameter. A remarkable feature of our algorithm is that it is computationally efficient. Specifically, learningk-length hash codes requiresrunning time andextra space, and returning the-ANN of the query needsrunning time. The experimental results on computer vision and natural language understanding tasks demonstrate the significant advantage of our algorithm compared to state-of-the-art methods.