Sampling near neighbors in search for fairness
Sampling near neighbors in search for fairness
复制标题
在邻居附近采样以寻求公平
DOI：
10.1145/3543667
复制
发表时间：
2022
影响因子：
22.7
通讯作者：
Silvestri, Francesco
中科院分区：
文献类型：
--
作者：
Aumüller, Martin;Har-Peled, Sariel;Mahabadi, Sepideh;Pagh, Rasmus;Silvestri, Francesco
相似性搜索是一种基本的算法原语，广泛应用于许多计算机科学学科。给定一个点集和一个半径参数r> 0，最近邻（r-NN）问题要求一个数据结构，给定任何查询点q，返回一个点p在距离内最strfromq.本文中，我们研究了最近邻问题的个人公平和提供平等的机会：所有点的距离内的查询应该有相同的概率被返回。这个问题是特别感兴趣的高维，其中局部敏感哈希（LSH），理论上领先的相似性搜索方法，不提供任何公平性保证。在这项工作中，我们表明，基于LSH的算法可以做到公平，而没有显着的效率损失。我们提出了几个有效的数据结构的公平NN问题的精确和近似的变种。我们的方法更普遍地适用于从给定集合的集合的子集合中均匀采样，并且可以在其他一些应用中使用。我们还进行了实验评估，突出了现有NN数据结构固有的不公平性。
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of pointsSand a radius parameterr> 0, ther-near neighbor (r-NN) problem asks for a data structure that, given any query pointq, returns a pointpwithin distance at mostrfromq.In this paper, we study ther-NN problem in the light of individual fairness and providing equal opportunities: all points that are within distancerfrom the query should have the same probability to be returned. The problem is of special interest in high dimensions, whereLocality Sensitive Hashing(LSH), the theoretically leading approach to similarity search, does not provide any 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 carried out an experimental evaluation that highlights the inherent unfairness of existing NN data structures.
登录
查看更多内容
DOI：
10.1109/sfcs.1983.35
发表时间：
1983-11
期刊：
24th Annual Symposium on Foundations of Computer Science (sfcs 1983)
影响因子：
--
作者：
R. Karp;M. Luby
通讯作者：
R. Karp;M. Luby
DOI：
10.1145/3196959.3196976
发表时间：
2017-03
期刊：
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
--
作者：
Martin Aumüller;Tobias Christiani;R. Pagh;Francesco Silvestri
通讯作者：
Martin Aumüller;Tobias Christiani;R. Pagh;Francesco Silvestri
DOI：
--
发表时间：
2019
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
Sariel Har;S. Mahabadi
通讯作者：
S. Mahabadi
k-NN 作为情境测试的实现，以发现和预防歧视
DOI：
--
发表时间：
2011
期刊：
Knowledge Discovery and Data Mining
影响因子：
--
作者：
Binh Luong Thanh;S. Ruggieri;F. Turini
通讯作者：
F. Turini
在高维度中对近邻进行采样——谁是其中最公平的？
DOI：
10.1145/3502867
发表时间：
2021
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
Martin Aumuller;Sariel Har;S. Mahabadi;R. Pagh;Francesco Silvestri
通讯作者：
Francesco Silvestri