Bloom filter and trie

In short: A Bloom filter checks in a space-saving way whether an element is “definitely not” or “maybe” in a set. A trie (prefix tree) stores words by their initial letters.

In more detail: The Bloom filter is a bit array with several hash functions. A “no” is certain, a “yes” can be a false alarm. A trie has a branch for each character. Common beginnings are stored only once; search takes O(length of the word).

In Depth

• Bloom filter: saves expensive lookups (for example “is this URL known to be malicious?”), databases (LSM trees), caches. Deleting is not possible.
• Error rate: adjustable via size and number of hashes.
• Trie: autocomplete, spell checking, routing tables (IP prefixes), dictionary games.
• Memory: Tries need a lot of space for many words; compressed variants (radix tree) help.

See also: Hashing, Tree data structure