Near Neighbor Who Is The Fairest Of Them All

Sariel Har-peled, Sepideh Mahabadi. Neural Information Processing Systems 2019

[Paper]    
Independent LSH NEURIPS

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., $B(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 $p$ in the $r$-neighborhood of a query $q$ with almost uniform probability. The time to report such a point is proportional to $O(\text{dns}(q.r)Q(n,c))$, and its space is $O(S(n,c))$, where $Q(n,c)$ and $S(n,c)$ are the query time and space of an LSH algorithm for $c$-approximate near neighbor, and $\text{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.

Similar Work

• Sampling A Near Neighbor In High Dimensions -- Who Is The Fairest Of Them All
• Fair Near Neighbor Search Independent Range Sampling In High Dimensions
• Kernel Density Estimation Through Density Constrained Near Neighbor Search
• Parameter-free Locality Sensitive Hashing For Spherical Range Reporting