Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadata
Contributor : Javier Olivares Connect in order to contact the contributor
Submitted on : Tuesday, December 13, 2016 - 11:20:32 AM
Last modification on : Saturday, June 25, 2022 - 7:40:52 PM


  • HAL Id : hal-01415495, version 1


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



Record views