Hashing de conjuntos de números inteiros para teste de inclusão

10

Estou procurando uma função hash sobre os conjuntos H (.) E uma relação R (.,.) De modo que, se A for incluído em B, então R (H (A), H (B)). Obviamente, R (.,.) Deve ser fácil de verificar (tempo constante) e H (A) deve ser calculado em tempo linear.

Um exemplo de H e R é:

  • , onde k é um número inteiro fixo e h (x) uma função hash sobre números inteiros.H(A)=xA1<<(h(x)modk)
  • R (H (A), H (B)) = ((H (A) e H (B)) == H (A))

Existem outros bons exemplos? (bom é difícil de definir, mas intuitivamente se R (H (A), H (B)), então whp está incluído em B).

Edição posterior :

  1. Estou procurando uma família de funções de hash. Eu tenho muitos sets; 3-8 elementos em cada conjunto; 90% deles têm 3 ou 4 elementos. A função de hash de exemplo que eu dei não está muito bem distribuída para este caso.
  2. O número de bits de H (.) (No meu exemplo, k) que devem ser pequenos (ou seja, H (.) Devem caber em um número inteiro ou longo).
  3. Uma boa propriedade de R é que, se H (.) Possui k bits, então R (.,.) É verdadeiro para (3 ^ k - 2 ^ k) / 4 ^ k pares, ou seja. por muito poucos pares.
  4. Os filtros Bloom são especialmente bons para conjuntos grandes. Tentei usar o BF para esse problema, mas os melhores resultados foram com apenas uma função.

(crosspost do stackoverflow , não recebi uma resposta boa o suficiente)

Alexandru
fonte
"whp" sobre o que? Você assume que suas entradas são provenientes de uma determinada distribuição?
Jukka Suomela
E você está realmente procurando por uma única função hash fixa e não uma família de funções hash?
Jukka Suomela
@Jukka: Eu acho que ele quer dizer se R (H (A), H (B)), então com alta probabilidade, concluímos que A é um subconjunto de B. A probabilidade é assumida por escolhas aleatórias de A e B, bem como lançamentos internos de moedas de H e R (se houver).
MS Dousti 29/09/10
Estou procurando uma família de funções de hash. Meus conjuntos tendem a ser pequenos (3 a 8 elementos cada; 90% deles têm 3 ou 4 elementos); portanto, a função hash de exemplo que eu dei não é muito bem distribuída.
Alexandru
Uma boa propriedade de R é que, se H (.) Possui n bits, então R (.,.) É verdadeiro para (3 ^ n - 2 ^ n) / 4 ^ n pares, ou seja. por muito poucos pares.
Alexandru

Respostas:

10

(Essa resposta foi originalmente nos comentários, mas estou passando para uma resposta separada, por sugestão de Suresh.)

kh1h2h3m23=1/8thuns. Hash de cada conjunto no bit a bit ou nos hashes de seus elementos constituintes. Como seus conjuntos têm de 3 a 8 elementos, os hashes resultantes ficarão próximos dos metade, o que provavelmente é o que você deseja para manter a taxa de falsos positivos mais baixa.

Gn,pdkm/8m/8

Warren Schudy
fonte
Isso é particularmente bom para m grandes (32 ou 64), como você sugeriu.
Alexandru
4

mkm=64k=4

Warren Schudy
fonte
k
h1h2h3m
A vantagem dessa variação é apenas que ela faz melhor uso do paralelismo inerente às operações de palavras que a maioria dos computadores possui.
Warren Schudy
Warren, você deve postar isso como resposta. Merece votos
Suresh Venkat
2
@ Warren, @Suresh: Eu acho que faria mais sentido combinar essas duas respostas estreitamente relacionadas e depois excluir os comentários. Seria mais fácil de seguir, principalmente porque uma das respostas se refere aos parâmetros definidos na outra.
Jukka Suomela