Anne-Marie Kermarrec, Olivier Ruas, and François Taïani

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

Europar 2018, Turin, Italy, August, LNCS, volume 11014, pp. 419-431, Springer, 2018 (12p.)
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 document

doi: http://doi.org/10.1007/978-3-319-96983-1_30 (publisher's link)

bibtex

Copies / Update: Please contact me by email if you wish to obtain a copy of a paper that is not available on line.

[Maison.png]Back to Home
 
Last generated on 5 Feb 2020       francois.taiani@irisa.fr     Valid HTML 4.0!