On Mon, Sep 19, 2005 at 12:18:34AM +0400, Alexey Tourbin wrote:
> bloom filter -- это специальный бинарный хеш, который позволяет
> проверить принадлежность элемента к множеству, не имея при этом (на
> стадии проверки) самого множества элементов.  Множество элементов
> нужно только на стадии создания хеша.

У этих хешей есть одной замечательной свойство: к хешам с одинаковой
конфигурацией примеными теоретико-множественные операции.

Union and intersection of Bloom filters with the same size and set of
hash functions can be implemented with bitwise OR and AND operations,
respectively.  http://en.wikipedia.org/wiki/Bloom_filter

Кажется, все остальные операции булевой алгебры можно выразить через
OR и AND.  Сейчас точно не вспомню.