Qual é a vantagem de usar filtros Bloom?

Estou lendo sobre filtros de flor e eles parecem bobos. Qualquer coisa que você possa realizar com um filtro bloom, você pode realizar em menos espaço, com mais eficiência, usando uma única função hash em vez de várias, ou é o que parece. Por que você usaria um filtro bloom e como ele é útil?

Da Wikipedia :

Os filtros Bloom têm uma grande vantagem de espaço sobre outras estruturas de dados para representar conjuntos, como árvores de busca binária de autobalanceamento, tentativas, tabelas de hash ou matrizes simples ou listas vinculadas de entradas. A maioria deles exige o armazenamento de pelo menos os próprios itens de dados, o que pode exigir desde um pequeno número de bits, para pequenos inteiros, até um número arbitrário de bits, como para strings (as tentativas são uma exceção, pois podem compartilhar o armazenamento entre elementos com prefixos iguais). Estruturas vinculadas incorrem em uma sobrecarga de espaço linear adicional para ponteiros. Um filtro Bloom com 1% de erro e um valor ideal de k, por outro lado, requer apenas cerca de 9,6 bits por elemento - independentemente do tamanho dos elementos. Essa vantagem vem em parte de sua compactação, herdada de matrizes, e em parte de sua natureza probabilística. Se uma taxa de 1% de falsos positivos parece muito alta, cada vez que adicionamos cerca de 4,8 bits por elemento, nós a diminuímos dez vezes.

Muito claro para mim.

Um filtro bloom não armazena os elementos em si, este é o ponto crucial. Você não usa um filtro bloom para testar se um elemento está presente, você o usa para testar se é certo não está presente, uma vez que não garante falsos negativos. Isso permite que você não faça trabalho extra para elementos que não existem em um conjunto (como IO de disco para procurá-los).

E tudo em muito menos espaço do que algo como uma tabela hash (que provavelmente estará parcialmente no disco para grandes conjuntos de dados). Embora você possa usar um filtro bloom em conjunto com uma estrutura como uma tabela hash, uma vez que você tenha certeza de que o elemento tem uma chance de estar presente.

Portanto, um exemplo de padrão de uso pode ser:

Você tem muitos dados no disco - você decide qual limite de erro deseja (por exemplo, 1%), que prescreve o valor de m . Então o k ótimo é determinado (a partir da fórmula dada no artigo). Você preenche seu filtro a partir desses dados vinculados ao disco uma vez.

Agora você tem o filtro na RAM. Quando você precisa processar algum elemento, você consulta seu filtro para ver se ele tem chance de existir em seu conjunto de dados. Caso contrário, nenhum trabalho extra será feito. Sem leituras de disco, etc. (o que você teria que fazer se fosse um hash ou árvore, etc.).

Caso contrário, se o filtro disser "Sim, está lá", há 1% de chance de que esteja errado, então você faz o trabalho necessário para descobrir. 99% das vezes, realmente estará lá, então o trabalho não foi em vão.

Alex explicou muito bem. Para aqueles que ainda não entenderam bem, espero que este exemplo ajude você a entender:

Vamos dizer que eu trabalho para o Google, na equipe do Chrome, e quero adicionar um recurso ao navegador que notifica o usuário se o url que ele inseriu é um URL malicioso. Portanto, tenho um conjunto de dados de cerca de 1 milhão de URLs maliciosos, sendo o tamanho deste arquivo em torno de 25 MB. Como o tamanho é muito grande (grande em comparação com o tamanho do navegador), armazeno esses dados em um servidor remoto.

Caso 1: uso uma função hash com uma tabela hash. Eu escolho uma função de hash eficiente e executo todos os 1 milhão de urls por meio da função de hash para obter as chaves de hash. Em seguida, faço uma tabela hash (uma matriz), onde a chave hash me daria o índice para colocar essa URL. Agora, depois de fazer o hash e preencher a tabela de hash, verifico seu tamanho. Eu armazenei todos os 1 milhão de URLs na tabela de hash junto com suas chaves. Portanto, o tamanho é de pelo menos 25 MB. Esta tabela hash, devido ao seu tamanho, será armazenada em um servidor remoto. Quando um usuário chega e insere um URL na barra de endereço, preciso verificar se é malicioso. Assim, executo o URL por meio da função hash (o próprio navegador pode fazer isso) e obtenho uma chave hash para esse URL. Agora tenho que fazer uma solicitação ao meu servidor remoto com essa chave hash, para verificar se o URL específico em minha tabela de hash com aquela chave específica é o mesmo que o usuário inseriu. Se sim, então é malicioso e se não, então não é malicioso. Assim, cada vez que o usuário insere um URL, uma solicitação ao servidor remoto deve ser feita para verificar se é um URL malicioso. Isso levaria muito tempo e, portanto, tornaria meu navegador lento.

Caso 2: Eu uso um filtro bloom. A lista inteira de 1 milhão de URLs é executada através do filtro bloom usando várias funções hash e as respectivas posições são marcadas como 1, em uma enorme matriz de 0s. Digamos que queremos uma taxa de falso positivo de 1%, usando uma calculadora de filtro bloom ( http://hur.st/bloomfilter?n=1000000&p=0.01), obtemos o tamanho do filtro bloom necessário como apenas 1,13 MB. Esse tamanho pequeno é esperado porque, embora o tamanho do array seja enorme, estamos armazenando apenas 1s ou 0s e não os URLs como no caso da tabela hash. Este array pode ser tratado como um array de bits. Ou seja, como temos apenas dois valores 1 e 0, podemos definir bits individuais em vez de bytes. Isso reduziria o espaço ocupado em 8 vezes. Este filtro bloom de 1,13 MB, devido ao seu tamanho pequeno, pode ser armazenado no próprio navegador da web !! Assim, quando um usuário chega e insere um URL, simplesmente aplicamos as funções hash necessárias (no próprio navegador) e verificamos todas as posições no filtro bloom (que está armazenado no navegador). Um valor de 0 em qualquer uma das posições nos diz que este URL NÃO ESTÁ DEFINITIVAMENTE na lista de URLs maliciosos e que o usuário pode proceder livremente. Portanto, não fizemos uma chamada para o servidor e, portanto, economizamos tempo. Um valor de 1 nos diz que o URL PODE estar na lista de URLs maliciosos. Nestes casos, fazemos uma chamada para o servidor remoto e lá podemos usar alguma outra função hash com alguma tabela hash como no primeiro caso para recuperar e verificar se a URL está realmente presente. Como, na maioria das vezes, um URL provavelmente não é malicioso, o pequeno filtro bloom no navegador descobre isso e, portanto, economiza tempo, evitando chamadas para o servidor remoto. Somente em alguns casos, se o filtro bloom nos diz que a URL PODE ser maliciosa, somente nesses casos fazemos uma chamada para o servidor. Esse 'MIGHT' está 99% certo. Nestes casos, fazemos uma chamada para o servidor remoto e lá podemos usar alguma outra função hash com alguma tabela hash como no primeiro caso para recuperar e verificar se a URL está realmente presente. Como, na maioria das vezes, um URL provavelmente não é malicioso, o pequeno filtro bloom no navegador descobre isso e, portanto, economiza tempo, evitando chamadas para o servidor remoto. Somente em alguns casos, se o filtro bloom nos diz que a URL PODE ser maliciosa, somente nesses casos fazemos uma chamada para o servidor. Esse 'MIGHT' está 99% certo. Nestes casos, fazemos uma chamada para o servidor remoto e lá podemos usar alguma outra função hash com alguma tabela hash como no primeiro caso para recuperar e verificar se a URL está realmente presente. Como, na maioria das vezes, um URL provavelmente não é malicioso, o pequeno filtro bloom no navegador descobre isso e, portanto, economiza tempo, evitando chamadas para o servidor remoto. Somente em alguns casos, se o filtro bloom nos diz que a URL PODE ser maliciosa, somente nesses casos fazemos uma chamada para o servidor. Esse 'MIGHT' está 99% certo. o pequeno filtro bloom no navegador descobre isso e, portanto, economiza tempo, evitando chamadas para o servidor remoto. Somente em alguns casos, se o filtro bloom nos diz que a URL PODE ser maliciosa, somente nesses casos fazemos uma chamada para o servidor. Esse 'MIGHT' está 99% certo. o pequeno filtro bloom no navegador descobre isso e, portanto, economiza tempo, evitando chamadas para o servidor remoto. Somente em alguns casos, se o filtro bloom nos diz que a URL PODE ser maliciosa, somente nesses casos fazemos uma chamada para o servidor. Esse 'MIGHT' está 99% certo.

Portanto, ao usar um pequeno filtro bloom no navegador, economizamos muito tempo, pois não precisamos fazer chamadas de servidor para cada URL inserido.

Podemos ver que a tabela hash com uma única função hash é usada para uma finalidade totalmente diferente de um filtro bloom. Espero que isso esclareça suas dúvidas :)

editar :

Implementei um filtro bloom para a tarefa de teste de URL malicioso em Python. O código pode ser encontrado aqui - https://github.com/tarunsharma1/Bloom-Filter O código é muito simples de entender e uma descrição detalhada é fornecida no arquivo leia-me.

Vou começar com a explicação do que é um filtro bloom, o que ele pode e não pode fazer, por que precisamos dele, mostrarei uma descrição intuitiva de como ele funciona e depois darei alguns exemplos de quando podem ser úteis.

Portanto, um filtro bloom padrão é uma estrutura de dados probabilística que pode ^* :

• adicionar elemento a um conjunto
• verifique se um elemento está no conjunto dizendo definitely not in the setoupossibly in the set

Este possibly in the seté exatamente por isso que ele é chamado probabilística. Usar palavras inteligentes significa que falso positivo é possível (pode haver casos em que ele pensa erroneamente que o elemento é positivo), mas falso negativo é impossível.

Mas não pode ^* :

• remova um item do conjunto
• dar-lhe uma lista de todos os elementos que estão atualmente em seu conjunto

^* _{Este conjunto de pode / não pode ser usado para um filtro bloom básico. Por ser uma estrutura de dados útil criada há muito tempo, as pessoas descobriram como aumentá- la com outros recursos úteis .}

Mas espere um minuto: já conhecemos uma estrutura de dados que pode responder a tudo isso sem vago 'possível' e também sem todas as limitações (não pode remover, não pode mostrar tudo). E é chamado de conjunto . E aqui vem uma vantagem principal de um filtro bloom: é eficiente em termos de espaço e constante .

Isso significa que não importa quantos elementos armazenemos lá, o espaço será o mesmo. Sim, um filtro bloom com 10^6elementos (filtro bloom inútil) ocupará a mesma quantidade de espaço que um filtro bloom com 10^20elementos e o mesmo espaço que um filtro bloom com 0elementos. Então, quanto espaço será necessário? Cabe a você decidir (mas há uma troca: quanto mais elementos você tem, mais incerto você fica ao possible in the setresponder.

Outra coisa legal é que é uma constante de espaço. Quando você salva os dados em um conjunto, você realmente precisa salvar esses dados. Portanto, se você armazenar, this long string in the setterá que usar pelo menos 27 bytes de espaço. Mas para um erro de 1% e um valor ideal de k ^** , você precisará de ~ 9,6 bits (<2 bytes) por qualquer elemento (seja um pequeno int ou uma grande parede de texto).

Outra propriedade é que todas as operações estão levando tempo constante, o que não é absolutamente o mesmo que tempo constante amortizado no caso de conjuntos (lembre-se que se o conjunto tiver colisões, ele pode se deteriorar em O(n) tempo).

^** _{k é um valor de funções hash usadas no filtro Bloom}

Não vou descrever como funcionam os filtros do bloom (o artigo da wikipedia explica tudo muito bem). Aqui, contarei apenas brevemente o básico.

• você inicia uma matriz de bits vazia de comprimento m
• você seleciona kdiferentes funções hash (quanto mais independente, melhor)
• se você quiser adicionar um elemento, você calcula todos os k hashes deste valor e define os bits correspondentes para 1
• se você quiser verificar se o elemento existe, você também calcula todos os khashes e se pelo menos um deles não está definido, certamente não está no conjunto. Caso contrário, pode estar no conjunto.

Mesmo esta descrição é suficiente para entender por que não podemos ter certeza (você pode obter todos os bits definidos a partir de vários outros valores). Aqui está uma visualização muito boa de como funciona .

Então, quando os filtros Bloom podem ser úteis? A resposta curta está em todos os lugares onde falsos positivos são aceitáveis ​​e onde você gostaria de verificar se algo está no conjunto , mas mesmo que não esteja, pode ser uma primeira linha de defesa para descartar chamadas caras para verificadores.

Aqui está uma lista de descrições mais concretas:

• um exemplo padrão de sites maliciosos e um navegador é descrito em quase todos os lugares onde as pessoas falam sobre filtros bloom
• é uma senha fraca: em vez de ter um grande conjunto de todas as possíveis senhas fracas, você pode apenas verificar se a senha certamente não é fraca com um filtro bloom muito menor
• se você tem uma lista de artigos e uma lista de usuários, você pode usar o filtro bloom para mostrar os artigos dos usuários que eles não leram. O interessante é que você pode ter apenas um filtro (você verifica se a combinação de user_id + article_id está lá)
• bitcoin usa filtro bloom para sincronização de carteira
• Os servidores da web da Akamai usam filtros Bloom para evitar que "maravilhas de um só golpe" sejam armazenadas em seus caches de disco. Maravilhas de um golpe são objetos da web solicitados pelos usuários apenas uma vez, algo que a Akamai descobriu que se aplica a quase três quartos de sua infraestrutura de cache. Usar um filtro Bloom para detectar a segunda solicitação de um objeto da web e armazenar em cache esse objeto apenas em sua segunda solicitação evita que maravilhas de um único acerto entrem no cache de disco, reduzindo significativamente a carga de trabalho do disco e aumentando as taxas de acerto do cache de disco (retirados de exemplos no filtro do bloom artigo na wiki)

Filtros Bloom são bastante úteis em bioinformática. Eles podem ser mais eficientes em termos de espaço em comparação com o uso de um hash regular, especialmente quando o tamanho das strings com as quais você está trabalhando pode ser de centenas de milhões de letras com um alfabeto muito pequeno, ou seja, {A, G, T, C}. Eles geralmente são usados ​​para avaliar se um determinado k-mer está presente ou ausente em um genoma. Há um exemplo de um usado para algo relevante aqui .

EDITAR:

As várias funções hash são usadas para minimizar falsos positivos. A esperança é que, entre todas as funções k-hash, cada valor tenha uma assinatura exclusiva na matriz de bits em comparação com todos os outros valores possíveis. No entanto, falsos positivos existem, mas podem ser minimizados a um nível gerenciável. Usando essa técnica, você hash elementos independentemente de seu tamanho. Ao pesquisar por eles, você usa cada função hash e verifica se todos os valores de bits são 1.

Compare isso com o genoma humano, onde um aumento no tamanho do elemento aumenta o tamanho da tabela hash significativamente (o tamanho da tabela é 4 * 4 ^k ). Isso pressupõe que você codifique os elementos usando 2 bits / letra.

Se um filtro Bloom retornar que um item é membro do conjunto, há uma certa probabilidade de um falso positivo. Se apenas uma única função hash fosse usada para indicar a participação no conjunto, a probabilidade de um falso positivo seria maior do que usar várias funções hash.