Ask HN: What are some cool but obscure data structures you know about?
1. Probabilistic filtering and matching:<p>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&#x2F;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&#x2F;geospatial data classification.<p>2. Checking for, locating and counting subsequences in giant string datasets:<p>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&#x27;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?<p>3. Reconstructing structured information from (potentially noisy) fragments:<p>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.<p>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.<p>1, 2 and 3 together are some of the fundamentals of computational biology. If you&#x27;re interested in understanding them, <a href="https:&#x2F;&#x2F;rosalind.info&#x2F;problems&#x2F;list-view&#x2F;" rel="nofollow">https:&#x2F;&#x2F;rosalind.info&#x2F;problems&#x2F;list-view&#x2F;</a> is a great starting place.