GPH: Similarity Search in Hamming Space
GPH: Similarity Search in Hamming Space
复制标题
DOI：
10.1109/icde.2018.00013
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Jianbin Qin;Yaoshu Wang;Chuan Xiao;Wei Wang;Xuemin Lin;Y. Ishikawa
中科院分区：
文献类型：
--
作者：
Jianbin Qin;Yaoshu Wang;Chuan Xiao;Wei Wang;Xuemin Lin;Y. Ishikawa
汉明空间中的相似性搜索从查询向量中找到汉明距离不超过阈值的二进制向量。它是许多应用中的一个基本问题，包括图像检索，近似重复网页检测和机器学习。回答这种查询的最先进的方法主要是基于鸽子洞原理来生成一组候选人，然后验证它们。我们观察到，基于鸽子洞原则的约束并不总是严格的，因此可能会带来不必要的候选人。我们还观察到，在真实的数据的分布往往是倾斜的，但大多数现有的解决方案采用一个简单的等宽分区，并分配相同的阈值，所有的分区，因此无法利用数据的偏斜度来优化查询处理。在本文中，我们提出了一种新的形式的鸽子洞原则，它允许可变的分区大小和阈值。基于新的原则，我们首先开发了一个紧约束的候选人，然后设计成本感知的方法进行维划分和阈值分配，以优化查询处理。我们对具有各种数据分布的数据集的评估表明，我们的解决方案的鲁棒性和其上级查询处理性能的国家的最先进的方法。
A similarity search in Hamming space finds binary vectors whose Hamming distances are no more than a threshold from a query vector. It is a fundamental problem in many applications, including image retrieval, near-duplicate Web page detection, and machine learning. State-of-the-art approaches to answering such queries are mainly based on the pigeonhole principle to generate a set of candidates and then verify them. We observe that the constraint based on the pigeonhole principle is not always tight and hence may bring about unnecessary candidates. We also observe that the distribution in real data is often skew, but most existing solutions adopt a simple equiwidth partitioning and allocate the same threshold to all the partitions, and hence fail to exploit the data skewness to optimize the query processing. In this paper, we propose a new form of the pigeonhole principle which allows variable partition size and threshold. Based on the new principle, we first develop a tight constraint of candidates, and then devise cost-aware methods for dimension partitioning and threshold allocation to optimize query processing. Our evaluation on datasets with various data distributions shows the robustness of our solution and its superior query processing performance to the state-of-the-art methods.