Sampling a Near Neighbor in High Dimensions --- Who is the Fairest of Them All?
$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\Mh}[1]{#1}
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
Martin Aumüller,
Sariel Har-Peled,
Sepideh Mahabadi, Rasmus Pagh, and Francesco Silvestri.
Similarity search is a fundamental algorithmic primitive, widely
used in many computer science disciplines. Given a set of points
$\PS$ 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 inherent unfairness of NN data
structures and shows the performance of our algorithms on
real-world datasets.
\regVer{Preliminary versions of the results of this paper were published in
\cite{hm-nnwft-19,aps-fnnsi-20}.}
PDF.
:
arXiv
:
CACM
:
TDS
:
SIGMOD Rec.
:
NeuroIPS.
Last modified: Mon 2022-07-25 15:47:35 UTC 2022 by Sariel Har-Peled