Estava lendo uma resposta aqui no SOpt (sim, é jocoso) e vi sobre Bloom Filter, queria mais informações sobre ele. Além do que é e para que serve, onde posso usar na prática?
-
Já leste esse ic.unicamp.br/~francesquini/mc202/files/aula26.pdf– user60252Commented 23/06/2020 às 19:46
-
@LeoCaracciolo sim.– Maniero ♦Commented 23/06/2020 às 19:49
-
eu tinha imaginado que sim :-)– user60252Commented 23/06/2020 às 19:52
-
até eu fiquei na curiosidade e fui procurar a respeito. o link psafe.com/blog/o-que-e-bloom-filter parece tirar 99% das duvidas sobre bloom filter de forma bem didatica. da uma olhada la– Alexandre GuerreiroCommented 24/06/2020 às 1:11
-
pois é cara, eu fui em busca do assunto também. Inicialmente não faz sentido nenhum ter uma estrutura que usa um hash probabilístico impreciso e com perda de desempenho no aumento do hash. Só fazendo o estudo assintético para ver se gera benefício em hashes pequenos. Ou isto, ou auxilia aplicações específicas que precisam eliminar os falsos negativos a qualquer custo. É de se pensar.– Breno ZanchettaCommented 24/06/2020 às 6:41
|
Mostrar mais 1 comentário
1 Resposta
Bloom filter é uma estrutura de dados criada em 1970 por Burton Howard Bloom (daí o nome bloom filter)
Ele é uma estrutura probabilística com as seguintes propriedades:
Possui eficiência de espaço
Permite falsos-positivos
Não permite falsos-negativos
Elementos podem ser adicionados ao filtro
Uma vez adicionados no filtro, elementos não podem ser removidos
Quanto mais itens dentro do filtro, maior a chance de haver falsos-positivos
São baseados em:
- Funções de hash
- Bit fields
Para um bom funcionamento são essenciais:
- Diversas funções de hash
- Espalhamento uniforme
Exemplo de aplicação pratica:
O seu browser verifica todos os endereços que você acessa para determinar se é um endereço seguro e poder te dar um aviso caso não seja.
- Há bilhões de endereços na Internet.
- Podemos supor com uma boa margem de segurança que dentre eles há alguns milhões de sites fraudulentos.
- Seria ineficiente fazer com que todos os computadores do mundo fizessem download de uma lista completa de sites fraudulentos.
- Também não seria muito eficiente checar um banco de dados central a cada endereço que fosse acessado.
- O browser faz download de um filtro de Bloom contendo todos os sites reconhecidos como inseguros
- A cada endereço acessado, o browser verifica se ele está contido no filtro.
- Se a consulta ao filtro indicar que o endereço não está contido, então com certeza o endereço não está na lista de sites inseguros e o acesso continua normalmente.
- Se o filtro indicar que está contido, então pode ser que site esteja na lista de endereços inseguros. Neste caso o seu browser faz uma consulta adicional a um banco de dados na Internet (esta sim com a lista completa)
- Note que caso seja um falso positivo, a única consequência é uma demora um pouco maior para acessar o site desejado.
Outras aplicações:
- Verificação preliminar de direitos de acesso
- Evitar recomendar artigos/páginas que o usuário não gostou ou já leu
- Evitar leituras no disco em bancos de dados
- Verificar senhas fracas
- Corretores ortográficos
- Dentre outros
Fonte: https://www.ic.unicamp.br/~francesquini/mc202/files/aula26.pdf
-
Diga-se de passagem que esse slide citado é muito ruim... o conteúdo pode até não ser, mas é complicado ler com aquela imagem de fundo e esquema de cores. Tirando isso achei interessante o assunto... Muito boa resposta. Commented 30/06/2020 às 1:46