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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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

https://hal.inria.fr/hal-01336673
Contributor : Javier Olivares <>
Submitted on : Thursday, June 23, 2016 - 3:24:29 PM
Last modification on : Thursday, January 7, 2021 - 4:39:45 PM
Long-term archiving on: : Saturday, September 24, 2016 - 11:45:04 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01336673, version 1

Citation

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⟩

Share

Metrics

Record views

624

Files downloads

723