2020/05/23 by Christiani, Tobias
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2005.11547
Weighted minwise hashing is a standard dimensionality reduction technique with applications to similarity search and large-scale kernel machines. We introduce a simple algorithm that takes a weighted set x ∈ ℝ≥ 0d and computes k independent minhashes in expected time O(k log k + \Vert x \Vert0log( \Vert x \Vert1 + 1/\Vert x \Vert1)), improving upon the state-of-the-art BagMinHash algorithm (KDD '18) and representing the fastest weighted minhash algorithm for sparse data. Our experiments show running times that scale better with k and \Vert x \Vert0 compared to ICWS (ICDM '10) and BagMinhash, obtaining 10x speedups in common use cases. Our approach also gives rise to a technique for computing fully independent locality-sensitive hash values for (L, K)-parameterized approximate near neighbor search under weighted Jaccard similarity in optimal expected time O(LK + \Vert x \Vert0), improving on prior work even in the case of unweighted sets.