Greenwald-Khanna Invariant Check

Problem

Check whether a Greenwald-Khanna quantile summary satisfies its rank-error invariant.

summary is a list of [value, g, delta] tuples and the invariant requires every g >= 1 and g + delta <= floor(2 * epsilon * n), where n is the stream length. Return True when all tuples pass, and False for non-positive epsilon or negative n.

Hint

The band width g + delta of every tuple must stay inside the global rank-error budget.

Test cases

case 1

in: [[[1,1,0],[3,1,0]],0.1,100]

expected: true

case 2

in: [[[1,1,0],[3,1,40]],0.1,100]

expected: false

case 3

in: [[[1,0,0]],0.1,10]

expected: false

case 4

in: [[],0.1,0]

expected: true

case 5

in: [[[2,2,8]],0.05,100]

expected: true

Starter codePython

def gk_invariant_holds(summary, epsilon, n):
    # Your code here
    pass

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