6 ms·
After the Bloom Filter post the other day, I've been doing a dive on probabilistic data structures. This one was obviously on the list along with: skip list, bl
by _asummers 10y ago
After the Bloom Filter post the other day, I've been doing a dive on probabilistic data structures. This one was obviously on the list along with: skip list, bloom filter, count-min sketch, linear counting, loglog, hyperloglog. Are there any major ones I'm missing, or even better, any lesser known ones I should be aware of? Are there any good resources/courses on this class of data structure/algorithm?
- jhalstead 10y agoHow about the treap? http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-treaps.pdf http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-tr... or https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap
- ejbs2 10y agoThe treap, aka what people should learn instead of red black trees (because they're a lot simpler with similar performance).
- dmit 10y ago>Are there any major ones I'm missing, or even better, any lesser known ones I should be aware of? MinHash. I also highly recommend this blog: https://research.neustar.biz/tag/sketching/ https://research.neustar.biz/tag/sketching/
- senderista 10y agoMinHash works well if you need to approximate Jaccard similarity. To approximate cosine similarity, you can use Charikar's SimHash: http://d3s.mff.cuni.cz/~holub/sw/shash/ http://d3s.mff.cuni.cz/~holub/sw/shash/.
- dalke 10y agoYou might be interested in reading the section at the end of v.3 of Knuth's "The Art of Computer Programming" on superimposed coding. It was first developed by Mooers in the late 1940s as a way to reduce the number of punches needed on a punched card. Mooers was annoyed that the computer scientists decades after him re-discovered he principles he first worked on, but without citing him. Knuth points out the connection.