Skip to Main content Skip to Navigation
Journal articles

Efficient Sampling of Random Permutations

Jens Gustedt 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000900
Contributor : Jens Gustedt <>
Submitted on : Thursday, October 26, 2006 - 1:57:57 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Monday, October 22, 2012 - 11:51:17 AM

Files

Identifiers

  • HAL Id : inria-00000900, version 2

Collections

Citation

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

Share

Metrics

Record views

342

Files downloads

1481