Near neighbor: Who is the fairest of them all?

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., Bpq, rq, 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 proportional to Odnspq:rqQpn; cq; and its space is OpSpn; cqq, where Qpn; cq and Spn; cq are the query time and space of an LSH algorithm for c-approximate near neighbor, and dnspq; rq is a function of the local density around q. and Spn, cq are the query time and space of an LSH algorithm for c-approximate near neighbor, and dnspq, rq 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.