Existe um filtro anti-Bloom?

Um filtro Bloom permite controlar com eficiência se vários valores já foram encontrados durante o processamento. Quando existem muitos itens de dados, um filtro Bloom pode resultar em uma economia significativa de memória em uma tabela de hash. O principal recurso de um filtro Bloom, que ele compartilha com uma tabela de hash, é que ele sempre diz "não novo" se um item não é novo, mas há uma probabilidade diferente de zero de que um item seja sinalizado como "não novo" "mesmo quando é novo.

Existe um "filtro anti-Bloom", que tem o comportamento oposto?

Em outras palavras: existe uma estrutura de dados eficiente que diz "novo" se um item é novo, mas que também pode dizer "novo" para alguns itens que não são novos?

Manter todos os itens vistos anteriormente (por exemplo, em uma lista vinculada classificada) satisfaz o primeiro requisito, mas pode consumir muita memória. Espero que também seja desnecessário, dado o segundo requisito relaxado.

Para aqueles que preferem um tratamento mais formal, escreva se o filtro Bloom considerar que é novo, caso contrário, e escreva se realmente for novo caso contrário.$b(x) = 1$$x$$b(x) = 0$$n(x) = 1$$x$$n(x) = 0$

Então ; ; ; , para alguns .$Pr[b(x) = 0 | n(x) = 0] = 1$$Pr[b(x) = 0 | n(x) = 1] = \alpha$$Pr[b(x) = 1 | n(x) = 0] = 0$$Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$$0 < \alpha < 1$

Estou perguntando: existe uma estrutura de dados eficiente, implementando uma função $b'$ com algum $0 < \beta < 1$ , de modo que $Pr[b'(x) = 0 | n(x) = 0] = \beta$ ; $Pr[b'(x) = 0 | n(x) = 1] = 0$ ; $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$ ; $Pr[b'(x) = 1 | n(x) = 1] = 1$ ?

Editar: parece que essa pergunta já foi feita no StackExchange, pois /programming/635728 e /cstheory/6596 com várias respostas de "não podem ser done "through" pode ser feito, com algum custo "to" é trivial, revertendo os valores de $b$ ". Ainda não está claro para mim qual é a resposta "certa". O que está claro é que um esquema de cache de LRU de algum tipo (como o sugerido por Ilmari Karonen) funciona bastante bem, é fácil de implementar e resultou em uma redução de 50% no tempo necessário para executar meu código.

Seguindo a idéia de hash de Patrick87, aqui está uma construção prática que quase atende aos seus requisitos - a probabilidade de confundir falsamente um novo valor com um antigo não é zero, mas pode ser facilmente reduzida de maneira insignificante.

Escolha os parâmetros e ; valores práticos podem ser, digamos, e . Seja uma função hash criptográfica segura, produzindo (pelo menos) bits de saída.k n = 128 k = 16 H n + $n$$k$$n = 128$$k = 16$$H$$n+k$

Deixe ser uma matriz de -BIT bitstrings. Essa matriz armazena o estado do filtro, usando um total de bits. (Não importa particularmente como essa matriz é inicializada; podemos apenas preenchê-la com zeros ou com bits aleatórios.)2 k n n 2 $a$$2^k$ $n$$n2^k$

• Para adicionar um novo valor ao filtro, calcule , em que indica os primeiros bits e indica os bits a seguir de . Seja .$x$$i \,\|\, j = H(x)$$i$j n H ( x ) a i = $k$$j$$n$$H(x)$$a_{i} = j$

• Para testar se um valor foi adicionado ao filtro, calcule , como acima, e verifique se . Se sim, retorne verdadeiro; caso contrário, retorne false.i $x'$a i ′ = j $i' \,\|\, j' = H(x')$$a_{i'} = j'$

Reivindicação 1: A probabilidade de um falso positivo (= novo valor que se afirma falsamente ter sido visto) é . Isso pode ser arbitrariamente pequeno, a um custo modesto no espaço de armazenamento, aumentando ; em particular, para , essa probabilidade é essencialmente insignificante, sendo, na prática, muito menor que a probabilidade de um falso positivo devido a um mau funcionamento do hardware. n n ≥ $1/2^{n+k}$$n$$n \ge 128$

Em particular, depois que valores distintos foram verificados e adicionados ao filtro, a probabilidade de ocorrer pelo menos um falso positivo é . Por exemplo, com e , o número de valores distintos necessários para obter um falso positivo com 50% de probabilidade é de cerca de .( N 2 - N ) / 2 n + k + 1 n = $N$$(N^2-N) / 2^{n+k+1}$$n=128$2 ( n + k ) / 2 = 2 $k=16$$2^{(n+k)/2} = 2^{72}$

Reivindicação 2: A probabilidade de um falso negativo (= valor adicionado anteriormente que se afirma falsamente ser novo) não é maior que , em que é o número de valores distintos adicionados ao filtro (ou, mais especificamente, o número de valores distintos adicionados após o valor específico que está sendo testado ter sido adicionado mais recentemente ao filtro).$1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$$N$

Ps. Para colocar "insignificantemente pequeno" em perspectiva, a criptografia de 128 bits geralmente é considerada inquebrável com a tecnologia atualmente conhecida. Obter um falso positivo desse esquema com é tão provável quanto alguém adivinhar corretamente sua chave secreta de criptografia de 128 bits na primeira tentativa . (Com e , que é, na verdade, cerca de 65.000 vezes menos provável do que isso.)$n+k=128$$n=128$$k=16$

Mas se isso ainda o deixa irracionalmente nervoso, você sempre pode mudar para ; isso dobrará seus requisitos de armazenamento, mas posso apostar com segurança qualquer quantia que você gostaria de citar que ninguém nunca verá um falso positivo com - assumindo que a função hash não esteja quebrada.$n=256$$n=256$

Não, não é possível ter uma estrutura de dados eficiente com essas propriedades, se você quiser ter uma garantia de que a estrutura de dados dirá "novo" se for realmente novo (nunca, nunca dirá "não novo" se é de fato novo; não são permitidos falsos negativos). Qualquer estrutura de dados desse tipo precisará manter todos os dados para responder "não novos". Veja a resposta de pents90 em cstheory para uma justificativa precisa.

Por outro lado, os filtros Bloom podem garantir que a estrutura de dados diga "não nova" se não for nova, de maneira eficiente. Em particular, os filtros Bloom podem ser mais eficientes do que armazenar todos os dados: cada item individual pode ser bastante longo, mas o tamanho do filtro Bloom é escalonado com o número de itens, e não com o comprimento total. Qualquer estrutura de dados para o seu problema precisará ser dimensionada com o comprimento total dos dados, não com o número de itens de dados.

Que tal apenas uma tabela de hash? Quando você vir um novo item, verifique a tabela de hash. Se o local do item estiver vazio, retorne "novo" e adicione o item. Caso contrário, verifique se o local do item está ocupado pelo item. Nesse caso, retorne "não novo". Se o local estiver ocupado por algum outro item, retorne "novo" e substitua o local pelo novo item.

Você definitivamente sempre será "Novo" corretamente se nunca viu o hash do item antes. Definitivamente, você sempre obterá "Not New" corretamente se você só viu o hash do item quando viu o mesmo item. A única vez em que você obterá "Novo" quando a resposta correta for "Não é novo" é se vir o item A, depois ver o item B, depois ver o item A novamente e o hash A e B na mesma coisa. Importante, você nunca pode obter "Not New" incorretamente.

No caso em que o universo de itens é finito, então sim: basta usar um filtro de bloom que registra quais elementos estão fora do conjunto e não no conjunto. (Ou seja, use um filtro de bloom que represente o complemento do conjunto de interesse.)

Um local em que isso é útil é permitir uma forma limitada de exclusão. Você mantém dois filtros de floração. Eles começam vazios. À medida que você insere elementos, insere-os no filtro de bloom A. Se você desejar excluir um elemento posteriormente, insira esse elemento no filtro de bloom B. Não há como cancelar a exclusão. Para fazer uma pesquisa, primeiro procure no filtro de bloom A. Se você não encontrar correspondência, o item nunca foi inserido (com probabilidade 1). Se você encontrar uma correspondência, o elemento pode (ou não) ter sido inserido. Nesse caso, você faz uma pesquisa no filtro de bloom B. Se não encontrar correspondência, o item nunca foi excluído. Se você encontrar uma correspondência no filtro B de bloom, provavelmente o item foi inserido e excluído.

Isso realmente não responde à sua pergunta, mas, neste caso limitado, o filtro de bloom B está executando exatamente o comportamento do "filtro anti-bloom" que você está procurando.

Os pesquisadores de filtro do Real Bloom usam maneiras muito mais eficientes de representar a exclusão, consulte a página da publicação de Mike Mitzenmacher .

$v_i$

Um exemplo pode ser o endereço IP e você deseja saber sempre que aparecer um que nunca viu antes. Mas ainda é um conjunto finito, para que você saiba o que pode esperar.

A solução real é simples:

1. Adicione todos os seus itens ao filtro de contagem florida.
2. $\ge1$
3. Depois de ver um novo item real, subtraia-o do filtro.

Portanto, você pode ter valores de "falsos positivos" que eram antigos, mas reconhecidos como novos. No entanto, você nunca terá 'não novo' para um novo valor, pois o valor ainda estará em todos os slots, e ninguém mais poderia ter tirado isso.