Multithreading approach to process real-time updates in KNN algorithms

Anne-Marie Kermarrec 1 Nupur Mittal 1 Javier Olivares 1
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 algorithm is the core of a considerable amount of online services and applications, like recommendation engines, content-classifiers, information retrieval systems, etc. The users of these services change their preferences and evolve with time, aggravating the computational challenges of KNN more with the ever evolving data to process. In this work, we present UpKNN: an efficient thread-based approach to take the updates of users preferences into account while it computes the KNN efficiently, keeping a check on the wall-time. By using an efficient thread-based approach, UpKNN processes millions of updates online, on a single commodity PC. Our experiments confirm the scalability of UpKNN, both in terms of the number of updates processed and the threads used. UpKNN achieves speedups ranging from 13.64X to 49.5X in the processing of millions of updates, with respect to the performance of a non-partitioned baseline. These results are a direct consequence of reducing the number of disk operations, roughly speaking, only 1% disk operations are performed as compared to the baseline.
Liste complète des métadonnées

https://hal.inria.fr/hal-01415495
Contributeur : Javier Olivares <>
Soumis le : mardi 13 décembre 2016 - 11:20:32
Dernière modification le : mardi 16 janvier 2018 - 15:54:13

Identifiants

  • HAL Id : hal-01415495, version 1

Collections

Citation

Anne-Marie Kermarrec, Nupur Mittal, Javier Olivares. Multithreading approach to process real-time updates in KNN algorithms. 2016. 〈hal-01415495〉

Partager

Métriques

Consultations de la notice

264