Near Neighbor Search via Efficient Average Distortion Embeddings

Deepanshu Kush, Aleksandar Nikolov, Haohua Tang

A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide…