PANENE: A Progressive Algorithm for Indexing and Querying Approximate k-Nearest Neighbors
Open Access
- 24 September 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Visualization and Computer Graphics
- Vol. 26 (2) , 1347-1360
Abstract
We present PANENE, a progressive algorithm for approximate nearest neighbor indexing and querying. Although the use of k-nearest neighbor (KNN) libraries is common in many data analysis methods, most KNN algorithms can only be queried when the whole dataset has been indexed, i.e., they are not online. Even the few online implementations are not progressive in the sense that the time to index incoming data is not bounded and cannot satisfy the latency requirements of progressive systems. This long latency has significantly limited the use of many machine learning methods, such as t-SNE, in interactive visual analytics. PANENE is a novel algorithm for Progressive Approximate k-NEarest NEighbors, enabling fast KNN queries while continuously indexing new batches of data. Following the progressive computation paradigm, PANENE operations can be bounded in time, allowing analysts to access running results within an interactive latency. PANENE can also incrementally build and maintain a cache data structure, a KNN lookup table, to enable constant-time lookups for KNN queries. Finally, we present three progressive applications of PANENE, such as regression, density estimation, and responsive t-SNE, opening up new opportunities to use complex algorithms in interactive systems.Keywords
Funding Information
- National Research Foundation of Korea (NRF-2016R1A2B2007153)
This publication has 29 references indexed in Scilit:
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Scalable Nearest Neighbor Algorithms for High Dimensional DataIEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
- KNN-kernel density-based clustering for high-dimensional multivariate dataComputational Statistics & Data Analysis, 2006
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998
- OpenMP: an industry standard API for shared-memory programmingIEEE Computational Science and Engineering, 1998
- AnO(n logn) algorithm for the all-nearest-neighbors ProblemDiscrete & Computational Geometry, 1989
- A hierarchical O(N log N) force-calculation algorithmNature, 1986
- Response time and display rate in human performance with computersACM Computing Surveys, 1984
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975