PANENE: A Progressive Algorithm for Indexing and Querying Approximate k-Nearest Neighbors - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Visualization and Computer Graphics Année : 2020

PANENE: A Progressive Algorithm for Indexing and Querying Approximate k-Nearest Neighbors

Jaemin Jo
  • Fonction : Auteur
  • PersonId : 1024025
Jinwook Seo
  • Fonction : Auteur
  • PersonId : 1024026
Jean-Daniel Fekete

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (3.99 Mo) Télécharger le fichier
Vignette du fichier
rtsne-cropped.png (658.1 Ko) Télécharger le fichier
rtsne (1).png (731.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
licence : CC BY NC ND - Paternité - Pas d'utilisation commerciale - Pas de modification
Loading...

Dates et versions

hal-01855672 , version 1 (08-08-2018)

Identifiants

Citer

Jaemin Jo, Jinwook Seo, Jean-Daniel Fekete. PANENE: A Progressive Algorithm for Indexing and Querying Approximate k-Nearest Neighbors. IEEE Transactions on Visualization and Computer Graphics, 2020, 26 (2), pp.1347-1360. ⟨10.1109/TVCG.2018.2869149⟩. ⟨hal-01855672⟩
274 Consultations
586 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More