Similarity search is a fundamental algorithmic primitive, widely used in many\ncomputer science disciplines. Given a set of points $S$ and a radius parameter\n$r>0$, the $r$-near neighbor ($r$-NN) problem asks for a data structure that,\ngiven any query point $q$, returns a point $p$ within distance at most $r$ from\n$q$. In this paper, we study the $r$-NN problem in the light of individual\nfairness and providing equal opportunities: all points that are within distance\n$r$ from the query should have the same probability to be returned. In the\nlow-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS\n2014). Locality sensitive hashing (LSH), the theoretically strongest approach\nto similarity search in high dimensions, does not provide such a fairness\nguarantee. In this work, we show that LSH based algorithms can be made fair,\nwithout a significant loss in efficiency. We propose several efficient data\nstructures for the exact and approximate variants of the fair NN problem. Our\napproach works more generally for sampling uniformly from a sub-collection of\nsets of a given collection and can be used in a few other applications. We also\ndevelop a data structure for fair similarity search under inner product that\nrequires nearly-linear space and exploits locality sensitive filters. The paper\nconcludes with an experimental evaluation that highlights the inherent\nunfairness of NN data structures and shows the performance of our algorithms on\nreal-world datasets.\n