Probabilistic Hashing Methods for Succinct Data Representations and Applications

on YouTube ↗39m

" summary

Uses alpha-stable random projections (alpha near zero and maximally-skewed beta=1) to get extremely sparse, noise-robust compressive sensing that recovers k=2 sparse signals with three measurements for k=2 and generalizes to one-scan or few-iteration exact recovery with sparse design matrices. Shows moment/entropy estimation on streams with 10–100 samples instead of millions via correlated stable projections. Introduces b-bit minwise hashing and one-permutation with K bins to cut storage dramatically — empirical example compresses a 24 GB feature representation down to ~70 MB while preserving accuracy.

AI-written summary · about

" chapters (18)

1. 0:00Start
2. 7:27Advantages of the New Compressed Sensing Framework
3. 11:55Simulations
4. 12:42An Example of "Single Pixel Camera" Application
5. 14:43Summary of Contributions on Compressed Sensing
6. 15:20Other Applications of Stable Random Projections
7. 18:23Data Streams and Entropy Estimation
8. 18:55Anomaly Detection of Network Traffic
9. 19:31Entropy Estimation Using Derivatives
10. 22:1210 Samples Provide Good Estimates
11. 30:35A Popular Solution Based on Normal Random Projections
12. 30:52Very Sparse Random Projections
13. 31:14A Running Example Using (Small) Webspam Data
14. 32:30Binary Data Vectors and Sets
15. 35:08Experiments on Webspam Data: Testing Accuracy
16. 36:07One Permutation Hashing
17. 36:35Summary of Contributions on b-Bit Minwise Hashing
18. 37:19Conclusion

" related talks

• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 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
• 36mThe unreasonable effectiveness of feature hashingGianluca Campanella · PyData London 2019
• 26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement ProcessesSidharth Jaggi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 01h 02mTheory and Big DataRavi Kannan · Big Data Boot Camp 2013
• 01h 34mAlgorithmic High-Dimensional Geometry IAlex Andoni · Big Data Boot Camp 2013