Overview
Count-Min Sketch is a data structure that maintains an invariant that supports efficient queries, updates, summaries, or indexing. It trades implementation complexity for faster or more compact operations on repeated workloads.
CoreSource checked
Count-Min Sketch
Count-Min Sketch organizes data around a query, update, ordering, or approximation invariant.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Data Structure
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
invariantquery operationupdate operationstorage layout
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use Count-Min Sketch when repeated operations benefit from its invariant or summary structure.
- Use it when operation mix is stable enough to justify maintaining the structure.
When Not to Use
- Avoid when the workload is too small to justify the added invariant maintenance.
- Avoid when updates violate assumptions behind the query guarantees.
What It Does
- Organizes data for efficient access
- Maintains structural invariants
- Supports queries, inserts, deletes, or summaries
Use Cases
- Indexing data
- Caching
- Fast query processing
Inputs
- Items, keys, or graph records
- Queries or updates
Outputs
- Stored structure
- Query result
- Updated structure
Key Formulas (1)
Count estimate
estimate(x) = min(tablei[hashi(x)])
estimate(x) = min(table_i[hash_i(x)])Uses the smallest hashed counter as an upper-bound estimate.
Pseudocode
- 1.Initialize the structure and invariants
- 2.Apply insert, query, update, or delete operations
- 3.Rebalance, hash, summarize, or split nodes as needed
- 4.Return the query result or updated structure
Canonical Example
- Input
- operations = insert A, insert B, query A
- Output
- updated structure and query result
- Explanation
- Count-Min Sketch maintains its invariant while answering the requested operation.
Implementation Notes
- Write invariant checks for debug builds.
- Benchmark the expected query/update mix instead of isolated operations only.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Breaking the invariant during an update can make later queries silently wrong.
- Ignoring adversarial or skewed input can erase expected performance.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure changing as items are inserted, queried, or removed.
Step 1 of 4: Initialize the structure and invariants
data-structureNotes
Count-Min Sketch operates in O(log n) time and O(n) space within the Data Structure family. Key governing relation: estimate(x) = min(table_i[hash_i(x)]). Often compared with Bloom Filter and Hash Table.
Sources (1)
What each reference supports for this entry.
Count-Min Sketch
PaperOriginal reference for count-min sketch frequency estimation, hash tables, and error bounds.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toBloom Filter
Data Structures · Core
Count-Min Sketch organizes data with different query and update tradeoffs than Bloom Filter.
Compare with thisRelationships
View full relationship pageAlternative toBloom Filter
Count-Min Sketch organizes data with different query and update tradeoffs than Bloom Filter.
Related Algorithms
Tags
Data Structure