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

https://hal.inria.fr/hal-02888286
Contributor : François Taïani <>
Submitted on : Thursday, July 2, 2020 - 9:48:29 PM
Last modification on : Wednesday, February 17, 2021 - 3:31:24 AM
Long-term archiving on: : Friday, November 27, 2020 - 11:09:56 AM

File

papier.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics