La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Construire une famille optimale de permutations indépendantes min-wise

Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Une Famille C de permutations indépendantes au niveau minimum est connu pour être un outil utile pour indexer les documents répliqués sur le Web. Pour tout entier n>0, une famille C de permutations sur [n]={1,2,. . . ,n} est dit être indépendant en termes de min si pour tout (non vide) X [n] et n'importe quel x X, Pr (min{π(X)} = π(x))= ||X||-1 lorsque π est choisi uniformément au hasard parmi C, où ||A|| est la cardinalité d'un ensemble fini A. Pour tout entier n>0, on sait que (1) ||C|| lcm(n,n-1,. . . ,2,1) = enon) pour toute famille C de permutations indépendantes min-wise sur [n]; (2) il existe un temps polynomial échantillonnable C famille de permutations indépendantes min-wise sur [n] tel que ||C|| 4n. Cependant, il n’est pas clair s’il existe une famille indépendante au niveau min. C tel que ||C|| = lcm(n,n-1,. . . ,2,1) pour chaque entier n>0 et comment construire une telle famille C de permutations indépendantes au minimum pour chaque entier n>0 s'il existe. Dans cet article, nous allons construire une famille Fn de permutations pour chaque entier n>0 et montre que Fn est indépendant au niveau minimum et ||Fn|| = lcm(n,n-1,. . . ,2,1). De plus, nous présentons un Temps polynomial algorithme d'échantillonnage pour la famille. Ainsi la famille Fn des permutations indépendantes min-wise est optimaux au sens de la taille de la famille et est facile à mettre en œuvre en raison de son échantillonnage temporel polynomial.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.747-755
Date de publication
2000/04/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Mots-clés

Table des matières