Um conjunto probabilístico sem falsos positivos?

35

Portanto, os filtros Bloom são bem legais - são conjuntos que suportam a verificação de associação sem falsos negativos, mas com uma pequena chance de um falso positivo. Recentemente, porém, eu estava querendo um "filtro Bloom" que garanta o contrário: sem falsos positivos, mas potencialmente falsos negativos.

Minha motivação é simples: dado um grande fluxo de itens a serem processados ​​(com duplicatas), gostaríamos de evitar o processamento de itens que já vimos antes. Não custa processar uma duplicata, é apenas uma perda de tempo. No entanto, se deixássemos de processar um elemento, seria catastrófico. Com um "filtro Bloom reverso", era possível armazenar os itens vistos com pouco espaço e evitar o processamento de duplicatas com alta probabilidade, testando a associação ao conjunto.

No entanto, parece que não consigo encontrar nada disso. Os mais próximos que encontrei são os " filtros Bloom retocados ", que permitem trocar falsos positivos selecionados por uma taxa de falsos negativos mais altos. No entanto, não sei o desempenho da estrutura de dados quando se deseja remover todos os falsos positivos.

Alguém viu algo assim? :)

Christopher Monsanto
fonte
3
O complemento do conjunto no qual estou interessado é infinito. Como eu o armazenaria?
Christopher Monsanto
11
Eu vejo o problema (os discos modernos ainda não são grandes o suficiente).
Dave Clarke
8
Se você tivesse essa estrutura de dados, poderia usá-la para "trapacear" usando-a em conjunto com um filtro de bloom regular e armazenar a associação exata do conjunto.
Mark Reitblatt
11
@MarkReitblatt os filtros e caches da Bloom são probabilísticos, e qualquer combinação dos mesmos será probabilística, ou seja, não será capaz de obter o teste exato de associação ao conjunto. :)
awdz9nld

Respostas:

25

Uma resposta é usar uma grande tabela de hash e, quando preenchida, comece a substituir elementos nela, em vez de encontrar slots vazios (inexistentes) em outros lugares para eles. Você não obtém a boa taxa fixa de respostas falsas que obtém com os filtros Bloom, mas é melhor que nada. Acredito que isso seja padrão, por exemplo, no software de xadrez para acompanhar as posições que já foram pesquisadas.

David Eppstein
fonte
Obrigado pela resposta. Sim, essa é a solução óbvia - se também é a solução padrão , parece que estou sem sorte. Ah bem.
Christopher Monsanto
2
Isso é chamado de cache mapeado direto e é comumente usado em CPUs. (Qualquer cache ou conjunto de hash com perdas se ajusta aos requisitos em vários graus). A taxa de erro é uma função da distribuição da função hash (avalanche) e o número de slots disponíveis no cache / conjunto - ajuste de acordo. :)
awdz9nld
Observe também que apenas as chaves literais podem ser armazenados sem a introdução de falsos positivos (por exemplo, o armazenamento de uma chave de hash)
awdz9nld
20

A resposta para esta pergunta é não". Para entender por que, podemos pensar em um caso muito extremo e como um filtro de bloom normal funcionaria em comparação com um filtro de bloom "Bizzaro World" teórico, que podemos chamar de "filtro de melancolia".

O que é ótimo em um filtro de bloom é que você pode fazer testes unilaterais para associação de itens (com falsos positivos) usando uma estrutura de dados que possui um tamanho fixo em relação à probabilidade de erro e ao número de itens armazenados. Os tamanhos dos itens em si não importam nada. Por exemplo, se tivéssemos um filtro de bloom configurado para armazenar até 1.000 itens com menos de 3% de erro, poderíamos armazenar 1.000 versões ligeiramente diferentes de todo o corpus da Wikipedia, com uma letra alterada em cada uma, e ainda assim obtenha as métricas desejadas e a estrutura de dados seria muito pequena (menos de um kilobyte). Obviamente, calcular esses hashes será um desafio, mas o princípio ainda é válido.

Agora, considere armazenar essas mesmas cordas enormes em um filtro sombrio! Agora só podemos ter falsos negativos. Portanto, se dissermos "sim, essa versão de todo o corpus da Wikipedia está nesse conjunto", então temos que estar absolutamente certos sobre isso. Isso significa que o hash não nos ajudará, pois sempre haverá outras strings com o mesmo valor. A única maneira de dizer "sim" e não se esqueça de armazenar toda a string ou alguns dados equivalentes do mesmo comprimento. Nem sempre conseguimos armazená-lo e dizer "não", mas, eventualmente, a taxa de erro nos alcança. O melhor que podemos fazer é a compactação, diminuindo o tamanho da estrutura até o produto da entropia dos dados armazenados e a precisão que desejamos.

Infelizmente, o filtro sombrio não existe. O armazenamento em cache é a única solução, mas não é exatamente o oposto de um filtro de bloom, pois seu tamanho será proporcional ao produto da quantidade de informações armazenadas e à taxa de precisão desejada do filtro. Obviamente, em muitos cenários do mundo real, grandes dados podem ser representados por um ID, portanto o armazenamento em cache ainda pode ser bastante aceitável. Mas é fundamentalmente diferente do poderoso filtro de floração.

pents90
fonte
checkout somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - o que há de errado nessa implementação? /
Yehosef
@Yehosef está bom e pode funcionar para suas necessidades, mas você notará que o autor fala sobre a existência de "alguns IDs que identificam completamente o evento". Portanto, o que é implementado ainda está efetivamente armazenando o objeto inteiro. Portanto, é uma variante de um cache. Um "oposto de um filtro de bloom" real, se existisse, não precisaria armazenar objetos inteiros.
usar o seguinte código
Ele mencionou alguns IDs que identificam o evento - não o objeto inteiro. Eu só preciso manter o "cache" no session_id - não no registro inteiro da interação. Mas ouvi dizer que não é o mesmo tipo de abordagem que o bloom ou um hiperloglog.
Yehosef
Na sua "prova", você assume que há um número ilimitado de entradas possíveis. No entanto, há casos em que o conjunto de entradas possíveis é conhecido antecipadamente. Por exemplo, para coleta de lixo de uma página de memória: você sabe quais entradas ela contém. Agora você cria um "filtro sombrio" que mapeia cada entrada possível para um índice 0..n. Agora, quando uma entrada for removida, defina o bit nesse índice. Quando todos os bits estão definidos, você pode coletar a página com lixo. O "filtro sombrio" é um MPHF. Para permitir falsos negativos, altere o MPHF para que algumas entradas sejam mapeadas para n + 1.
Thomas Mueller
@ThomasMueller Correto, estou assumindo o pior caso / adversário, que é o ponto de vista padrão da teoria do CS. É verdade que, se você tiver apenas um conjunto fixo de N entradas possíveis, existem muitas soluções simples, com apenas o espaço N de log necessário para cada item. O filtro bloom não tem essas limitações, no entanto.
usar o seguinte código
13

Você só quer um cache , mas está pensando nisso de uma maneira estranha.

Craig Gidney
fonte
11
... cuidado ao elaborar? É claro que um cache funcionaria, mas isso não é o ideal, portanto, uma pergunta sobre o estado da arte nas estruturas de dados probabilísticas. Para ser mais específico: as técnicas de cache que conheço exigem muito armazenamento. Quanto mais níveis de cache, mais armazenamento usado. Pode-se colocar um limite nos elementos armazenados no cache, fazer truques com padrões de uso, etc., mas isso ainda não chega nem perto da eficiência de espaço até a proporção de respostas falsas que um filtro Bloom fornece.
Christopher Monsanto
11
(continuação) Dito isto, eu poderia estar esquecendo uma técnica óbvia de armazenamento em cache que resolve todos os meus problemas. Nesse caso, você poderia explicitar essa técnica em vez de me fornecer um link para uma categoria geral na Wikipedia?
Christopher Monsanto
2

AVISO LEGAL: Eu não sou especialista em caches, então essa pode ser uma idéia ingênua, e também pode ser uma ideia conhecida da qual nunca ouvi falar antes. Então, desculpe-me se eu deixar de citar sua referência (se ela existir); e informe-me se houver uma referência para editar a postagem e adicioná-la. (Eu suspeito que ele possa ter uma referência porque é muito intuitivo).

cc

M. Alaggan
fonte
0

Eu usei árvores AVL (e às vezes vermelho-preto) com itens parciais para atuar como um filtro sem negativos negativos. Use apenas os primeiros X bytes do item ao inserir ou consultar a árvore. Como a estrutura de dados não é probabilística em forma, não há o risco de um falso positivo por colisão de bits. E, diferentemente do armazenamento em cache de todo o item, essa abordagem fornece um espaço máximo calculável. Você pode ajustar a taxa de falsos positivos considerando diferentes comprimentos de prefixo / profundidade de árvore em comparação com o custo de falsos positivos e espaço.

JRideout
fonte
Eu também queria tentar tentativas com dados de string, mas meus dados tendem a ser estruturas binárias compactadas.
JRideout
0

Eu acho que se pode provar um limite inferior afirmando que a estrutura de dados acima não pode existir. Basicamente, se a estrutura de dados usa m bits, um vetor de bits fixo (representação de uma entrada) pode corresponder a no máximo (((un) + n eps) \ escolher (un)) conjuntos por um argumento de contagem. Dado que 2 ^ m vezes esse número deve ser pelo menos (u \ escolha n) (todos os conjuntos devem ser representados), obtemos um limite inferior que está basicamente muito próximo de armazenar o conjunto S com precisão.

Mayank
fonte