Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?

Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi +2

Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points $S$ and a radius parameter $r>0$, the $r$-near nei…