When Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors
summary
A MapReduce-style algorithm (WIMP) combines wedge sampling (Cohen–Lewis) with SimHash sketches to approximate all pairs with cosine similarity ≥ τ while minimizing network shuffle. Communication scales roughly as (output_count)/τ + (nnz)/τ^2, requiring sketch lengths ≈1/τ^2 bits. Implemented on production-scale data (about 100 billion non-zeros after filtering extreme-degree rows), it reduces estimated shuffle from tens of thousands of terabytes to a few hundred and completes within a day, with high precision and tunable recall.
AI-written summary · about
chapters (26)
- 0:00Intro
- 1:55The problem
- 5:28The challenge
- 7:50The distributed framework
- 10:17Previous art
- 11:51The Twitter problem
- 12:57The similarity threshold
- 13:24Real recommendations
- 13:57The quadratic bottleneck
- 14:37Our real contribution
- 19:52Distributed wedge sampling
- 20:57How many wedges?
- 22:33Signal vs noise
- 24:50Pruning with oracle
- 26:08Something obvious
- 26:41Something not obvious
- 27:57The hashing scheme
- 28:38Choosing the hash length
- 29:18Generating Sim Hashes
- 31:42The Wedges
- 34:15Major caveat!
- 35:03Communication
- 36:17The skew problem?
- 37:12Minhash alternative?
- 37:45Uses of non-negativity?
- 38:12Finding large entries in matrix product?
related talks
11mFinding Friends in High Dimensions...
36mThe unreasonable effectiveness of feature hashing
01h 24mStreaming, Sketching and Sufficient Statistics I
40mData Deduplication using Locality Sensitive Hashing
45mThe Approximate Filter, Join, and GroupBy
27mSampling Algorithms to Count Frequent Patterns in Graphs
37mMin-Wise Hashing for Large-Scale Regression and Classification
24mEfficient Similar-Object Search Algorithms for Terabytes of Data