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

ABSTRACT

前置知识：k-NN（k近邻）问题，以及其近似c-NN（乘上1+c）。

数学定义：

此处针对不同的相似度测量方法，局部敏感哈希的算法设计也不同。主要有min-hash（jaccard系数）, P-stable hash（欧氏距离度量）。

hash函数（单向散列函数）MD5、SHA-1、SHA-2和 SHA-3

提出了QALSH

大量的实验表明，QALSH优于C2LSH和LSB-Forest，特别是在高维空间。具体来说，通过使用比率c < 2, QALSH可以获得更好的查询质量。

INTRODUCTION

桶分区是在任何查询到达之前进行的，因此被称为是查询无关的。相应地，相应的LSH函数称为无关查询的LSH函数。图1给出了无关查询的桶分区的示例，其中随机线被分割为桶[0,w)，[−w, 0)， [w, 2w)，[−2w，−w)，等等。由于使用了floor函数，这里可以将随机线的原点(即0)视为定位每个区间边界的“锚”。查询无关桶分区的优点是将桶分区的开销留给预处理步骤

提到了关于E2LSH的两个点：C2LSH和Entropy-LSH

关于后者，有一篇北邮的论文ENTROPY BASED LOCALITY SENSITIVE HASHING 。

The distribution of mapped values is always uneven. Some buckets own many points, but others own few points.

this paper presents a set of new hash functions based on maximum entropy.