MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances
MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances
复制标题
DOI：
10.14778/3574245.3574269
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Kejing Lu;Y. Ishikawa;Chuan Xiao
中科院分区：
文献类型：
--
作者：
Kejing Lu;Y. Ishikawa;Chuan Xiao
点到超平面最近邻搜索（P2HNNS）是一个在数据挖掘和机器学习中有着广泛应用的基本问题。本文提出了一种基于多级量化误差的可证明位置敏感哈希（LSH）方案来解决这一问题。在索引阶段，对于每个数据点，我们通过逐步量化过程计算其残差向量的哈希值。在查询阶段，对于每个处理过的点，我们首先确定其适合的哈希级别，然后根据其在该级别的量化误差确定哈希桶的大小。我们从理论上证明，这种处理不仅可以保证查询结果的概率，而且还可以使生成的哈希函数更有效地修剪那些假点。在5个真实数据集上的实验结果表明，该方法的运行速度通常比最先进的基于lsh的方法快2 -10倍。
Point-to-hyperplane nearest neighbor search (P2HNNS) is a fundamental problem which has many applications in data mining and machine learning. In this paper, we propose a provable Locality-Sensitive-Hashing (LSH) scheme based on multi-level quantization errors to solve this problem. In the indexing phase, for each data point, we compute the hash values of its residual vectors generated by a stepwise quantization process. In the query phase, for each processed point, we first determine its suitable level for hashing and then determine the size of hash bucket based on its quantization error in that level. We theoretically show that this treatment not only yields a probability guarantee on query results, but also makes the generated hash functions much more efficient to prune those false points. Experimental results on five real datasets show that the proposed approach generally runs 2X-10X faster than the state-of-the-art LSH-based approaches.