Sampling a Near Neighbor in High Dimensions — Who is the Fairest of Them All?
Sampling a Near Neighbor in High Dimensions — Who is the Fairest of Them All?
复制标题
在高维度中对近邻进行采样——谁是其中最公平的？
DOI：
10.1145/3502867
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Francesco Silvestri
中科院分区：
文献类型：
--
作者：
Martin Aumuller;Sariel Har;S. Mahabadi;R. Pagh;Francesco Silvestri
相似性搜索是一种基本的算法原语，广泛应用于许多计算机科学学科。给定一组点S和半径参数r > 0，r-近邻（r-NN）问题要求一个数据结构，给定任何查询点q，返回距离q至多r的点p。在本文中，我们研究的r-NN问题，根据个人的公平性，并提供平等的机会：所有的点，距离r内的查询应该有相同的概率被返回。在低维情况下，这个问题首先由Hu，Qiao和Tao（PODS 2014）研究。局部敏感哈希（LSH），理论上最强的方法，在高维相似性搜索，不提供这样的公平性保证。在这项工作中，我们表明，基于LSH的算法可以做到公平，而没有显着的效率损失。我们提出了几个有效的数据结构的公平NN问题的精确和近似的变种。我们的方法更普遍地适用于从给定集合的集合的子集合中均匀采样，并且可以在其他一些应用中使用。我们还开发了一个公平的相似性搜索下的内积，需要近线性空间和利用局部敏感的过滤器的数据结构。最后，本文通过实验评估强调了最先进的NN数据结构的不公平性，并显示了我们的算法在真实数据集上的性能。
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points S and a radius parameter r > 0, the r-near neighbor (r-NN) problem asks for a data structure that, given any query point q, returns a point p within distance at most r from q. In this paper, we study the r-NN problem in the light of individual fairness and providing equal opportunities: all points that are within distance r from the query should have the same probability to be returned. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014). Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. In this work, we show that LSH based algorithms can be made fair, without a significant loss in efficiency. We propose several efficient data structures for the exact and approximate variants of the fair NN problem. 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. We also develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights the unfairness of state-of-the-art NN data structures and shows the performance of our algorithms on real-world datasets.
DOI：
10.1145/3092931.3092933
发表时间：
2017
期刊：
ACM SIGMOD Record
影响因子：
--
作者：
Abiteboul S
通讯作者：
Abiteboul S
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