The implementation of the Min-Hashing algorithm in Mahout

Min-Hashing was originally proposed as an efficient clustering algorithm that groups similar web pages into the same cluster with probability guarantee. In this paper, we focused on Min-Hashing implementations using MapReduce in Mahout, which is an open-source project of distributed and scalable machine learning algorithms. In particular, we observed a significant deviation between the real and expected performance of the minhash clustering package in Mahout. After careful examination of the relevant sourcecode, we identified two fatal conceptual mistakes in the implementation. Then, we rewrote the core part of the problematic Min-Hashing implementation in Mahout following the standard LSH algorithm. To validate the soundness of the revised version, we conducted extensive experiments with several real datasets. Experimental results confirmed the validity of our implementation, which could be integrated as a standard package in future versions of Mahout.