This is gaining popularity in bioinformatics too. When you sequence a genome with a sequencing machine in tiny pieces you get the same piece several times, it'

This is gaining popularity in bioinformatics too. When you sequence a genome with a sequencing machine in tiny pieces you get the same piece several times, it's not even coverage, some pieces show up a lot, some pieces show up rarely so that you have to sequence the genome several times, so to speak (30 to 80 times is the norm). A lot of that data is redundant to get to those rare pieces, so 'data sketching' is getting more popular. Examples: - The Abyss genome assembler has (experimentally) a Bloom filter to decrease memory requirements and run time at the expense of accuracy and having to fiddle with the Bloom filter parameters. The paper assembles a genome using 35GB o RAM instead of a few hundred GB. - The khmer package contains many functions to downsample sequencing runs using, again, Bloom filters. It also has a HyperLogLog implementation to quickly count k-mers (similar to n-grams, but with ATGC instead of words) - MinHash sketching is a popular first step in aligning messy PacBio reads (implemented for example in the Canu assembler). People also use this to map population structure using sequencing reads directly, and to quickly assign a taxon to the data of an unknown species. - There are some approaches with the Oxford Nanopore sequencer (that tiny thing you can hook up to your laptop) where you stream the incoming data directly into the assembler or other program and tell the sequencer to stop sequencing once you found what you're looking for, or your coverage is high enough Etc. pp. It's a goldmine for fast algorithms, I haven't seen people use a Cuckoo filter, for example