A framework for estimating stream expression cardinalities¶
Dasgupta, A., Lang, K., Rhodes, L., & Thaler, J. (2016). A framework for estimating stream expression cardinalities. International Conference on Database Theory (ICDT 2016), 48, 1-6.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Cardinality
- Mapped back to the six-component structural signature: the carrier collections are the customer's data tables and event streams (each with billions of rows or events); the equinumerosity bijection is implicit in the hash function feeding the HLL or Theta sketch (uniform hashing approximates a bijection from the data domain to a register-index domain, justifying the sketch's accuracy); the cardinal number as equivalence class is the estimated distinct-count register-pattern interpretation; cardinal arithmetic is realised in the sketch-merge, sketch-intersection, and sketch-union operations (these are direct cardinal-arithmetic implementations); ordering by injection plus Schröder-Bernstein is implicit in the comparison operations the optimiser performs to choose join orders (smaller-cardinality input on the build side of a hash join, larger on the probe side — a pure cardinal-ordering decision); and the use is the entire query-planning, schema-design, and customer-facing-API stack that depends on cardinality estimates being accurate and cheap.
This sourceIdentifies a broad class of unbiased distinct-count estimators over set-expression streams with strong variance bounds (the Theta-sketch foundations used in Apache DataSketches), grounding mergeable/intersectable sketches as cardinal-arithmetic implementations.
Supported in partVerified against the work's full text
The paper supplies mergeable, intersectable distinct-count sketching over stream set-operations; it does not state the six-component mapping or the application details this claim adds.
“sketching, data stream algorithms, mergeability, distinct elements, set operations}”
- Mapped back to the six-component structural signature: the carrier collections are the customer's data tables and event streams (each with billions of rows or events); the equinumerosity bijection is implicit in the hash function feeding the HLL or Theta sketch (uniform hashing approximates a bijection from the data domain to a register-index domain, justifying the sketch's accuracy); the cardinal number as equivalence class is the estimated distinct-count register-pattern interpretation; cardinal arithmetic is realised in the sketch-merge, sketch-intersection, and sketch-union operations (these are direct cardinal-arithmetic implementations); ordering by injection plus Schröder-Bernstein is implicit in the comparison operations the optimiser performs to choose join orders (smaller-cardinality input on the build side of a hash join, larger on the probe side — a pure cardinal-ordering decision); and the use is the entire query-planning, schema-design, and customer-facing-API stack that depends on cardinality estimates being accurate and cheap.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 1 citation: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:e6ecbc561677 · see in the full table