Approximate k -flat Nearest Neighbor Search
Wolfgang Mulzer, Huy Lê Nguyễn, Paul Seiferth, Yannik Stein · 2015
Let k ≥ 0 be an integer. In the approximate k-flat nearest neighbor (k-ANN) problem, we are given a set P ⊂ Rd of n points in d-dimensional space and a fixed approximation factor c > 1. Our goal is to preprocess P so that we can efficiently answer approximate k-flat nearest neighbor queries: given a k-flat F, find a point in P whose distance to F is within a factor c of the distance between F and the closest point in P. The case k = 0 corresponds to the well-studied approximate nearest neighbor problem, for which a plethora of results are known, both in low and high dimensions. The case k = 1 is called approximate line nearest neighbor. In this case, we are aware of only one provably efficient data structure, due to Andoni, Indyk, Krauthgamer, and Nguyen (AIKN) [2]. For k ≥ 2, we know of no previous results.