Approximate Nearest Neighbor Search for Low Dimensional Queries

Sariel Har-Peled, Nirman Kumar

We study the Approximate Nearest Neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high-di…