Count-distinct problem

Template:Short description In computer science, the count-distinct problem^[1] (also known in applied mathematics as the cardinality estimation problem) is the problem of finding the number of distinct elements in a data stream with repeated elements. This is a well-known problem with numerous applications. The elements might represent IP addresses of packets passing through a router, unique visitors to a web site, elements in a large database, motifs in a DNA sequence, or elements of RFID/sensor networks.

Formal definition

Instance: Consider a stream of elements

x_{1}, x_{2}, \dots, x_{s}

with repetitions. Let

n

denote the number of distinct elements in the stream, with the set of distinct elements represented as

{e_{1}, e_{2}, \dots, e_{n}}

.

Objective: Find an estimate

\hat{n}

of

n

using only

m

storage units, where

m ≪ n

.

An example of an instance for the cardinality estimation problem is the stream: $a, b, a, c, d, b, d$ . For this instance, $n = | {a, b, c, d} | = 4$ .

Naive solution

The naive solution to the problem is as follows:

 Initialize a counter, Template:Mvar, to zero, Template:Nowrap
 Initialize an efficient dictionary data structure, Template:Mvar, such as hash table or search tree in which insertion and membership can be performed quickly.  
 Template:Nowrap, a membership query is issued. 
     Template:Nowrap Template:Nowrap
         Template:Nowrap
         Increase Template:Mvar by one, Template:Nowrap
     Otherwise Template:Nowrap do nothing.
 Template:Nowrap

As long as the number of distinct elements is not too big, Template:Mvar fits in main memory and an exact answer can be retrieved. However, this approach does not scale for bounded storage, or if the computation performed for each element $x_{i}$ should be minimized. In such a case, several streaming algorithms have been proposed that use a fixed number of storage units.

HyperLogLog algorithm

Template:Main

Streaming algorithms

To handle the bounded storage constraint, streaming algorithms use a randomization to produce a non-exact estimation of the distinct number of elements, $n$ . State-of-the-art estimators hash every element $e_{j}$ into a low-dimensional data sketch using a hash function, $h (e_{j})$ . The different techniques can be classified according to the data sketches they store.

Min/max sketches

Min/max sketches^[2]^[3] store only the minimum/maximum hashed values. Examples of known min/max sketch estimators: Chassaing et al.^[4] presents max sketch which is the minimum-variance unbiased estimator for the problem. The continuous max sketches estimator^[5] is the maximum likelihood estimator. The estimator of choice in practice is the HyperLogLog algorithm.^[6]

The intuition behind such estimators is that each sketch carries information about the desired quantity. For example, when every element $e_{j}$ is associated with a uniform RV, $h (e_{j}) \sim U (0, 1)$ , the expected minimum value of $h (e_{1}), h (e_{2}), \dots, h (e_{n})$ is $1 / (n + 1)$ . The hash function guarantees that $h (e_{j})$ is identical for all the appearances of $e_{j}$ . Thus, the existence of duplicates does not affect the value of the extreme order statistics.

There are other estimation techniques other than min/max sketches. The first paper on count-distinct estimation^[7] describes the Flajolet–Martin algorithm, a bit pattern sketch. In this case, the elements are hashed into a bit vector and the sketch holds the logical OR of all hashed values. The first asymptotically space- and time-optimal algorithm for this problem was given by Daniel M. Kane, Jelani Nelson, and David P. Woodruff.^[8]

Bottom-m sketches

Bottom-m sketches ^[9] are a generalization of min sketches, which maintain the $m$ minimal values, where $m \geq 1$ . See Cosma et al.^[2] for a theoretical overview of count-distinct estimation algorithms, and Metwally ^[10] for a practical overview with comparative simulation results.

Python Implementation of Knuth's CVM Algorithm

def algorithm_d(stream, s):
    m = len(stream) # We assume that this is given to us in advance.
    t = -1 # Note that Knuth indexes the stream from 1. 
    p = 1
    a = 0
    buffer = []
    while t < (m - 1):
        t += 1
        a = stream[t]
        u = uniform(0,1)
        buffer = list(filter(lambda x : x[1] != a, buffer)) 
        if u < p:
            if (len(buffer) < s):
                buffer.append([u, a])
            else:
                buffer = sorted(buffer)
                p = max(buffer[-1][0],u)
                buffer.pop()
                buffer.append([u, a])
    return len(buffer) / p

CVM Algorithm

Compared to other approximation algorithms for the count-distinct problem the CVM Algorithm^[11] (named by Donald Knuth after the initials of Sourav Chakraborty, N. V. Vinodchandran, and Kuldeep S. Meel) uses sampling instead of hashing. The CVM Algorithm provides an unbiased estimator for the number of distinct elements in a stream,^[12] in addition to the standard (ε-δ) guarantees. Below is the CVM algorithm, including the slight modification by Donald Knuth. ^[12]

 Template:Nowrap
 Initialize max buffer size  $s$ , where  $s \geq 1$ 
 Initialize an empty buffer, Template:Mvar  
 Template:Nowrap in data stream  $A$  of size  $n$  do: 
   Template:Nowrap
       Template:Nowrap
   Template:Nowrap
   Template:Nowrap
       Template:Nowrap
           insert  $(a_{t}, u)$  in Template:Mvar
       else
            $(a^{'}, u^{'})$  such that  $u^{'} = \max {u^{″} : (a^{″}, u^{″}) \in B, \forall a^{″}}$  /*  $(a^{'}, u^{'})$  whose  $u^{'}$  is maximum in Template:Mvar */
           If  $u > u^{'}$  then
                $p \leftarrow u$ 
           else
               Replace  $(a^{'}, u^{'})$  with  $(a_{t}, u)$ 
                $p \leftarrow u^{'}$ 
 Template:Nowrap
 Template:Nowrap

The previous version of the CVM algorithm is improved with the following modification by Donald Knuth, that adds the while loop to ensure B is reduced. ^[12]

 Template:Nowrap
 Initialize max buffer size  $s$ , where  $s \geq 1$ 
 Initialize an empty buffer, Template:Mvar  
 Template:Nowrap in data stream  $A$  of size  $n$  do: 
   Template:Nowrap
       Template:Nowrap
   Template:Nowrap
   Template:Nowrap
       Insert  $(a_{t}, u)$  into Template:Mvar
   Template:Nowrap
       Remove every element of  $(a^{'}, u^{'})$  of Template:Mvar with  $u^{'} > \frac{p}{2}$ 
       Template:Nowrap
   Template:Nowrap
   If  $u < p$  then
       Insert  $(a_{t}, u)$  into Template:Mvar
 Template:Nowrap
 Template:Nowrap

Weighted count-distinct problem

In its weighted version, each element is associated with a weight and the goal is to estimate the total sum of weights. Formally,

Instance: A stream of weighted elements

x_{1}, x_{2}, \dots, x_{s}

with repetitions, and an integer

m

. Let

n

be the number of distinct elements, namely

n = | {x_{1}, x_{2}, \dots, x_{s}} |

, and let these elements be

{e_{1}, e_{2}, \dots, e_{n}}

. Finally, let

w_{j}

be the weight of

e_{j}

.

Objective: Find an estimate

\hat{w}

of

w = \sum_{j = 1}^{n} w_{j}

using only

m

storage units, where

m ≪ n

.

An example of an instance for the weighted problem is: $a (3), b (4), a (3), c (2), d (3), b (4), d (3)$ . For this instance, $e_{1} = a, e_{2} = b, e_{3} = c, e_{4} = d$ , the weights are $w_{1} = 3, w_{2} = 4, w_{3} = 2, w_{4} = 3$ and $\sum w_{j} = 12$ .

As an application example, $x_{1}, x_{2}, \dots, x_{s}$ could be IP packets received by a server. Each packet belongs to one of $n$ IP flows $e_{1}, e_{2}, \dots, e_{n}$ . The weight $w_{j}$ can be the load imposed by flow $e_{j}$ on the server. Thus, $\sum_{j = 1}^{n} w_{j}$ represents the total load imposed on the server by all the flows to which packets $x_{1}, x_{2}, \dots, x_{s}$ belong.

Solving the weighted count-distinct problem

Any extreme order statistics estimator (min/max sketches) for the unweighted problem can be generalized to an estimator for the weighted problem .^[13] For example, the weighted estimator proposed by Cohen et al.^[5] can be obtained when the continuous max sketches estimator is extended to solve the weighted problem. In particular, the HyperLogLog algorithm^[6] can be extended to solve the weighted problem. The extended HyperLogLog algorithm offers the best performance, in terms of statistical accuracy and memory usage, among all the other known algorithms for the weighted problem.

References

Template:Reflist

[1] Template:Cite journal

[cosma2011-2] 2.0 ^2.1 Template:Cite journal

[3] Template:Cite book

[4] Template:Cite journal

[edithCohen-5] 5.0 ^5.1 Template:Cite journal

[hyperloglog-6] 6.0 ^6.1 Template:Cite journal

[7] Template:Cite journal

[optimalf0-8] Template:Cite journal

[9] Template:Cite journal

[10] Template:Citation

[11] Template:Cite journal

[:0-12] 12.0 ^12.1 ^12.2 Template:Cite journal

[13] Template:Cite journal

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Count-distinct problem

Contents

Formal definition

Naive solution

HyperLogLog algorithm

Streaming algorithms

Min/max sketches

Bottom-m sketches

Python Implementation of Knuth's CVM Algorithm

CVM Algorithm

Weighted count-distinct problem

Solving the weighted count-distinct problem

See also

References

Navigation menu

Count-distinct problem

Formal definition

Naive solution

HyperLogLog algorithm

Streaming algorithms

Min/max sketches

Bottom-m sketches

Python Implementation of Knuth's CVM Algorithm

CVM Algorithm

Weighted count-distinct problem

Solving the weighted count-distinct problem

See also

References

Navigation menu

Search