Treffer: Efficient Sampling of Random Permutations
Title:
Efficient Sampling of Random Permutations
Authors:
Contributors:
Algorithms for the Grid (ALGORILLE), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Grid'5000
Source:
Journal of Discrete Algorithms. 6(1):125-139
Publisher Information:
CCSD; Elsevier, 2008.
Publication Year:
2008
Collection:
collection:CNRS
collection:INRIA
collection:INPL
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:GRID5000
collection:TESTALAIN1
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:SLICES-FR
collection:AM2I-UL
collection:INRIA
collection:INPL
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:GRID5000
collection:TESTALAIN1
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:SLICES-FR
collection:AM2I-UL
Subject Terms:
random permutations, random shuffling, coarse grained parallelism, external memory algorithms, uniformly generated communication matrix, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.1: Combinatorics, G.2.1.3: Permutations and combinations, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Original Identifier:
HAL:
Document Type:
Zeitschrift
article<br />Journal articles
Language:
English
ISSN:
1570-8667
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00000900v2
Database:
HAL
Weitere Informationen
We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external memory. In contrast to previously known work for parallel setups, our method is able to fulfill the three criteria of uniformity, work-optimality and balance among the processors simultaneously. To guarantee the uniformity we investigate the matrix of communication requests between the processors. We show that its distribution is a generalization of the multivariate hypergeometric distribution and we give algorithms to sample it efficiently in the two settings.