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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01867230
Contributor : Olivier Ruas <>
Submitted on : Tuesday, September 4, 2018 - 10:30:02 AM
Last modification on : Monday, December 3, 2018 - 10:20:04 PM
Long-term archiving on : Wednesday, December 5, 2018 - 12:57:31 PM

File

paper26.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

232

Files downloads

120