Sampling Algorithms to Count Frequent Patterns in Graphs
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Develops and proves wedge-sampling estimators that need ~38k independent samples for 1% error and 99% confidence, implements a streaming version using an edge reservoir and wedge reservoir (20k each in experiments), and runs a Hadoop prototype that counts triangles on Orkut (200M edges) using kilobytes of memory. Streaming unbiasing relies on the birthday paradox and randomized hashing for repeated edges; empirical errors are consistently small and run times scale roughly linearly.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:27Sampling and Streaming Algorithms
- 1:57Graphs
- 4:48Sampling
- 5:18Experiment
- 7:35Sampling Wages
- 8:58Large Graphs
- 10:10Experiments
- 11:39Streaming
- 13:23Beulah
- 15:01Birthday Paradox
- 18:42Results
- 20:23Multiple Edges
- 23:06Conclusion
related talks
01h 03mData Streams II
29mApplying Randomized Methods for Zonotope Enumeration and...
42mWhen Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 07mMarrying Graph Convergence and Cascade Models
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
50mSeeding with Costly Network Information
31mSome Novel Computational Models to Think About