Method
streaming
Articles
STR
Algorithm
The Aho–Corasick algorithm
Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function.
O(n + Σ|wᵢ| + z)
1 problem
SYS
Data structure
Count-Min Sketch
Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards.
O(d) per item and per query
2 problems
SYS
Data structure
HyperLogLog
The number of distinct elements of a stream in a kilobyte of memory: long runs of zeros in hashes and an average over registers.
O(1) per element, O(m) per estimate
2 problems
Problems
Often together
in production 3 networks 2 sketch 2 hashing 2 probabilistic 2 analytics 2 string matching 1 automaton 1 trie 1 security 1 bioinformatics 1 classic 1