Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
复制标题
DOI：
10.1007/978-3-540-73951-7_4
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
Kengo Terasawa;Yuzuru Tanaka
中科院分区：
文献类型：
--
作者：
Kengo Terasawa;Yuzuru Tanaka
LSH （Locality Sensitive hash）是解决高维空间中最接近近邻问题的最著名的方法之一。本文提出了LSH算法的一种变体，重点讨论了数据集中所有点都位于ad维欧几里德空间中单位超球表面的特殊情况。LSH方案基于一组保持点局部性的哈希函数。本文指出，当所有点都被约束在单位超球的表面上时，存在比先前提出的方法更有效地划分空间的哈希函数。这些哈希函数的设计使用随机旋转的规则多面体，它像Voronoi图一样划分了单位超球的表面。我们的新方案改进了指数ρ，这是LSH算法性能的主要指标。
LSH (Locality Sensitive Hashing) is one of the best known methods for solving thec-approximate nearest neighbor problem in high dimensional spaces. This paper presents a variant of the LSH algorithm, focusing on the special case of where all points in the dataset lie on the surface of the unit hypersphere in ad-dimensional Euclidean space. The LSH scheme is based on a family of hash functions that preserves locality of points. This paper points out that when all points are constrained to lie on the surface of the unit hypersphere, there exist hash functions that partition the space more efficiently than the previously proposed methods. The design of these hash functions uses randomly rotated regular polytopes and it partitions the surface of the unit hypersphere like a Voronoi diagram. Our new scheme improves the exponentρ, the main indicator of the performance of the LSH algorithm.