Efficient Sampling of Random Permutations - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Journal of Discrete Algorithms Year : 2008

Efficient Sampling of Random Permutations

Jens Gustedt

Abstract

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.
Fichier principal
Vignette du fichier
perm.pdf (255.41 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00000900 , version 1 (02-12-2005)
inria-00000900 , version 2 (26-10-2006)

Identifiers

  • HAL Id : inria-00000900 , version 2

Cite

Jens Gustedt. Efficient Sampling of Random Permutations. Journal of Discrete Algorithms, 2008, 6 (1), pp.125-139. ⟨inria-00000900v2⟩
132 View
1491 Download

Share

Gmail Facebook X LinkedIn More