DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search

局部敏感哈希（LSH）是在高维空间中进行近似最近邻（ANN）搜索的众所周知的解决方案，由于其在查询准确度上具有强大的理论保证。传统的基于LSH的方法主要集中于通过设计不同的查询策略来提高查询阶段的效率和准确性，但很少关注如何提高索引阶段的效率。它们通常通过微调现有的数据导向分区树来索引数据点并支持它们的查询策略。然而，直接对多维空间进行分区的策略耗时，并且随着空间维度的增加，性能会下降。本文设计了一种基于编码的树，称为动态编码树（DE-Tree），以提高索引效率并支持基于欧几里得距离的有效范围查询。基于DE-Tree，我们提出了一种新颖的LSH方案，称为DET-LSH。DET-LSH采用一种新颖的查询策略，它在多个独立的索引DE-Tree中执行范围查询，以降低错过精确NN点的概率，从而提高查询准确性。我们的理论研究表明，DET-LSH具有查询准确性的概率保证。对真实数据集的广泛实验表明，DET-LSH在效率和准确性上优于现有的基于LSH的方法。虽然比竞争对手实现了更好的查询准确性，但DET-LSH在索引时间上实现了高达6倍的加速，在查询时间上实现了2倍的加速。本文发表于PVLDB 2024。

提高局部敏感哈希（LSH）索引阶段的效率，以支持高维空间中的近似最近邻搜索。

设计一种基于编码的树结构，称为Dynamic Encoding Tree（DE-Tree），以提高索引效率，并支持基于欧氏距离的高效范围查询。在DE-Tree的基础上，提出了一种新颖的LSH方案，称为DET-LSH，采用多个独立的DE-Tree执行范围查询，以降低错过精确最近邻点的概率，从而提高查询准确性。

DET-LSH在实验中表现出比现有LSH方法更高的效率和准确性，同时实现了比竞争对手更好的查询准确性，DE-Tree的使用使得DET-LSH在索引时间上实现了高达6倍的加速，在查询时间上实现了2倍的加速。

与本论文相关的研究包括：1.在高维空间中进行近似最近邻搜索的其他LSH方法，如Multi-probe LSH；2.基于编码的索引方法，如Product Quantization。