Nobody cares if you liked Star Wars: KNN graph construction on the cheap - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (2) , (2)
1
2

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.
Fichier principal
Vignette du fichier
paper26.pdf (442.85 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01867230 , version 1 (04-09-2018)

Identifiers

Cite

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⟩
249 View
208 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More