Title: Engineering a Simplified 0-Bit Consistent Weighted Sampling,
Abstract: The Min-Hashing approach to sketching has become an important tool in data
analysis, information retrial, and classification. To apply it to real-valued
datasets, the ICWS algorithm has become a seminal approach that is widely used,
and provides state-of-the-art performance for this problem space. However, ICWS
suffers a computational burden as the sketch size K increases. We develop a new
Simplified approach to the ICWS algorithm, that enables us to obtain over 20x
speedups compared to the standard algorithm. The veracity of our approach is
demonstrated empirically on multiple datasets and scenarios, showing that our
new Simplified CWS obtains the same quality of results while being an order of
magnitude faster.