Finding Friends in High Dimensions...

on YouTube ↗11m

" summary

Locality-sensitive hashing converts item vectors into d-bit binaries by slicing space with random hyperplanes, producing fingerprints where Hamming distance proportional to angle lets similar items land in the same buckets. Permuting bits and lexically sorting yields candidate neighbors, then cosine similarity filters them. This drops nearest-neighbor work from O(n^2) to roughly s times n log n and is used for recommendations at SoundCloud on catalogs of 130,000,000 tracks, giving huge speedups in practice.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:51Vectors
3. 1:51KNearest Neighbors
4. 2:35Locality Sensitive Hashing
5. 6:23Hamming Distance
6. 8:10Summary
7. 8:49Why is this better
8. 9:09Supervised hashing

" related talks

• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 01h 34mAlgorithmic High-Dimensional Geometry IAlex Andoni · Big Data Boot Camp 2013
• 32mAdventures with Randomized Algebra for Extreme-Scale Signal ProcessingAnshumali Shrivastava · Randomized Numerical Linear Algebra and Applications 2018
• 01h 02mImportance Sampling in High Dimensions via HashingMoses Charikar · Sublinear Algorithms and Nearest-Neighbor Search
• 42mWhen Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity VectorsC. Seshadhri · Sublinear Algorithms and Nearest-Neighbor Search
• 40mData Deduplication using Locality Sensitive HashingMatti Lyra · PyData London 2018
• 36mThe unreasonable effectiveness of feature hashingGianluca Campanella · PyData London 2019