Approximate Nearest-Neighbors Using TCQ-Trees

We present a quad-tree variant that requires O(n) space, to answer low-dimensional approximate nearest-neighbor queries and approximate k-nearest-neighbor queries in O(d log h) time, where h is the height of the standard quad-tree on the input data. For most “realistic” input data, h = O(log n), implying that this algorithm provides a log-logarithmic query time using linear space. Achieving the query speed requires a new query-processing algorithm called the projection-based method. Our data structure is dynamic: insertions and deletions can be done in O(d log h) time as well, and it is fairly easy to implement. 1