Answering Multi-dimensional Queries on Massive Datasets
summary
Built a realtime estimation subsystem that answers multi-dimensional count‑distinct queries by precomputing and storing per‑value sketches and merging them at query time. Uses Apache DataSketches theta sketches computed in Spark (per‑partition sketches merged and persisted), with polyglot clients (Scala for preprocessing, Kotlin for queries). Handles 10–15 dimensions with 1k–100k distinct values; using k=4,096 yields ~3% error for unions while complex intersections show ±10% error. Sketch storage is small (≈24 KB per value, ~30 MB per 1,000 values) and this works in production for campaign reach estimates.
AI-written summary · about
chapters (6)
- 0:00Introduction and background
- 12:01What are sketches
- 18:06Apache DataSketches library
- 22:19Theta sketch framework
- 29:43Solution and implementation
- 30:45Q&A and closing
related talks
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
28mCasting the spell: Druid in practice
33mApache DataSketches
56mSpark-driven Audience counting
47mData Sketches — How to Eat an Elephant Whole (Even If It's Infinite)
01h 13mSketching High-Dimensional Data
01h 09mSketching High-Dimensional Data
42mMergeable Summaries and the Data Sketches Library