4
$\begingroup$

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:

enter image description here (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 enter image description here

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
$\endgroup$
17
  • $\begingroup$ Text format: do you mean chars ? $\endgroup$
    – user16034
    Jan 25 at 16:15
  • $\begingroup$ How large are your numbers ? And how many of them ? $\endgroup$
    – user16034
    Jan 25 at 16:15
  • 1
    $\begingroup$ It makes little sense to use 80 threads. The processor cannot run in parallel more than the number of cores ! $\endgroup$
    – user16034
    Jan 25 at 16:16
  • $\begingroup$ @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 $\endgroup$
    – CodeNoob
    Jan 25 at 16:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – user16034
    Jan 25 at 16:31

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks a lot! Smart idea to use the hashmap to cover larger numbers. Gonna give this a try :) $\endgroup$
    – CodeNoob
    Jan 26 at 4:09
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Jan 26 at 7:24
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jan 26 at 7:32
  • $\begingroup$ @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? $\endgroup$
    – CodeNoob
    Jan 26 at 8:29
  • $\begingroup$ (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}$. $\endgroup$
    – greybeard
    Jan 28 at 7:15
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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) $\endgroup$
    – CodeNoob
    Jan 26 at 12:49
  • $\begingroup$ To remember why that doesn't strictly apply, familiarity with merge sorting multi-tape data with a limited number of tape drives would help. $\endgroup$
    – greybeard
    Jan 26 at 13:27
  • $\begingroup$ Unless spending endless CPU-hours/kWh on this, it would be a pretty elaborate experiment to implement and tune both approaches. $\endgroup$
    – greybeard
    Jan 26 at 14:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Jan 26 at 17:55
  • $\begingroup$ @D.W. thanks for the simplification :) I'm familiar with merge sorting from multiple files. I will give that a try $\endgroup$
    – CodeNoob
    Jan 26 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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