Since you mentioned bloom filters - other probabilistic data structures like count-min sketches (roughly, streaming bloom filters) are super useful. Approximate kmer methods like minhash and w-shingling use them in really cool ways. Rolling hash methods like Rabin chunking also work really nicely with probabilistic/streaming hash tables - splitting the data stream into chunks that can be consistently filtered or matched is useful in many circumstances! Think NSA-level data harvesting, or realtime genome/geospatial data classification.
2. Checking for, locating and counting subsequences in giant string datasets:
Wavelet trees, FM-indices, suffix arrays more generally - and structures that allow extreme performance in very niche situations with arbitrary encodings like bitvectors and compressed integer vectors. If you have a million books, or all the genomes ever sequenced, you use the first structures to find where a specific phrase can be found, even if you don't quite spell it right. You can use the latter ones to do super fast comparisons of giant datasets - given a million viruses, how similar is each one to the human genome, and where specifically do they most closely match?
3. Reconstructing structured information from (potentially noisy) fragments:
De-brujn graphs (and related graphs like string graphs, colored de brujns). This is a way to find all the overlap connections between fragments of information, and then weight the possible traversals of those connections by the evidence. These can be represented using the data structures from #1 (FM-indices for example), and efficiently used in some circumstances with those from #2 to enable some kinds of graph algorithms. If you have a shredded set of documents, or a billion short DNA reads from a genome sequencing experiment, this is how you reconstruct the original.
4. Decentralised coordination structures. Merkle-DAGs and Kademlia DHTs in particular. Being able to compare any trees by root-first hashes, and being able to request the content of the subtree for any node hash from an arbitrary set of peers - these structures enable the p2p web infrastructure. Everything from Limewire to bittorrent, IPFS and blockchains, and, most importantly, Sci-Hub.
1, 2 and 3 together are some of the fundamentals of computational biology. If you're interested in understanding them, https://rosalind.info/problems/list-view/ is a great starting place.
Basically, it makes a similar point to https://news.ycombinator.com/item?id=32186837 — i.e., cache effects are not modeled in big O analysis, even though most problems that involve large amounts of data (so most problems) are memory bound rather than CPU bound. The blog post makes a good case for a very simple hash table as a better fit for this problem.
> While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simpler
Yes, standard Bloom filters fail for large filter sizes and/or very small false-positive rates. But we've known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible.
Was there really no easy way to bring in an open-source Cuckoo filter implementation? They're not that complicated. Maybe I'm just used to modern languages having good package managers.
Plus the author's solution is basically the idea behind Cuckoo filters: "what if we just use a hash table, but allow for collisions?" Cuckoo hashing is just clever about guaranteeing O(1) worst-case lookup.
And for absolute dead-simple filters, a blocked Bloom filter is basically just as easy as a Bloom filter. It's like two or three more lines of code. It's just changing the indexing operation to be modulo some large "block" size. That said, I don't think they'd work too well in this case, since the author has a pretty small false-positive rate (0.000019), and in my experience small Bloom filters (which is what comprise blocked Bloom filters) don't handle small FP rates well.
But guess what excel at small FP rates… cuckoo filters.
A linear probing hash table is simpler. That’s the trade off they were going for at that time. I don’t think that’s the most efficient solution given the hardware they were using, and I don’t think the blog author would either, but it’s certainly easier to write such a hash table — and it’s well written, but still mostly interview level stuff.
To me the blog post is not about cuckoo or bloom filters or hash tables at all. It’s about profiling and highlighting that a naive reading of the literature can easily lead you astray (worse performance and complexity). In school they don’t teach you that mov is the biggest cycle-eater of them all — at least it’s not the lesson people remember.
If you’re willing to use moderately more memory, you can get much better cache locality using a blocked bloom filter. The basic idea is to use an array of bloom filters that each fit into a cache line, and use some bits of hash to determine which sub-filter each item goes into. Suddenly each lookup or insertion has at most one cache miss!
Since you mentioned bloom filters - other probabilistic data structures like count-min sketches (roughly, streaming bloom filters) are super useful. Approximate kmer methods like minhash and w-shingling use them in really cool ways. Rolling hash methods like Rabin chunking also work really nicely with probabilistic/streaming hash tables - splitting the data stream into chunks that can be consistently filtered or matched is useful in many circumstances! Think NSA-level data harvesting, or realtime genome/geospatial data classification.
2. Checking for, locating and counting subsequences in giant string datasets:
Wavelet trees, FM-indices, suffix arrays more generally - and structures that allow extreme performance in very niche situations with arbitrary encodings like bitvectors and compressed integer vectors. If you have a million books, or all the genomes ever sequenced, you use the first structures to find where a specific phrase can be found, even if you don't quite spell it right. You can use the latter ones to do super fast comparisons of giant datasets - given a million viruses, how similar is each one to the human genome, and where specifically do they most closely match?
3. Reconstructing structured information from (potentially noisy) fragments:
De-brujn graphs (and related graphs like string graphs, colored de brujns). This is a way to find all the overlap connections between fragments of information, and then weight the possible traversals of those connections by the evidence. These can be represented using the data structures from #1 (FM-indices for example), and efficiently used in some circumstances with those from #2 to enable some kinds of graph algorithms. If you have a shredded set of documents, or a billion short DNA reads from a genome sequencing experiment, this is how you reconstruct the original.
4. Decentralised coordination structures. Merkle-DAGs and Kademlia DHTs in particular. Being able to compare any trees by root-first hashes, and being able to request the content of the subtree for any node hash from an arbitrary set of peers - these structures enable the p2p web infrastructure. Everything from Limewire to bittorrent, IPFS and blockchains, and, most importantly, Sci-Hub.
1, 2 and 3 together are some of the fundamentals of computational biology. If you're interested in understanding them, https://rosalind.info/problems/list-view/ is a great starting place.