1
$\begingroup$

I've a large list A of elements. Given another list B of elements, I need B to be sorted by the number of occurences in A (that is, least common to most common in A). A precise count of A would require too much extra memory/disk and an approximate count if sufficient for my needs.

I couldn't find a common solution for this problem, which I suspect is common; I'm not a CS, though.

The way I came up with is to use a counting bloom filter where I increment the counter for every seen element with a chance of 2-c , where c is the current count, initialized to zero. When asked for the approximate count of a given element, I look it up in the bloom filter and return 2c-1 as the result, if it's there at all.

This is Morris Counting, stuck into a Bloom filter. On the plus side, the behavior and memory requirements of the Bloom filter are well known; the counter spends the same amount of storage for the ranges "between 8 and 16" and "between one or two million", which is great for my need. The false positive rate for the Bloom filter and the variance for the counter are known. On the downside: I have no idea what I'm doing. Can I do better?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.