Como os filtros de bloom escalonáveis ​​funcionam?

Eu estava lendo sobre filtros de bloom escaláveis ​​e não conseguia entender como cada vez que um filtro de bloom constituinte é preenchido, um novo filtro de bloom com tamanho maior é adicionado.

Os elementos que contribuíram para os bits definidos nos filtros criados inicialmente não podem ser procurados para presença. Talvez eu esteja errado na minha compreensão disso?

Eu entendo os filtros básicos de bloom. No entanto, não consigo entender os filtros dinâmicos de bloom.

Deixe-me tentar dar uma chance para ver o quanto eu posso matá-lo. :-)

Portanto, para começar, você precisa criar um filtro de bloom regular que permita um número finito de elementos com uma probabilidade máxima de um falso positivo. A adição desses recursos ao seu filtro básico é necessária antes de tentar criar uma implementação escalável.

Antes de tentarmos controlar e otimizar qual é a probabilidade, vamos descobrir qual é a probabilidade para um determinado tamanho de filtro de bloom.

Primeiro, dividimos o campo de bits pelo número de funções de hash que temos (número total de bits / número de funções de hash = fatias) para obter k fatias de bits que representam cada função de hash, para que cada elemento seja sempre descrito por k bits.

Se você aumentar o número de fatias ou o número de bits por fatia, a probabilidade de falsos positivos diminuirá.

Da mesma forma, à medida que os elementos são adicionados, mais bits são definidos como 1, aumentando assim os falsos positivos. Nós nos referimos a isso como a "proporção de preenchimento" de cada fatia.

Quando o filtro contém uma grande quantidade de dados, podemos assumir que a probabilidade de falsos positivos para esse filtro é a taxa de preenchimento aumentada para o número de fatias (se formos contar os bits em vez de usar uma proporção, isso simplifica permutação com problema de repetição).

Então, como descobrimos como escolher uma probabilidade de falsos positivos em um filtro de bloom? Podemos modificar o número de fatias (o que afetará a taxa de preenchimento).

Para descobrir quantas fatias deveríamos ter, começamos a descobrir a proporção ideal de preenchimento para uma fatia. Como a taxa de preenchimento é determinada pelo número de bits em uma fatia que é 1 versus o número de bits que é 0, podemos determinar que cada bit permanecerá não definido com probabilidade de (100% - (1 / bits em uma fatia) ) Como vamos inserir vários itens, temos outra permutação com problemas de reputação e expandimos as coisas para a taxa de preenchimento esperada, que é (100% - ((100% - (1 / bits em uma fatia)) ^ "elementos inseridos")). Bem, acontece que isso é muito semelhante a outra equação. No artigo, eles relacionam a taxa de preenchimento a outra equação, para que ela se encaixe perfeitamente em uma série de taylor (1-e ^ (- n / m)). Após um pouco de futzing com isso, verifica-se que a taxa de preenchimento ideal é sempre de cerca de 50%,

Portanto, como a probabilidade de um filtro é a taxa de preenchimento aumentada para o número de fatias, podemos preencher 50% e obter P = (50%) ^ k ou k = log_2 (1 / P). Em seguida, podemos usar essa função para calcular o número de fatias que devemos gerar para um determinado filtro na lista de filtros para um filtro de bloom escalável.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Edit: Depois de escrever isso, me deparei com uma menção à "regra dos cinquenta por cento" ao ler sobre alocação de memória dinâmica baseada em sistema de amigos no TAoCP Vol 1, pp 442-445 com um raciocínio muito mais limpo do que ajustar a curva a (1 -e ^ (- n / m)). Knuth também faz referência a um artigo "A regra dos cinquenta por cento revisitada" com um pouco de conhecimento sobre o conceito ( pdf disponível aqui ).

Um item está no filtro de bloom escalável se algum filtro retornar verdadeiro. Portanto, você pode adicionar filtros sem afetar as consultas de associação dos itens anteriores.

Para garantir que você ainda tenha uma garantia de falso positivo no pior dos casos, novos filtros são adicionados com taxas de falso positivo que diminuem geometricamente. Por exemplo, o primeiro filtro tem taxa de falsos positivos p, o segundo rp, o terceiro r^2p, etc. A probabilidade de um falso positivo sobre o filtro flor escalável é depois delimitada pela união ligado: sum_{k>=0} r^k p = p/(1-r).

Eu estava lendo sobre filtros de bloom escaláveis ​​e não conseguia entender como cada vez que um filtro de bloom constituinte é preenchido, um novo filtro de bloom com tamanho maior é adicionado.

Os elementos que contribuíram para os bits definidos nos filtros criados inicialmente não podem ser procurados para presença. Talvez eu esteja errado na minha compreensão disso?

Olá,
A idéia básica é adicionar ao primeiro filtro até que o campo de bits do filtro de primeiro nível esteja saturado. Estar saturado não significa que cada bit é usado, mas significa que o filtro contém tantas entradas que entradas adicionais criariam muitos falsos positivos.

Do ponto de saturação, qualquer novo item não será adicionado ao filtro saturado, mas a um subfiltro novo e maior (o filtro de segundo nível).

Para encontrar um valor, procure-o no filtro de primeiro nível e, se não o encontrar, procure-o no filtro de segundo nível. Se você puder encontrá-lo em qualquer um desses filtros, é (por uma boa chance) "conhecido" pelo filtro (podem ocorrer falsos positivos como resultado da natureza dos filtros Bloom). Se você não conseguir encontrar o valor em nenhum dos filtros, é garantido que o filtro não o tenha visto. Obviamente, isso pode ser expresso como uma estrutura de dados recursiva.

Você pode ler minha postagem no blog que contém uma implementação de filtro Bloom escalável em Java e uma explicação de como funciona em detalhes.