Data Structures
- Tries: Prefix Trees, all nodes with the same prefix have the same parent
- HyperLogLog: statistical population counting
- Bloom filter: space-efficient, probabilistic hash lookups. May result in false positive, that is, firm No, but probable Yes
- consists of
n hash functions, and a bitmap that is m bits wide
- each hash function returns a value upto
m
- for all inputs, bit positions that were returned by hash functions are set to
1
- for a lookup, if a bit position is not set for any hash function, the item is definitely not present
- B+ Trees: