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
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
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:
So to summarize:
- numbers come from the
UInt64range, and seem to be uniform across this range
- The frequency distribution is highly skewed. In this case 75% of the numbers only occur <= 100