RUC. Repositorio da Universidade da Coruña
Publication
Artículo científico (JournalArticle)
Fast Distributed kNN Graph Construction Using Auto-tuned Locality-sensitive Hashing
© 2020 Authors|ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Trans. Intell. Syst. Technol. 11, 6, Article 71 (October 2020). https://doi.org/10.1145/3408889., [Abstract]: The k-nearest-neighbors (kNN) graph is a popular and powerful data structure that is used in various areas of Data Science, but the high computational cost of obtaining it hinders its use on large datasets. Approximate solutions have been described in the literature using diverse techniques, among which Locality-sensitive Hashing (LSH) is a promising alternative that still has unsolved problems. We present Variable Resolution Locality-sensitive Hashing, an algorithm that addresses these problems to obtain an approximate kNN graph at a significantly reduced computational cost. Its usability is greatly enhanced by its capacity to automatically find adequate hyperparameter values, a common hindrance to LSH-based methods. Moreover, we provide an implementation in the distributed computing framework Apache Spark that takes advantage of the structure of the algorithm to efficiently distribute the computational load across multiple machines, enabling practitioners to apply this solution to very large datasets. Experimental results show that our method offers significant improvements over the state-of-the-art in the field and shows very good scalability as more machines are added to the computation., This research has been supported in part by the Spanish Ministerio de Economía y Competitividad (Projects No. TIN 2015-65069-C2-1-R and No. 2-R), partially funded by FEDER funds of the EU and by the Xunta de Galicia (Project No. ED431C 2018/34 and Centro singular de investigación de Galicia, accreditation 2016–2019), Xunta de Galicia; ED431C 2018/34
Project:
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2015-65069-C2-1-R
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2015-65069-C2-2-R
HANDLE: http://hdl.handle.net/2183/36047
View at: http://hdl.handle.net/2183/36047