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.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2008, 6 (1), pp.125-139
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00000900
Contributeur : Jens Gustedt <>
Soumis le : jeudi 26 octobre 2006 - 13:57:57
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : lundi 22 octobre 2012 - 11:51:17

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

715