Count-Min Query Upper Bound

Problem

Return the theoretical upper bound on a Count-Min estimate for a sketch of width width.

After total increments the true count is at most estimate + e * total / width, where e is Euler's number. Return the estimate itself when width is non-positive or total is negative.

Hint

The additive error term is e * total / width, so wider sketches tighten the bound.

Test cases

case 1

in: [5,100,1000]

expected: 32.182818284590454

case 2

in: [0,10,100]

expected: 27.18281828459045

case 3

in: [5,0,100]

expected: 5

case 4

in: [12,7,0]

expected: 12

case 5

in: [3,50,250]

expected: 16.591409142295227

Starter codePython

import math


def cms_query_upper_bound(estimate, width, total):
    # Your code here
    pass

5 test cases · run your code against them in the editor