Data structure to estimate the frequency of low frequency elements

Question

I have a file with trillions of numbers and I want to get all numbers that have a frequency <=100. These numbers are in text format (UInt8s) so I first have to parse them. As this is slower than reading the bytes to a buffer I have one thread reading the data and 80 threads processing the bytes.

I could give each thread a HashMap that keeps track of the frequencies and later merges them but this will require quite a lot of RAM. As an alternative, I thought of Count-min sketch but as this (likely) overestimates it doesn't seem to suit my purpose.

• Some overestimates are fine
• I don't care about high frequency numbers at all

Is there any data structure/idea that comes to mind to tackle this? Or are hashmaps my only way to go

---

Edit
The numbers come from another tool that generates any number in the UInt64 range. The amount of numbers, as well as how many unique numbers there are will depend on the output of the other tool. For our initial dataset for example, we have 25 billion numbers, of which 22M are unique, and around 18M have a frequency <=100.

Distribution of number frequency

Since these numbers are based on DNA sequences they won't be random and likely very skewed. For this dataset for example:

(Note the x-axis is log10)

Integer range

As I noted they can technically be in the whole UInt64 range. Plotting this for the dataset the numbers are quite uniformly picked along the range, here stopping at around 5e8

So to summarize:

• numbers come from the UInt64 range, and seem to be uniform across this range
• The frequency distribution is highly skewed. In this case 75% of the numbers only occur <= 100

Answer 1

For the dataset you show in the question, all numbers are in the range between 0 to about 500 million. For this dataset, there is an easy efficient algorithm. Build an array $A$ with 500M entries, initialized to zero. Read each line one at a time; when you read the number $x$, increment $A[x]$. At the end, output all numbers $x$ where $A[x] \ge 1$ and $A[x]\le 100$.

How much memory will this take? Based on your plot, all frequencies will fit into a 32-bit int, so you need at most 2GB of memory to store the array.

What about threading? There is something wrong with your implementation if it takes 80 parsing threads to keep up with 1 thread that reads from disk. If you implement it right, with hand-coded C tailored for this task, I expect you should be able to parse as fast as you can read from disk. Your comments indicate that the lines are tab-separated, but it is trivial to split a line by tabs, and it is trivial to convert an integer expressed in decimal to an int. So, based on the information you given I expect that you can replace your 80 parsing threads with a single thread, with proper implementation.

If you cannot, there are other simple methods. For instance, if you really need a lot of parsing threads, you can have 1 thread to read the disk, 80 parsing threads, and 1 thread to increment the array. Each parsing thread would parse numbers, accumulate the parsed numbers into a large buffer, and when that buffer gets full, pass the buffer to the array-incrementing thread.

If you are concerned that occasionally some input line might contain a value that is larger than 500M, it is easy to accommodate this as well. You can have an array A for all numbers below 500M, and a hashmap for all larger numbers. If very few numbers are above 500M, then you'll rarely need to touch the hashmap and performance will be dominated by the time to increment the array.

Answer 2

With unordered data spread over such a range, cache hit rate will be very low indexing a table directly or using a hash function.
One alternative is ordering the data using an algorithm with good locality.
Merge sort has been discussed for elimination of duplicates.
With an "occurrence limit" higher than 1, one would need to keep a count with each value. Encountering the same value in more than one input sequence, add the counts (using saturating arithmetic as appropriate) and add just this merged item to the output.

---

When supplying data to multiple threads from a distribution as flat as shown, see to it that merging frequencies is as simple as concatenation:
split the value range in as many ranges as threads deemed useful.