[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.  Сейчас точно не вспомню.
----------- следущая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : отсутствует
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: отсутствует
Url     : http://lists.altlinux.ru/pipermail/devel/attachments/20050920/4968ad82/attachment.bin