On the theory and practice of high-dimensional data indexing with iDistance
Michael A. Schuh, Rafal A. Angryk · 2016
An important and challenging task for modern large-scale and high-dimensional data is k-nearest neighbor (kNN) retrieval. Using iDistance as the current state-of-the-art high-dimensional indexing algorithm, this work discusses the theoretical bounds associated with a distance-based indexing technique and proposes several simple optimizations to improve the efficiency and stability of query retrieval. We then present practical analysis of these bounds and optimizations through experiments on synthetic and real world datasets over a wide variety of data characteristics. Results indicate overall greatly improved retrieval performance and especially promising results in high dimensions.