# Data structure to estimate the frequency of low frequency elements

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
• Text format: do you mean chars ? Jan 25 at 16:15
• How large are your numbers ? And how many of them ? Jan 25 at 16:15
• It makes little sense to use 80 threads. The processor cannot run in parallel more than the number of cores ! Jan 25 at 16:16
• @YvesDaoust, I have 96 cores on our server. Yeah chars (hence UInt8). For my current test file I have 25B numbers, of which 22M are unique, and all are in the UInt32 range. Ideally this should be scalable to handle ~1B unique and ~1 trillion numbers. I think, usually the ones satisfying<=100 are around 20M Jan 25 at 16:25
• It they are in the 32 bits range, then keep an array of counters. That will fit in 4 GB of memory (8 bits counters, with saturation). You can avoid saturation but that will cost you 64 bits counters, hence 32 GB. Jan 25 at 16:31

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.

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.

• Thanks a lot! Smart idea to use the hashmap to cover larger numbers. Gonna give this a try :) Jan 26 at 4:09
• You can have an array A for all numbers below 500M, and a hashmap for all larger numbers If the density is as flat for wider ranges as that shown for here stopping at around 5e8, such a split won't help. Establishing count ≤ t, t < max. value of a byte, the table would "just" consume range bytes using saturating arithmetic or stopping increment at t+1. Jan 26 at 7:24
• @greybeard, I agree on all counts. Yes, saturating arithmetic is another option, which uses more time in exchange for less space. My sense is that 2GB is so small that it may not be worth worrying about the difference between 2GB vs 500MB, but either choice is perfectly valid. This answer is based on data that follows the distribution shown in the question. The plot in the question shows that the numbers are smaller than 5e8, and 5e8 = 500M. If the data follows some other distribution then this answer might not be useful.
– D.W.
Jan 26 at 7:32
• @greybeard could you explain how I would map the numbers to the 500MB range? Are you talking about a hashtable where the value (count) is UInt8 for example? Jan 26 at 8:29
• (agree on small factors in memory requirement may be insignificant (without significant difference in frequency of access to slower levels in memory hierarchy)) Based on your plot, all frequencies will fit into a 32-bit int staring at the plots once more, the counts seem to taper out at about 20000($10^{4.3}$). Note there is a sign to the exponent in the second plot, + only in the bottom line: While I still don't have an intuition what a density of 1e-9 or 2.02e-9 means or why it would be "lower" at both ends of the range, the latter is not much bigger than the reciprocal of $2^{31}$. Jan 28 at 7:15

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.

• Not sure if I get it😅, but to merge sort I would first need to extract all numbers and then sort them (rather than being able to stream them) Jan 26 at 12:49
• To remember why that doesn't strictly apply, familiarity with merge sorting multi-tape data with a limited number of tape drives would help. Jan 26 at 13:27
• Unless spending endless CPU-hours/kWh on this, it would be a pretty elaborate experiment to implement and tune both approaches. Jan 26 at 14:55
• @CodeNoob, I think the proposal is that each of the 80 threads mergesorts all of the numbers it receives, then you merge them. See en.wikipedia.org/wiki/External_sorting for how to do the sorting without needing to store them all in RAM at any one time.
– D.W.
Jan 26 at 17:55
• @D.W. thanks for the simplification :) I'm familiar with merge sorting from multiple files. I will give that a try Jan 26 at 18:37