publication . Preprint . 2019

Near Neighbor: Who is the Fairest of Them All?

Har-Peled, Sariel; Mahabadi, Sepideh;
Open Access English
  • Published: 06 Jun 2019
Abstract
$\newcommand{\ball}{\mathbb{B}}\newcommand{\dsQ}{{\mathcal{Q}}}\newcommand{\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., $\ball(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 p...
Subjects
arXiv: Computer Science::DatabasesComputer Science::Information Retrieval
free text keywords: Computer Science - Machine Learning, Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms, Statistics - Machine Learning
Download from

Matt Olfat and Anil Aswani. Convex formulations for fair principal component analysis. arXiv preprint arXiv:1802.03765, 2018.

Geo Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pages 5680{5689, 2017. [OpenAIRE]

Yinian Qi and Mikhail J. Atallah. E cient privacy-preserving k-nearest neighbor search. In 28th IEEE International Conference on Distributed Computing Systems (ICDCS 2008), 17-20 June 2008, Beijing, China, pages 311{319. IEEE Computer Society, 2008. [OpenAIRE]

Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighbor methods in learning and vision: theory and practice (neural information processing). The MIT Press, 2006.

A. Torralba and A. A. Efros. Unbiased look at dataset bias. In CVPR 2011, pages 1521{1528, 2011. [OpenAIRE]

Abstract
$\newcommand{\ball}{\mathbb{B}}\newcommand{\dsQ}{{\mathcal{Q}}}\newcommand{\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., $\ball(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 p...
Subjects
arXiv: Computer Science::DatabasesComputer Science::Information Retrieval
free text keywords: Computer Science - Machine Learning, Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms, Statistics - Machine Learning
Download from

Matt Olfat and Anil Aswani. Convex formulations for fair principal component analysis. arXiv preprint arXiv:1802.03765, 2018.

Geo Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pages 5680{5689, 2017. [OpenAIRE]

Yinian Qi and Mikhail J. Atallah. E cient privacy-preserving k-nearest neighbor search. In 28th IEEE International Conference on Distributed Computing Systems (ICDCS 2008), 17-20 June 2008, Beijing, China, pages 311{319. IEEE Computer Society, 2008. [OpenAIRE]

Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighbor methods in learning and vision: theory and practice (neural information processing). The MIT Press, 2006.

A. Torralba and A. A. Efros. Unbiased look at dataset bias. In CVPR 2011, pages 1521{1528, 2011. [OpenAIRE]

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue