[devel] Re: bloom filters

[Alexey Tourbin]

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.  Сейчас точно не вспомню.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20050920/4968ad82/attachment-0001.bin>