Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search

Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search

局部敏感哈希(Locality-Sensitive Hashing, LSH)及其变种是解决高维欧氏空间c-近似最近邻(c-ANN)搜索问题的常用索引方法。传统上，LSH函数是以一种查询无关的方式构造的，即在任何查询到达之前就对桶进行分区。然而，更接近查询的对象可能被划分到不同的桶中，这是我们不希望看到的。由于采用了查询无关的桶划分，目前最先进的外存LSH方案C2LSH和LSB-Forest仅适用于整数c≥2的近似比。

该文提出了一种新的查询感知的桶划分方法，该方法以给定的查询作为“锚”来进行桶划分。因此，查询感知的LSH函数是一个随机投影与查询感知的桶划分相耦合的过程，从而消除了传统查询无关LSH函数所需要的随机移位。值得注意的是，查询感知的桶划分可以很容易地实现，从而保证查询性能。本文提出了一种新的查询感知LSH方案QALSH，用于外存上的c-ANN搜索。理论研究表明，QALSH算法具有一定的查询质量保证。使用queryaware LSH函数使QALSH能够在任何近似比c &gt下工作;1. 实验结果表明，QALSH算法优于C2LSH算法和LSB-Forest算法，尤其在高维空间中表现更为突出。

一.解决的问题：