News for hackers. Stuff that matters.
Re:Ask HN: Sorting massive text files? by davidst on Saturday August 14, 2010 @09:43PM (#1604405)
BTW, as you desire to decrease your error rate Cuckoo hashing starts to become an attractive alternative to Bloom filters:

http://en.wikipedia.org/wiki/Cuckoo_hashing http://www.ru.is/faculty/ulfar/CuckooHash.pdf

You can get your hash table utilization to almost 100%. If you're willing to accept a 64-bit hash function and you have 2 billion unique strings you'll need just over 16GB to do it all in one pass.

A 64-bit hash is is just barely enough for 2 billion items. You might get a handful of collisions. Add more bits to reduce the probability. 128-bits would double the required size to 32GB but you're unlikely to ever see a collision in your life time.

If 16GB or 32GB is too much you could do it in multiple passes. Make N passes through the text file and adjust the range of hash values you accept to test only 1/N each time.

8 passes through the original file with a generous 128-bit hash would take only 4GB of RAM.

I have the feeling this is more work than you would want to put into the problem, though.

There are no comments on this comment yet.