You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
feat(streaming): Count-Min sketch with fixed-query accuracy #1201
Start the streaming/sketching direction with an executable insertion-only Count-Min sketch and its fixed-query accuracy theorem.
Scope: natural-number weighted updates; positive row and bucket counts; exact update/concatenation/merge invariants for the same hash bank; no underestimation; independently sampled universal-hash rows; an explicit additive-error/failure bound (in particular width * epsilon >= 2 gives failure at most 2^(-depth)). Reuse the existing universal-hashing, finite probability, and concentration APIs.
The source is Cormode–Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications,” Section 3 and Section 4.1, Theorem 1: https://www.cs.ox.ac.uk/people/graham.cormode/pubs/papers/cm-full.pdf
The source theorem bounds a point estimate between its true frequency and that frequency plus epsilon times total mass, with probability at least 1-delta. The stream and queried item are fixed independently of the sampled hashes. Our initial stream model is insertion-only.
Acceptance: checked Lean statements for deterministic correctness and probability, a concrete instantiated hash family/example, meaningful tests covering collisions and updates, explicit counter/seed representation scope, source attribution, and the repository validation gates. Runtime/space claims must describe the representation actually proved.
This is the first milestone of a broader streaming program. Communication lower-bound transfer, CountSketch/AMS, heavy hitters, and turnstile extensions remain separate follow-ups. The wider direction is not completed by this milestone.
Owner: worker-chatgpt-streaming-cb399a98, branch feat/streaming-count-min-cb399a98. AI-assisted implementation and agent review; maintainer/coordinator review required before merge.
active — worker-chatgpt-streaming-cb399a98, branch feat/streaming-count-min-cb399a98, starting from c09dcb2. I own integration and validation; delegated workers are checking the deterministic sketch model, probability proof, and isolated Lean setup. The first PR will cover this Count-Min milestone; the broader streaming program remains open.
active — worker-chatgpt-streaming-cb399a98: implementation and strict local checks are complete in #1206. The final revision includes the executable sketch, program-level accuracy, concrete hash instance, checked clients, and guide. Full hosted CI is running; validation and review evidence are maintained in the PR.
awaiting review — worker-chatgpt-streaming-cb399a98: #1206 is ready at 6b248cc. All six required Lean CI gates and the guide build passed; the PR records validation, source mapping, and the non-authoring agent review. Independent coordinator review is requested. The broader streaming/sketching directions remain in ROADMAP.md.
Activity
SamuelSchlesinger commentedon Oct 26, 2026
active — worker-chatgpt-streaming-cb399a98, branch feat/streaming-count-min-cb399a98, starting from c09dcb2. I own integration and validation; delegated workers are checking the deterministic sketch model, probability proof, and isolated Lean setup. The first PR will cover this Count-Min milestone; the broader streaming program remains open.
feat(streaming): add Count-Min fixed-query accuracy
SamuelSchlesinger commentedon Oct 26, 2026
active — worker-chatgpt-streaming-cb399a98: implementation and strict local checks are complete in #1206. The final revision includes the executable sketch, program-level accuracy, concrete hash instance, checked clients, and guide. Full hosted CI is running; validation and review evidence are maintained in the PR.
SamuelSchlesinger commentedon Oct 26, 2026
awaiting review — worker-chatgpt-streaming-cb399a98: #1206 is ready at 6b248cc. All six required Lean CI gates and the guide build passed; the PR records validation, source mapping, and the non-authoring agent review. Independent coordinator review is requested. The broader streaming/sketching directions remain in ROADMAP.md.
feat(streaming): add Count-Min fixed-query accuracy (cslib-community#…