论文标题
有效的近似近似邻居搜索多个加权$ l_ {p \ leq2} $距离功能
Efficient Approximate Nearest Neighbor Search for Multiple Weighted $l_{p\leq2}$ Distance Functions
论文作者
论文摘要
最近的邻居搜索对于广泛的应用是基础。由于确切的最近邻居搜索遭受了“维度的诅咒”，因此近似方法（例如对局部敏感的哈希（LSH））被广泛用于交易一些查询准确性，以提高查询效率。在许多情况下，有必要在高维空间中的多个加权距离功能下执行最近的邻居搜索。本文认为，在高维空间中支持有效的近似邻居搜索有效的近似邻居搜索的重要问题。据我们所知，先前的工作只能解决$ L_2 $距离的问题。但是，许多研究表明，$ l_p $距离$ p \ in（0,2）$比高维空间中的$ l_2 $距离更有效。我们提出了一种新颖的方法WLSH，以解决$ l_p $的$ p \ in（0,2] $。wlsh采用LSH方法，理论上可以保证处理查询的效率以及查询结果的准确性以及在最小化的总体效果上进行综合的效果，并显示出综合效果，并符合综合的效果，并符合综合效果，并符合综合效果。效率，查询准确性和空间消耗。
Nearest neighbor search is fundamental to a wide range of applications. Since the exact nearest neighbor search suffers from the "curse of dimensionality", approximate approaches, such as Locality-Sensitive Hashing (LSH), are widely used to trade a little query accuracy for a much higher query efficiency. In many scenarios, it is necessary to perform nearest neighbor search under multiple weighted distance functions in high-dimensional spaces. This paper considers the important problem of supporting efficient approximate nearest neighbor search for multiple weighted distance functions in high-dimensional spaces. To the best of our knowledge, prior work can only solve the problem for the $l_2$ distance. However, numerous studies have shown that the $l_p$ distance with $p\in(0,2)$ could be more effective than the $l_2$ distance in high-dimensional spaces. We propose a novel method, WLSH, to address the problem for the $l_p$ distance for $p\in(0,2]$. WLSH takes the LSH approach and can theoretically guarantee both the efficiency of processing queries and the accuracy of query results while minimizing the required total number of hash tables. We conduct extensive experiments on synthetic and real data sets, and the results show that WLSH achieves high performance in terms of query efficiency, query accuracy and space consumption.
