A Progressive k-d tree for Approximate k-Nearest Neighbors - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

A Progressive k-d tree for Approximate k-Nearest Neighbors

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

Résumé

We present a progressive algorithm for approximate k-nearest neighbor search. Although the use of k-nearest neighbor libraries (KNN) is common in many data analysis methods, most KNN algorithms can only be run 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 can exceed the latency required by progressive systems. Exceeding this latency significantly impacts the interactivity of visualization systems especially when dealing with large-scale data. We improve traditional k-d trees for progressive approximate k-nearest neighbor search, enabling fast KNN queries while continuously indexing new batches of data when necessary. Following the progressive computation paradigm, our progressive k-d tree is bounded in time, allowing analysts to access ongoing results within an interactive latency. We also present performance benchmarks to compare online and progressive k-d trees.
Fichier principal
Vignette du fichier
A_Progressive_KD_Tree___DSIA_VIS2017 (1).pdf (500.33 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01650272 , version 1 (28-11-2017)

Identifiants

  • HAL Id : hal-01650272 , version 1

Citer

Jaemin Jo, Jinwook Seo, Jean-Daniel Fekete. A Progressive k-d tree for Approximate k-Nearest Neighbors. Workshop on Data Systems for Interactive Analysis (DSIA), Oct 2017, Phoenix, United States. ⟨hal-01650272⟩
212 Consultations
1974 Téléchargements

Partager

Gmail Facebook X LinkedIn More