Skip to Main content Skip to Navigation
Conference papers

Nobody cares if you liked Star Wars: KNN graph construction on the cheap

Abstract : K-Nearest-Neighbors (KNN) graphs play a key role in a large range of applications. A KNN graph typically connects entities characterized by a set of features so that each entity becomes linked to its k most similar counterparts according to some similarity function. As datasets grow, KNN graphs are unfortunately becoming increasingly costly to construct, and the general approach, which consists in reducing the number of comparisons between entities, seems to have reached its full potential. In this paper we propose to overcome this limit with a simple yet powerful strategy that samples the set of features of each entity and only keeps the least popular features. We show that this strategy outperforms other more straightforward policies on a range of four representative datasets: for instance, keeping the 25 least popular items reduces computational time by up to 63%, while producing a KNN graph close to the ideal one.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Olivier Ruas Connect in order to contact the contributor
Submitted on : Tuesday, September 4, 2018 - 10:30:02 AM
Last modification on : Tuesday, October 19, 2021 - 11:04:41 AM
Long-term archiving on: : Wednesday, December 5, 2018 - 12:57:31 PM


Files produced by the author(s)



Anne-Marie Kermarrec, Olivier Ruas, François Taïani. Nobody cares if you liked Star Wars: KNN graph construction on the cheap. Europar 2018, Aug 2018, Turin, Italy. pp.419-431, ⟨10.1007/978-3-319-96983-1_30⟩. ⟨hal-01867230⟩



Record views


Files downloads