Python implemention of frugal streaming algorithms for estimating quantiles. See: http://arxiv.org/abs/1407.1121

frugal.py

class frugal1_estimator(object):
    def __init__(self, qtile):
        self.qtile_target = qtile
        self.m = 0.0

    def add(self, new_data):
        r = random.random()
        if new_data > self.m and r > (1.0 - self.qtile_target):
            self.m += 1
        elif new_data < self.m and r > self.qtile_target:
            self.m -= 1


class frugal2_estimator(object):
    def __init__(self, qtile):
        self.qtile_target = qtile
        self.m = 0.0
        self.step = 1
        self.sign = 1

    def add(self, new_data):
        r = random.random()
        if new_data > self.m and r > (1.0 - self.qtile_target):
            self.step += (1 if self.sign > 0 else -1)
            if self.step > 0:
                self.m += math.ceil(self.step)
            else:
                self.m += 1.0
            if self.m > new_data:
                self.step += (new_data - self.m)
                self.m = new_data
            if self.sign < 0 and self.step > 1:
                self.step = 1
            self.sign = 1
        elif new_data < self.m and r > self.qtile_target:
            self.step += (1 if self.sign < 0 else -1)
            if self.step > 0:
                self.m -= math.ceil(self.step)
            else:
                self.m -= 1.0
            if self.m < new_data:
                self.step += (self.m - new_data)
                self.m = new_data
            if self.sign > 0 and self.step > 1:
                self.step = 1
            self.sign = -1