Approximate Nearest Neighbor Search for Low-Dimensional Queries
Sariel Har-Peled, Nirman Kumar · SIAM Journal on Computing · 2013
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 dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data.