3
$\begingroup$

I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer while still using significantly less space than a traditional approach.

Would the following work to compute the exact (not approximate) distinct elements count of a huge multiset?

The idea is to use a Bloom filter twice, first processing the data one way, and then in reverse and additionally using a map (whose size is much smaller than the huge multiset -- this property is provided by the Bloom filter).

1st pass
create an empty bloom filter
create an empty map
for each element from the multiset
    if already in the bloom add to the map with key element / value 0
    else add to the bloom

Second pass is nearly identical but elements from the huge multiset are processed in reverse (multiset doesn't need to be an ordered set: it simply needs to have its elements iterated from the end to its beginning).

2nd pass
    empty the bloom filter (but not the set)
    for each element from the multiset (but processed this time in reverse order)
        if already in the bloom add to the map with key element / value 0
        else add to the bloom

At this point the map contains a list of potentially, but not necessarily, clashing entries in the multiset. So the entries are all set to zero.

3rd pass
   cnt = 0
   for each element in the multiset
       if present in the map, increment value in that map for that key
       else increment cnt

Exact cardinality is now equal to "cnt + nb entries in the map whose value is 1 or greater".

This requires three passes but uses space identical to a Bloom filter plus a map to count the x% of entries the Bloom filter couldn't answer if they were present or not.

I hacked a quick proof of concept and did some generative testing and it seemed to give the correct answer but I'm really not sure.

Is it possible to compute the exact distinct element count of a huge multiset this way?

$\endgroup$
  • $\begingroup$ Using cardinality is misleading. You're after the number of distinct elements in the multiset. $\endgroup$ – Yuval Filmus Apr 4 at 14:53
  • $\begingroup$ Can you explain what you mean by map? Also, what is the traditional approach, how much space does it use, and how much space does your proposed method use? $\endgroup$ – Yuval Filmus Apr 4 at 14:55
  • $\begingroup$ How does your method compare to using a dynamically resizing hash table? For each element, we check whether it is already found in the hash table, and if not, put it there, and increment a counter. $\endgroup$ – Yuval Filmus Apr 4 at 14:56
  • $\begingroup$ @YuvalFilmus: but I wrote the space usage in the question: it's the same space usage as a Bloom filter uses for space-efficiency usage plus an associative array used to count the elements for which the Bloom Filter couldn't answer "definitely not in set". The advantage being the space efficiency of the Bloom Filter and a hash table about 1% of the size of the size if counting using only a hash table? $\endgroup$ – Cedric Martin Apr 4 at 15:07
  • 1
    $\begingroup$ You're asking whether your algorithm is correct. Have you tried proving that it is correct? Where did you get stuck? $\endgroup$ – Yuval Filmus Apr 4 at 15:09
3
$\begingroup$

Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map.

Suppose that your elements are $x_1,\ldots,x_n$. For a given hash $h$, let $x_{i_1},\ldots,x_{i_\ell}$ be the elements hashing to $h$ (in order). If $\ell = 1$, then the elements won't be added to the map in the first or second step. Otherwise, elements $x_{i_2},\ldots,x_{i_\ell}$ will be added to the map in the first step, and elements $x_{i_{\ell-1}},\ldots,x_{i_1}$ will be added to the map in the second step.

In total, this shows that after the first two steps, the map will contain all elements whose hash appears more than once.

After the third step, cnt will contain the number of elements whose hash appears exactly once. All of these elements are distinct, and also distinct from the elements in the map. You then add to cnt the number of elements present in the map, and so obtain the number of distinct elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.