7

I have 3 billion strings. I want to make a frequency map so I can discard strings that occur fewer than 100 times or more than 100,000 times. What kind of data structure(s) should I use? I'm thinking some kind of bloom filter.

  • What percentage of the strings do you expect to discard? – Robert Harvey Aug 22 '16 at 19:30
  • 2
    Is it possible to hold all unique strings in memory at the same time? Can you read the list multiple times? What are you optimizing for (memory, CPU, wall-clock execution time, programmer time)? – kdgregory Aug 22 '16 at 19:36
  • 2
    Oh, and if the list is sorted, the answer is trivial. – kdgregory Aug 22 '16 at 19:44
  • 2
    Linux command line (assuming your strings are in foo.txt): cat foo.txt | awk '{for(i=1;i<=NF;i++) a[$i]++} END {for(k in a) print k,a[k]}' | awk '{if ($2 > 100 && $2 < 100000) print $0 }'. I've done similar on datasets of that order of magnitude and it will take a while but should be "fast enough" unless you need this repeatedly, in realtime. – Chris Shain Aug 26 '16 at 0:32
  • 1
    I was going to answer but I think @CodesInChaos did a good job. So I'll just leave you with the "minimal programmer time" version: sort data.txt | uniq -c | awk '($1 >= 100) && ($1 <= 100000) {print $0}' | sed -e 's/^ *[0-9]* *//' -- the sort will be the most expensive part, but I was able to sort 1 billion arbitrary-sized alpha strings in under 30 minutes on a previous-generation desktop, so it's not that bad if this is an infrequent exercise. – kdgregory Aug 26 '16 at 22:26
5
+50

If there are few enough unique strings to fit memory, just use a Dictionary<string, uint> where the key is the string and the value its count.

If the unique strings don't fit memory, you can use a bloom-filter like data-structure where you store a counter for each hash instead of a bit for each hash. Fill it in a first pass over the data. Then each string with sufficiently many occurrences will have the counter for all its associated hashes over the threshold (100 in your case). In the second pass, use the counting dictionary approach, but only on strings that aren't eliminated by the bloom-filter.

  • This is the approach that I'd use. But note that multiple strings will probably hash to the same value, so simply discarding strings based on the counts in the hash buckets will give you false positives. But you can definitely discard any strings where the accumulated count is less than the threshold. – kdgregory Aug 26 '16 at 22:21
2

.. so maybe 7 bytes on average for the word and 4 bytes to store the count, that's at least 11 bytes per word but maybe i am forgetting things so let's double = 20 bytes. 20 byes * 3 billion records = 60 billion bytes or 56 GB

If you're worried about storage, then in principle a Trie (or radix trie) is a good way to store the current working set of strings & counts. Whether it's actually useful depends on whether there's enough prefix redundancy in your strings to outweigh the extra housekeeping.

Whatever container you use for the current working set, note that you only need 16 bits (uint16_t)to represent counts up to 100k, which is all you need. When a string reaches a count of 100k, add to a bloom filter of strings we already know to ignore. Note that you still need a copy of the string somewhere since bloom filters produce false positive matches.

Your string processing becomes something like

if (probably_ignored(s) && // quick bloom filter check
    definitely_ignored(s)) // slow check to exact string
{
  return;
}
uint16_t *count = get_or_add(s); // lookup or insert in working set
if (99999 == *count) {
  ignore(s); // remove from working set, add to bloom filter etc.
}
++ *count;

It's also worth noting that your container can be smaller if the character set is reduced. For example, if you don't need case-sensitivity, or any non-printing characters, or digits - anything you can eliminate may reduce the storage requirements.

  • A trie is a god idea - like with IP routing tables, which have millions of records on usually tiny hardware, you can compress extensively, so long as you have many prefixes that are the same. And, if your strings are limited to a range, e.g. only ASCII, you'll get really good compression and also really fast lookups. – Chris Cirefice Aug 26 '16 at 21:23
0

The counting BloomFilter variant proposed by @CodesInChaos should do nicely, do choose your hash algorithm closely, collisions here are likely which would skew your results. You could use 2-3 different hash to create a single key to count on.

A simpler brutish approach where you could use a database, a simple embeded one should do the trick (SQlite, berkely db etc). Store the strings and a counter then query away to get the ones you are interrested in, then just trash the database alltogether if it's not needed. RAM is expensive but you should have disk space to spare. It is, however, going to be a tad (lot) slower at runtime than an all in-memory approach. That said, you do have to read the strings from disk anyhow so all in all it should not add a tons of overhead, especially so if the strings do repeat often, the database in the end should be a lot smaller than the original data set. At worst it will be the space for all the strings + an int + small database overhead.

Lastly, your estimations (56GB) are worst case, that will indeed be the case if all your strings are different. but something tells me that the actual data stored will be a lot less, I would give the dead simple map solution a go first. Store the string as the key and the counter and iterate through. Worst that's gonna happen is your app will fill-up the ram and will crash. If it does work you get your answer with a dozen of loc. At least you'd have an idea of what the data looks like.

---- Edit Flash idea, you could lastly concatenate the strings with a separator and use string pattern search algorithm on the whole thing. Quite frequent approach in genetic pattern search where the dataset can get as big as you describe.
Check Z-Box search http://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/ or the classic Boyer-Moore https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm both of which I have tried in the past with some success for similar problems.

0

Approach 1: Due to the size of the data set I would attempt to break the set apart if possible.

Let's assume that you currently have a single file original.txt My first thought would be a bucket sort into new files by first letter/character in the string. If the files in this result set are still too large to hold in memory then I would iterate over each file in the same manner using the second character. Repeat this approach until your files are manageable. If regularly distributed and alphabetic only strings then you will be down to 170687 strings per file after third pass.

This approach could also use a complex Nested HashMap and I believe that Java would be able to cache the deeper portions and prevent having the whole set in memory at once. (I could be tragically mistaken on that part though)

Approach 2: Use a database

put the data all in a single table indexed on the string in question and then you can use

Select count(*),your_string from your_table group by your_string;

And you could get rid of the less common strings with something like

delete from your_table 
where your_string in (
    Select count(*),your_string from your_table 
    group by your_string
    having (count(*) < 100 or count(*) > 100000;

Approach 3: Hashmap < String, frequency> prevents the repetition of data in storage

Your Answer

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

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