Telescope indexing for k-nearest neighbor search algorithms over high dimensional data & large data sets

When k-Nearest-Neighbors ([Formula: see text]-NN) was conceived more than 70 years ago, computation, as we use it now, would be hardly recognizable. Since then, technology has improved by orders of magnitude, including unprecedented connectivity. However, [Formula: see text]-NN has remained virtually unchanged, exposing its shortcomings for today's needs: becoming overwhelmed when presented with large, high-dimensional data. Although space partitioning data structures, especially k-d trees and ball-trees, have improved performance in larger data, they remain inadequate when data is also high-dimensional. Experiments confirm that space partitioning becomes ineffective in high-dimensional data because most of the search space is explored needlessly. Our strategy is to partition the data into small groups of points similarly distanced from a reference point in a B+ tree data structure and use this data structure to limit the search space of a [Formula: see text]-NN query. Further, we establish that the limited search space chosen by the B+ tree structure can be effectively explored by any indexing techniques applicable to the entire data. We then present our algorithm [Formula: see text]-NN with partitioning (ti[Formula: see text]-NN), including computational analysis and experiments. Our detailed evaluation demonstrates significant speedup achieved by ti[Formula: see text]-NN over the naive, [Formula: see text]-d tree, [Formula: see text]-tree based [Formula: see text]-NN and other state-of-the-art approximate [Formula: see text]-NN search approaches in high dimensional data.