turnstile-stream · research · also Turnstile model, Strict turnstile model, General turnstile model

Turnstile stream

A turnstile stream updates a frequency vector with positive or negative increments, allowing earlier contributions to be reduced or reversed.

Related Observatory article: Read on hesela.com

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

  1. Cormode, Garofalakis, Haas and Jermaine. Synopses for Massive Data. Author manuscript, sections 5.2 and 5.3.2. (accessed 2026-11-20)
  2. Cormode and Muthukrishnan. The Count-Min Sketch and its Applications. Author preprint, 16 December 2003, sections 2-4.1. (accessed 2026-11-20)
  3. Hesela. Exact signed-frequency and expiration examples, with executable tests. Constructed finite maps, not random-hash validation. (accessed 2026-11-20)
Sources & caveats
  • Frequency means the accumulated per-key weight, which can be a signed balance in the general model; it is not necessarily a nonnegative event count. [1]
  • The exact expiration example is an information-loss construction, not a claim about a named windowing implementation. [3]

JSON: /data/terms/turnstile-stream.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Turnstile stream. Hesela. 2026-11-20. https://hesela.dev/terms/turnstile-stream/