A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Min-Wise Independence vs. 3-Wise Independence Independência Min-Wise vs. Independência 3-Wise

Toshiya ITOH

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Uma família F de permutações independentes mínimas é conhecido por ser uma ferramenta útil para indexar documentos replicados na Web. Dizemos que uma família F de permutações em {0,1,. . . ,n-1} é independente minuciosamente se por algum X {0,1,. . . ,n-1} e qualquer x X, Pr[min {π(X)} =π(x)]= ||X||-1 quando π é escolhido uniformemente aleatoriamente de F, onde ||A|| é a cardinalidade de um conjunto finito A. Dizemos também que uma família F de permutações em {0,1,. . . ,n-1} é d-sábio independente se para qualquer distinto x1,x2,. . . ,xd {0,1,. . . , n-1} e qualquer distinto y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i = 1d π(xi) =π(yi)]= 1/{n(n-1)・・・ (n-d+1)} quando π é escolhido uniformemente aleatoriamente de F (observe que construções não triviais de dfamília independente e sábia F de permutações em {0,1,. . . ,n-1} são conhecidos apenas por d=2,3). Recentemente, Broder, et al. mostrou que qualquer família F de permutações independentes aos pares (2-sábios) se comporta próximo a uma família de permutações independentes min-sábias, ou seja, para qualquer X {0,1,. . . ,n-1} tal que 3 ||X|| =k n-2 e qualquer x X, (limite inferior) Pr[min {π(X)}=π(x)] 1/{2(k-1)}; (limite superior) Pr[min {π(X)}=π(x)] O(1 /k). Neste artigo, estendemos esses limites para a família de permutações independentes de 3 sentidos e mostramos que qualquer família de permutações independentes de 3 sentidos se comporta mais próximo de uma família de permutações independentes de mínimo, ou seja, para qualquer X {0,1,. . . ,n-1} tal que 4 ||X|| =k n-3 e qualquer x X, (limite inferior) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)2}; (limite superior) Pr[min {π(X)}=π(x)] 2/k - 2 /k + 1/(3kk).

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.957-966
Data de publicação
2002/05/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Palavra-chave