Mergeable Summaries and the Data Sketches Library
summary
Practical, production-ready C++/Java sketches for mergeable summaries and set membership: exact claims include an Alpha/Theta family that consistently beats KMV and adaptive sampling for distinct counts, returning ~4.9M uniques on a 10M-item test while using kilobytes instead of 74MB. Implements a median-chop heavy-hitter sketch that deletes half the keys fast, faster merging for weighted updates, and a new mergeable quantiles algorithm with provable sublinear space/merge bounds.
AI-written summary · about
chapters (11)
- 0:00Start
- 1:17Single machine data processing
- 2:14207 big-data infographics (a meta infographic)
- 3:06The streaming model
- 4:32Unique Counting with Map Reduce
- 7:21Data Mining with Traditional Windowing
- 8:42OLAP with Mergeable Summaries
- 10:53Data Sketches - Open Source Project
- 28:59Problem Definition
- 31:50The basic buffer idea
- 34:39Greenwald-Khanna (GK) sketch
related talks
25mMergeable Summaries for High Scale, High Cardinality Analytics
01h 24mStreaming, Sketching and Sufficient Statistics I
33mApache DataSketches
01h 50mData sketching workshop
31mAnswering Multi-dimensional Queries on Massive Datasets
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
47mData Sketches — How to Eat an Elephant Whole (Even If It's Infinite)
25mHigh on Cardinality, Low on Memory