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

Constructing an Optimal Family of Min-Wise Independent Permutations Construindo uma família ideal de permutações independentes min-wise

Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Uma família C de permutações independentes mínimas é conhecido por ser uma ferramenta útil para indexar documentos replicados na Web. Para qualquer número inteiro n>0, uma família C de permutações em [n]={1,2,. . . ,n} é dito ser independente minuciosamente if for any (não vazio) X [n] e qualquer x X, Pr ( min {π(X)} =π(x))= ||X||-1 quando π é escolhido uniformemente aleatoriamente de C, onde ||A|| é a cardinalidade de um conjunto finito A. Para qualquer número inteiro n>0, sabe-se que (1) ||C|| lcm (n,n-1,. . . ,2,1) = enão) para qualquer família C de permutações independentes mínimas em [n]; (2) existe uma amostra em tempo polinomial C família de permutações independentes min-wise em [n] tal que ||C|| 4n. No entanto, não está claro se existe uma família independente minuciosamente C tal que ||C|| = lcm(n,n-1,. . . ,2,1) para cada número inteiro n>0 e como construir tal família C de permutações independentes mínimas para cada número inteiro n>0 se existir. Neste artigo, construiremos uma família Fn de permutações para cada número inteiro n>0 e mostre que Fn é minuciosamente independente e ||Fn|| = lcm(n,n-1,. . . ,2,1). Além disso, apresentamos uma tempo polinomial algoritmo de amostragem para a família. Assim a família Fn de permutações independentes mínimas é ideal no sentido do tamanho da família e é fácil de implementar devido à sua amostragem em tempo polinomial.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.747-755
Data de publicação
2000/04/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Algoritmos e estruturas de dados

autores

Palavra-chave