Space efficient technique for estimating cardinality using probabilistic data structure

Abstract

Methods and technologies are disclosed for the sketch efficient estimation of large-scale multi-sets in distributed, stream-oriented environments. Sketch updates are idempotent and commutative, to support duplicate set elements and varying element sequences. They are also mergeable to support distributed sketch recording. The recording process uses stepwise approximated geometric distributions, efficiently generated from NLZ values of received sketch updates, by using only multiplications with powers of two and integer additions. Sketch registers are subdivided into a portion storing an observed max update value for the register, and a portion storing set of flag bits indicating observed next smaller update values for the register. A Max Likelihood base sketch data evaluation, based on the assumption of statistically independent sketch registers is proposed. The limited number of different probabilities created by the stepwise approximated geometric distributions leads to a Max Likelihood function with coefficients that can be calculated solely with integer arithmetic.