Turnstile stream
A turnstile stream updates a frequency vector with positive or negative increments, allowing earlier contributions to be reduced or reversed.
Strict turnstile requires every underlying frequency to stay nonnegative throughout the stream; general turnstile allows negative balances. Insertion-only streams are the special case with no negative increments. These conditions concern the true vector, not merely nonnegative sketch buckets. [1]
Ordinary additive Count-Min with its minimum estimator supports valid deletions under nonnegative true frequencies. A negative balance can invalidate its one-sided bound. The original paper also gives a median estimator for the general case, so signed updates are not exclusive to CountSketch. [2]
A negative increment is an arithmetic operation, not evidence of a legitimate deletion. In the constructed histories x at time 0 then y at 10, and y at 0 then x at 10, the final vectors agree. Expiring time 0 leaves different keys. A timestamp-free summary cannot identify that expired contribution. [3]
Relations
- related
- CountSketch, Count-Min sketch
Citations
- Cormode, Garofalakis, Haas and Jermaine. Synopses for Massive Data. Author manuscript, sections 5.2 and 5.3.2.
- Cormode and Muthukrishnan. The Count-Min Sketch and its Applications. Author preprint, 16 December 2003, sections 2-4.1.
- Hesela. Exact signed-frequency and expiration examples, with executable tests. Constructed finite maps, not random-hash validation.