# Theta intersections: preserve uncertainty when the sample is empty A zero cardinality estimate can mean **no sampled evidence of overlap**, not disjoint source sets. Carry the sketch's uncertainty state through storage and downstream set operations. Use exact identities for decisions that must never discard a live block. This packet extends Hesela's [HyperLogLog](https://hesela.dev/terms/hyperloglog/) and [sampling-design](https://hesela.dev/terms/sampling-design/) material. HLL register maxima support unions, but they do not supply this retained-hash intersection state. [Count-Min](https://hesela.dev/terms/count-min-sketch/) answers a different question: approximate frequency of a supplied key. ## What was executed Apache DataSketches Python **5.2.0**, on Python 3.12, with NumPy 2.2.6 as its package dependency. The actual set operations use the library's compiled code. Inputs are synthetic ascending Python integers in half-open ranges [start, stop). One distinct integer represents one logical chunk identity, not variable-sized bytes or a physical allocation. No storage device, backup engine or production dataset was measured. Default controls use seed 9001, p=1 and lg_k=5 (nominal k=32). This is a nominal retention parameter, not a promise that every untrimmed state retains at most 32 hashes. Compacting orders entries; these runs do not call trim. [run.py](run.py) contains every input and [results.json](results.json) every result. | Control | Exact overlap | Estimate | Upper bound, setting 2 | | --- | ---: | ---: | ---: | | [0,10) intersect [10,20), lg_k=5 | 0 | 0 | 0 | | [0,10) intersect [9,19), lg_k=5 | 1 | 1 | 1 | | [0,10000) intersect [9999,19999), lg_k=5 | 1 | 0 | 1092 | | Same rare overlap, lg_k=12 | 1 | 0 | 5 | | Same rare overlap, lg_k=14, exact mode | 1 | 1 | 1 | The first zero is an exact empty state: theta=1 and empty=true. The rare-overlap zero has theta=0.0034599747178553327 and empty=false. Both expose zero retained entries. Larger retention narrows uncertainty, but does not guarantee that a particular shared identity is sampled. The library APIs call these approximate bounds at a selected number of standard deviations, here 2. They are not deterministic maximum counts, nor a posterior probability that the true count lies in the displayed interval. The source uses a one-sided tail parameter approximately 0.02275026 at setting 2. Calling it an exact 95% guarantee would overstate the contract. [API][api] [bounds code][bounds] The same-input control is deliberately retained in the raw results: its true overlap is 10000 and its lower bound is about 10021.72. An individual interval can miss truth. These examples do not estimate repeated-sampling coverage. ## Where the information is lost Theta sketches retain hashes below a threshold. Intersections align to the smaller threshold, intersect the retained hashes, then estimate r/theta. The framework's guarantees assume ideal random hashing and suitable threshold-selection rules, not an arbitrary data-dependent sampler. [Framework sections 2.1-2.4 and 3.7][framework] The official state model distinguishes an exact empty result from a sampled zero. The C++ implementation only marks a zero-match intersection empty when its threshold is exact, unless an input already certifies emptiness. [State model][corner] [pinned implementation][intersection] The native tests confirm that compact serialization and deserialization preserve the rare result's threshold, flags, estimate and bounds. Union with an exact empty sketch also preserves its uncertainty. A deliberately incorrect consumer that replaces any zero-retained result with a fresh empty sketch instead changes the upper bound from 1092 to 0. This is an application interpretation error, not a discovered defect in Apache DataSketches. The reverse implication also fails: empty=false does not prove a nonempty underlying set. In the native self-difference A minus A, the exact difference is zero but the library conservatively returns empty=false and upper bound 959. Do not relabel that flag as a Boolean answer to "do the originals overlap?" ## Sampling resolution in a controlled regime For a **fixed** sampling probability p and c common identities, independent uniform hashes give: P(no common identity retained) = (1-p)^c P(at least one retained) = 1-(1-p)^c This follows by requiring each of the c shared hashes to miss the threshold. The hash for a shared identity is the same in both inputs; it is not sampled independently twice. Consequently the detection probability is not based on p^2. The second experiment deliberately stays in this fixed-threshold regime: lg_k=12, p=1/64, two sets of 10000 identities, seeds 1 through 256. Every run checks that both inputs and the result keep theta exactly 1/64. | Common identities c | Zero-retained results / runs | Observed fraction | Ideal-hash probability | | --- | ---: | ---: | ---: | | 1 | 251 / 256 | 98.05% | 98.44% | | 16 | 193 / 256 | 75.39% | 77.73% | | 64 | 95 / 256 | 37.11% | 36.50% | These are a deterministic seed sensitivity sweep, not a random sample of seeds or independent empirical replicates of a storage workload. No significance, population prevalence or confidence interval is inferred from these fractions. All 768 rows, including nonzero estimates, are available in results.json. The same seed list is reused across groups; the groups are not independent. For c=1, a fixed-p sampler needs p>=0.95 to make its ideal-model miss probability at most 5%. Small cardinality summaries are therefore a poor proof of "absolutely no shared chunks." This design calculation is separate from the adaptive-threshold controls. Substituting an observed adaptive theta into the fixed-p formula is not justified by this experiment. ## Engineering consequences - Preserve serialized state, format version, encoding contract and hash seed; a matching short seed hash is not a complete compatibility or authenticity proof. - Include result bounds in overlap reports. Input-size precision does not carry unchanged into a much smaller intersection. [Accuracy guidance][accuracy] - Distinguish unobserved overlap, exact empty offered sets and missing input. Neither sketch mode establishes that ingestion captured the intended source. - Use exact source manifests or reference checks for garbage collection and deduplication correctness. Approximate cardinality is capacity-planning evidence, not a list of safe deletion candidates. - Distinct overlap counts do not determine shared bytes when chunk sizes differ. ## Reproduce Create an isolated environment and install the pinned dependencies: python3 -m venv .venv .venv/bin/pip install --only-binary=:all: -r requirements.txt .venv/bin/python -B run.py --check .venv/bin/python -B -m unittest discover -s . -p test_run.py .venv/bin/python -B -O -m unittest discover -s . -p test_run.py Run from this directory. Native replay requires the dependencies; only the packet itself is included in [reproduction.zip](reproduction.zip), not third-party binaries. Installation needs package access or a pre-populated wheel cache. Use --write to regenerate deterministic results. Compare the installed versions and wheel provenance with [environment.json](environment.json). [Sources and precise reviewed locations](sources.json) separate the theoretical paper, live documentation and immutable implementation revision. The project version tag's CMake file references C++ 5.2.0; that correspondence is not a claim to have rebuilt or attested the PyPI wheel. Its SHA-256 and installed extension hash identify the executed artifact. No claim of new algorithm, performance replication, fleet reliability, SEO gain or deployment accompanies this packet. [framework]: https://doi.org/10.4230/LIPIcs.ICDT.2016.6 [corner]: https://datasketches.apache.org/docs/Theta/ThetaSetOpsCornerCases.html [api]: https://apache.github.io/datasketches-python/main/distinct_counting/theta.html [accuracy]: https://datasketches.apache.org/docs/Theta/ThetaAccuracyPlots.html [intersection]: https://github.com/apache/datasketches-cpp/blob/de8553ba372e618382c2e7b44b0ffc9422b9458c/theta/include/theta_intersection_base_impl.hpp [bounds]: https://github.com/apache/datasketches-cpp/blob/de8553ba372e618382c2e7b44b0ffc9422b9458c/common/include/binomial_bounds.hpp