Skip to Main content Skip to Navigation
Conference papers

The Out-of-core KNN Awakens: The light side of computation force on large datasets

Nitin Chiluka 1, * Anne-Marie Kermarrec 1 Javier Olivares 1 
* Corresponding author
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : K-Nearest Neighbors (KNN) is a crucial tool for many applications , e.g. recommender systems, image classification and web-related applications. However, KNN is a resource greedy operation particularly for large datasets. We focus on the challenge of KNN computation over large datasets on a single commodity PC with limited memory. We propose a novel approach to compute KNN on large datasets by leveraging both disk and main memory efficiently. The main rationale of our approach is to minimize random accesses to disk, maximize sequential accesses to data and efficient usage of only the available memory. We evaluate our approach on large datasets, in terms of performance and memory consumption. The evaluation shows that our approach requires only 7% of the time needed by an in-memory baseline to compute a KNN graph.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Javier Olivares Connect in order to contact the contributor
Submitted on : Thursday, June 23, 2016 - 3:24:29 PM
Last modification on : Wednesday, November 3, 2021 - 4:34:46 AM
Long-term archiving on: : Saturday, September 24, 2016 - 11:45:04 AM


Files produced by the author(s)


  • HAL Id : hal-01336673, version 1


Nitin Chiluka, Anne-Marie Kermarrec, Javier Olivares. The Out-of-core KNN Awakens: The light side of computation force on large datasets. The International Conference on Networked Systems NETYS, May 2016, Marrakech, Morocco. ⟨hal-01336673⟩



Record views


Files downloads