Skip to Main content Skip to Navigation
Conference papers

Smaller, Faster & Lighter KNN Graph Constructions

Abstract : We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard's index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and show that GoldFinger can drastically accelerate a large range of existing KNN algorithms with little to no overhead. As a side effect, we also show that the compact representation of the data protects users' privacy for free by providing k-anonymity and l-diversity. Our extensive evaluation of the resulting approach on several realistic datasets shows that our approach delivers speedups of up to 78.9% compared to the use of raw data while only incurring a negligible to moderate loss in terms of KNN quality. To convey the practical value of such a scheme, we apply it to item recommendation and show that the loss in recommendation quality is negligible.
Complete list of metadata

Cited literature [46 references]  Display  Hide  Download
Contributor : François Taïani Connect in order to contact the contributor
Submitted on : Thursday, July 2, 2020 - 9:48:29 PM
Last modification on : Saturday, August 6, 2022 - 3:33:12 AM
Long-term archiving on: : Friday, November 27, 2020 - 11:09:56 AM


Files produced by the author(s)



Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas, François Taïani. Smaller, Faster & Lighter KNN Graph Constructions. WWW '20 - The Web Conference 2020, Apr 2020, Taipei Taiwan, France. pp.1060-1070, ⟨10.1145/3366423.3380184⟩. ⟨hal-02888286⟩



Record views


Files downloads