High dimensional similarity search with space filling curves

We present a new approach for approximate nearest neighbor queries for sets of high dimensional points under any L-t-metric, t = 1,..., infinity. The proposed algorithm is efficient and simple to implement. The algorithm uses multiple shifted copies of the data points and stores them in up to (d + 1) B-trees where d is the dimensionality of the data, sorted according to their position along a space filling curve. This is done in a way that allows us to guarantee that a neighbor within an O(d(1+1/t)) factor of the exact nearest, can be returned with at most (d + 1)log(p) n page accesses, where p is the branching factor of the B-trees. In practice, for real data sets, our approximate technique finds the exact nearest neighbor between 87% and 99% of the time and a point no farther than the third nearest neighbor between 98% and 100% of the time. Our solution is dynamic, allowing insertion or deletion of points in O(d log(p) n) page accesses and generalizes easily to find approximate k-nearest neighbors.