Distance-Sensitive Hashing
Distance-Sensitive Hashing
复制标题
DOI：
10.1145/3196959.3196976
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Martin Aumüller;Tobias Christiani;R. Pagh;Francesco Silvestri
中科院分区：
文献类型：
--
作者：
Martin Aumüller;Tobias Christiani;R. Pagh;Francesco Silvestri
局部敏感哈希（LSH）是处理高维含噪或不确定数据的重要工具，例如在数据清理（相似性连接）和抗噪搜索（相似性搜索）方面。然而，对于许多问题，LSH框架并不能产生良好的解决方案，相反，针对特定的相似性和距离度量已经设计了一些特殊的解决方案。例如，对于输出敏感的相似性搜索/连接，以及对于支持环形查询（旨在报告一个与查询点距离接近给定值的点）的索引来说就是如此。在本文中，我们开启了对距离敏感哈希（DSH）的研究，它是LSH的一种推广，旨在寻找一族哈希函数，使得两点具有相同哈希值的概率是它们之间距离的一个给定函数。更准确地说，给定一个距离空间（X，dist）和一个“碰撞概率函数”（CPF）f：R -> [0,1]，我们寻找函数对（h，g）的一种分布，使得对于X中的每一对点x，y，碰撞概率为Pr[h(x)=g(y)] = f(dist(x,y))。局部敏感哈希研究的是随着距离增加，CPF下降的速度有多快。对于许多空间，即使我们将注意力限制在g = h的对称情况下，f也可以呈指数下降。我们表明，通过使用一对函数所实现的不对称性使得有可能实现例如递增或单峰的CPF，并展示了这如何为LSH框架未解决的问题带来有原则的解决方案。这包括在隐私保护距离估计方面的一种新应用。我们相信DSH框架将在高维数据管理中找到更多应用。为了正确看待所提出构造的运行时间界限，我们给出了在角距离下具有递增和递减CPF的DSH构造性能的下界。本质上，这表明我们的构造在低阶项上是紧的。特别是，我们扩展了现有的LSH下界，表明它们在不对称设置下也成立。
Locality-sensitive hashing (LSH) is an important tool for managing high-dimensional noisy or uncertain data, for example in connection with data cleaning (similarity join) and noise-robust search (similarity search). However, for a number of problems the LSH framework is not known to yield good solutions, and instead ad hoc solutions have been designed for particular similarity and distance measures. For example, this is true for output-sensitive similarity search/join, and for indexes supporting annulus queries that aim to report a point close to a certain given distance from the query point. In this paper we initiate the study of distance-sensitive hashing (DSH), a generalization of LSH that seeks a family of hash functions such that the probability of two points having the same hash value is a given function of the distance between them. More precisely, given a distance space (X, dist ) and a "collision probability function" (CPF) f: R -> [0,1] we seek a distribution over pairs of functions (h,g) such that for every pair of points x, y ın X the collision probability is ¶r[h(x)=g(y)] = f(dist(x,y)). Locality-sensitive hashing is the study of how fast a CPF can decrease as the distance grows. For many spaces, f can be made exponentially decreasing even if we restrict attention to the symmetric case where g=h. We show that the asymmetry achieved by having a pair of functions makes it possible to achieve CPFs that are, for example, increasing or unimodal, and show how this leads to principled solutions to problems not addressed by the LSH framework. This includes a novel application to privacy-preserving distance estimation. We believe that the DSH framework will find further applications in high-dimensional data management. To put the running time bounds of the proposed constructions into perspective, we show lower bounds for the performance of DSH constructions with increasing and decreasing CPFs under angular distance. Essentially, this shows that our constructions are tight up to lower order terms. In particular, we extend existing LSH lower bounds, showing that they also hold in the asymmetric setting.