LSH森林

我们考虑为回答（近似）相似性搜索查询而对高维数据进行索引的问题。相似性索引在各种环境中都被证明是重要的：网络搜索引擎希望对文本数据进行快速、并行、基于主内存的相似性搜索索引；数据库系统希望对高维数据（包括文本和图像）进行基于磁盘的相似性索引；点对点系统希望拥有低通信成本的分布式相似性索引。我们提出了一种称为LSH森林的索引方案，适用于上述所有上下文。我们的索引使用了众所周知的局部敏感哈希（LSH）技术，但通过（a）消除必须不断手动调优的不同数据依赖参数，以及（b）在保持相同存储和查询开销的同时改进LSH对偏斜数据分布的性能保证，来改进以往的设计。我们展示了如何在主内存、磁盘、并行系统和点对点系统中构建该索引。我们通过在多个文本语料库上的实验评估了该设计，并展示了LSH森林的自调节特性和卓越性能。