Bloom Filters

Bloom filters are cool. Start with a hash table, which is an efficient way to look up items in a set. A bloom filter is like a hash table, but it tells you only whether an item is in a set, and it sometimes incorrectly says yes (false positives), and the data structure is much smaller than a hash table.

This could be used to make a P2P filesharing client where searches could be performed offline. Peer A computes its Bloom filter signature, then broadcasts it to the world. Peer B collects Bloom filter signatures, then when it wants to search for an item, it iterates all the signatures, looking for a likely match, and broadcasts queries to one or more of the peers that come up positive.

Same idea but generalize it: a peer itself can be an item, so peers could exchange Bloom filters of connected peers to determine how to reach a particular peer without broadcasting queries to the whole world.