Medium
Error guarantee of a count-min sketch point query
A count-min sketch has d rows of w counters, each row with its own independent hash function. Each stream item increments one counter per row (counts only ever increase), and a point query for item x returns the minimum, over the d rows, of the counter x hashes to. The sketch is sized as w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉. Let N be the total count over the whole stream, a the true count of x, and â the query's answer. Which statement is the sketch's guarantee?
33 of 46 in Data Structures & Algorithms