LoSHa
Authors:
Open Access
- 7 August 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 635-644
Abstract
Locality Sensitive Hashing (LSH) algorithms are widely adopted to index similar items in high dimensional space for approximate nearest neighbor search. As the volume of real-world datasets keeps growing, it has become necessary to develop distributed LSH solutions. Implementing a distributed LSH algorithm from scratch requires high development costs, thus most existing solutions are developed on general-purpose platforms such as Hadoop and Spark. However, we argue that these platforms are both hard to use for programming LSH algorithms and inefficient for LSH computation. We propose LoSHa, a distributed computing framework that reduces the development cost by designing a tailor-made, general programming interface and achieves high efficiency by exploring LSH-specific system implementation and optimizations. We show that many LSH algorithms can be easily expressed in LoSHa's API. We evaluate LoSHa and also compare with general-purpose platforms on the same LSH algorithms. Our results show that LoSHa's performance can be an order of magnitude faster, while the implementations on LoSHa are even more intuitive and require few lines of code.Keywords
Funding Information
- ITF (6904079)
- Research Committee of CUHK (3132821)
- Hong Kong RGC (14222816, CUHK14206715)
This publication has 24 references indexed in Scilit:
- Large-scale distributed graph computing systemsProceedings of the VLDB Endowment, 2014
- SRSProceedings of the VLDB Endowment, 2014
- Scaling Distributed Machine Learning with the Parameter Server2014
- DSH2014
- SK-LSHProceedings of the VLDB Endowment, 2014
- Streaming similarity search over one billion tweets using parallel locality-sensitive hashingProceedings of the VLDB Endowment, 2013
- Efficient distributed locality sensitive hashing2012
- Locality-sensitive hashing scheme based on dynamic collision counting2012
- Data Mining2011
- Similarity estimation techniques from rounding algorithms2002