Near Neighbor: Who is the Fairest of Them All?
Near Neighbor: Who is the Fairest of Them All?
复制标题
近邻：谁是最美丽的？
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Mahabadi
中科院分区：
文献类型：
--
作者：
Sariel Har;S. Mahabadi
在这项工作中，我们研究了近邻问题的一个公平变体。也就是说，给定一组\(n\)个点\(P\)和一个参数\(r\)，目标是对这些点进行预处理，使得对于给定的一个查询点\(q\)，查询点的\(r\)邻域内的任何点，即\(\mathbb{B}(q,r)\)，被报告为近邻的概率相同。
我们表明基于局部敏感哈希（LSH）的算法可以变得公平，且效率没有显著损失。具体来说，我们展示了一种算法，它以几乎均匀的概率报告查询点\(q\)的\(r\)邻域内的一个点。查询时间与\(O(\mathrm{dns}(q,r)\mathcal{Q}(n,c))\)成正比，其空间为\(O(\mathcal{S}(n,c))\)，其中\(\mathcal{Q}(n,c)\)和\(\mathcal{S}(n,c)\)是用于\(c\)近似近邻的LSH算法的查询时间和空间，\(\mathrm{dns}(q,r)\)是\(q\)周围局部密度的一个函数。
我们的方法更普遍地适用于从给定集合的子集合中均匀采样，并且可以用于其他一些应用。最后，我们进行实验以展示我们的方法在真实数据上的性能。
$
ewcommand{all}{mathbb{B}}
ewcommand{dsQ}{mathcal{Q}}
ewcommand{dsS}{mathcal{S}}$In this work we study a fair variant of the near neighbor problem. Namely, given a set of $n$ points $P$ and a parameter $r$, the goal is to preprocess the points, such that given a query point $q$, any point in the $r$-neighborhood of the query, i.e., $all(q,r)$, have the same probability of being reported as the near neighbor.
We show that LSH based algorithms can be made fair, without a significant loss in efficiency. Specifically, we show an algorithm that reports a point in the $r$-neighborhood of a query $q$ with almost uniform probability. The query time is proportional to $Oigl( mathrm{dns}(q.r) dsQ(n,c) igr)$, and its space is $O(dsS(n,c))$, where $dsQ(n,c)$ and $dsS(n,c)$ are the query time and space of an LSH algorithm for $c$-approximate near neighbor, and $mathrm{dns}(q,r)$ is a function of the local density around $q$.
Our approach works more generally for sampling uniformly from a sub-collection of sets of a given collection and can be used in a few other applications. Finally, we run experiments to show performance of our approach on real data.
DOI：
--
发表时间：
2019-02
期刊：
ArXiv
影响因子：
--
作者：
A. Backurs;P. Indyk;Krzysztof Onak;B. Schieber;A. Vakilian;Tal Wagner
通讯作者：
A. Backurs;P. Indyk;Krzysztof Onak;B. Schieber;A. Vakilian;Tal Wagner