Query Independent Weighted Minwise Hashing

Abstract

Weighted Minwise Hashing (WMH) efficiently estimates
Generalized Jaccard Similarity between weighted sets
using rejection sampling, but requires query-dependent upper
bounds that prevent offline preprocessing of training data. This
limitation makes WMH impractical for large-scale data mining
and streaming applications. We propose Query Independent
Weighted Minwise Hashing (QIWMH), which eliminates this
dependency by randomly normalizing element weights to [0,1)
using only training data, enabling sketches of the training set to
be generated fully offline before any query arrives. We formally
prove that QIWMH is an approximate estimator of Generalized
Jaccard Similarity (GJS). Experimental evaluation on seven realworld
datasets across two tasks — 1-NN classification and Top-K
retrieval — demonstrates that QIWMH achieves comparable or
superior accuracy to state-of-the-art methods including WMH,
ICWS and PCWS, while achieving speedups of 2.3x to 14x in
generating sketches.