Statements (30)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
probabilistic data structure
|
| gptkbp:application |
natural language processing
data mining database systems network traffic measurement |
| gptkbp:citation |
Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the Count-Min Sketch and its applications. Journal of Algorithms, 55(1), 58-75.
|
| gptkbp:error_bound |
εN with probability 1-δ
|
| https://www.w3.org/2000/01/rdf-schema#label |
Count-Min Sketch
|
| gptkbp:introduced |
gptkb:Graham_Cormode
gptkb:S._Muthukrishnan 2005 |
| gptkbp:limitation |
no deletion support
overestimates counts |
| gptkbp:numberOfLocations |
integer counters
|
| gptkbp:parameter |
depth (d)
width (w) |
| gptkbp:publishedIn |
gptkb:Journal_of_Algorithms
|
| gptkbp:query_type |
point query
range query |
| gptkbp:relatedTo |
gptkb:Bloom_filter
Count Sketch |
| gptkbp:spaceComplexity |
O(w × d)
|
| gptkbp:time_complexity_(query) |
O(d)
|
| gptkbp:time_complexity_(update) |
O(d)
|
| gptkbp:usedFor |
stream processing
approximate counting frequency estimation |
| gptkbp:uses |
hash functions
|
| gptkbp:bfsParent |
gptkb:Graham_Cormode
|
| gptkbp:bfsLayer |
7
|