Os filtros de bloom são realmente mais rápidos que os hashes, mesmo levando em conta o cache?

14

Os filtros Bloom ficam ótimos quando você considera que pode determinar se um Int está em um conjunto com 99% de certeza em tempo constante. Mas também pode hashes, com a única diferença que, em um hash, na maioria das vezes você está acessando a memória apenas uma vez. Com os filtros bloom, você precisa acessá-los ~ 7 vezes por solicitação em lugares completamente distantes , então você teria vários erros de cache por solicitação.

Estou sentindo falta de algo?

    
por MaiaVictor 05.08.2014 / 15:11
fonte

2 respostas

29

Você está perdendo como as duas estruturas de dados lidam com colisões de hash. Os filtros bloom não armazenam os valores reais, portanto, o espaço necessário é o tamanho constante do array designado. Em vez disso, se você usar um hash tradicional, ele tentará armazenar todos os valores que você fornecer, aumentando assim com o tempo.

Considere uma função hash simplificada (apenas para um exemplo!) f(x) = x % 2 . Agora você insere os seguintes números inteiros: 2, 3, 4, 5, 6, 7 .

Hash padrão: os valores fornecidos serão divididos em hash e acabaremos com muitas colisões devido a f(2) = f(4) = f(6) = 0 e f(3) = f(5) = f(7) = 1 . No entanto, o hash armazena todos esses valores e poderá dizer a você que 8 não está armazenado nele. Como isso acontece? Ele rastreia as colisões e armazena todos os valores com o mesmo valor de hash; em seguida, quando você os consulta, ele também compara sua consulta. Então, vamos consultar o mapa para 8 : f(8) = 0 , para que ele analise um intervalo em que já inserimos 2, 4, 6 e precisa fazer três comparações para informar que 8 não fazia parte do entrada.

Bloom filter: Normalmente, cada valor de entrada é codificado em relação a k de funções hash diferentes. Novamente, para simplificar, vamos supor que apenas usamos a única função de hash f . Precisamos de uma matriz de 2 valores e, quando encontramos a entrada 2 , isso significa que, devido a f(2) = 0 , definimos o valor da matriz na posição 0 para o valor 1 . O mesmo acontece para 4 e 6 . Da mesma forma, as entradas 3, 5, 7 definem a posição da matriz 1 para o valor 1 . Agora, consultamos se 8 fazia parte da entrada: f(8) = 0 e a matriz na posição 0 é 1 , portanto, o filtro de bloom falsamente afirma que 8 era de fato parte da entrada.

Para ficar um pouco mais realista, vamos considerar que adicionamos uma segunda função hash g(x) = x % 10 . Com isso, o valor de entrada 2 leva a dois valores de hash f(2) = 0 e g(2) = 2 e as duas posições de matriz correspondentes serão definidas como 1 . Naturalmente, a matriz agora deve ter pelo menos o tamanho 10 . Porém, quando consultarmos 8 , verificaremos a matriz na posição 8 devido a g(8) = 8 e essa posição ainda será 0 . É por isso que funções hash adicionais diminuem os falsos positivos que você recebe.

Comparação: O filtro bloom usa k funções hash, o que significa que até k posições aleatórias de matrizes estão sendo acessadas. Mas esse número é exato. O hash, em vez disso, só garante um tempo de acesso constante amortizado, mas pode ser desregulado dependendo da natureza da função hash e dos dados de entrada. Por isso, normalmente é mais rápido, exceto pelos casos desengatados.

No entanto, uma vez que você tenha uma colisão de hash, o hash padrão terá que verificar a igualdade dos valores armazenados em relação ao valor da consulta. Essa verificação de igualdade pode ser arbitrariamente cara e nunca ocorrerá com um filtro de bloom.

Em termos de espaço, o filtro bloom é constante, já que nunca há necessidade de usar mais memória do que o array designado. Por outro lado, o hash cresce dinamicamente e pode ficar muito maior devido a ter que manter o controle dos valores de colisão.

Trade-off: Agora que você sabe o que é barato e o que não e em que circunstâncias, você deve ser capaz de ver o trade-off. Filtros Bloom são ótimos se você quiser detectar rapidamente que um valor foi visto anteriormente, mas pode viver com falsos positivos. Por outro lado, você pode escolher o mapa de hash se você quiser garantir a exatidão ao preço de não poder julgar seu tempo de execução, mas pode aceitar casos degenerados ocasionalmente, que podem ser muito mais lentos que a média.

Da mesma forma, se você estiver em um ambiente de memória limitada, talvez prefira filtrar filtros para garantir sua utilização de memória.

    
por 05.08.2014 / 15:42
fonte
5

Os casos de uso para filtros de bloom e hashes são distintos e, na maioria, disjuntos, portanto, comparação direta não faz sentido. Além disso, dependerá dos detalhes técnicos das implementações, pois há muitas maneiras de lidar com colisões de hash com diferentes trade-offs.

O filtro bloom pode responder se o elemento está em um conjunto para conjuntos enormes , com probabilidade razoável, mas não exatamente, usando uma quantidade modesta de memória. Enorme, como trilhões de elementos. Mas eles nunca são exatos. Você só pode reduzir a quantidade de falsos positivos usando mais memória ou mais funções hash.

Por outro lado, as tabelas de hash são exatas, mas precisam armazenar o conjunto. Assim, trilhões de elementos exigiriam terrabytes de memória (e isso é apenas trilhões americanos). Eles também podem armazenar dados extras para cada elemento, que filtros de bloom não podem.

So bloom filters são usados quando você tem um método lento de obter dados para algum membro (que envolve a consulta ao servidor, leituras do disco e outros) de um conjunto grande (que não cabe na memória ou é impraticável transferir para o cliente ou tal) e deseja evitar a execução da operação lenta para objetos que não estão no conjunto.

    
por 06.08.2014 / 16:04
fonte