Parallel peeling algorithms

被引：9
作者：
Jiang J. [1 ]
Mitzenmacher M. [1 ]
Thaler J. [2 ]
机构：
[1] Harvard University, School of Engineering and Applied Sciences, 33 Oxford Street, Cambridge, 02138, MA
[2] Saint Mary's Hall, Georgetown University, 37th and O Streets, NW, Washington, 20057-1232, DC
来源：
| 1600年 / Association for Computing Machinery, 2 Penn Plaza, Suite 701, New York, NY 10121-0701, United States卷 / 03期
基金：
美国国家科学基金会;
关键词：
Invertible Bloom lookup tables; Low-density parity check codes; Parallel algorithms; Peeling algorithms;
D O I：
10.1145/2938412
中图分类号：
学科分类号：
摘要：
The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k are removed until there are no vertices of degree less than k left. The remaining hypergraph is known as the k-core. In this article, we analyze parallel peeling processes, in which in each round, all vertices of degree less than k are removed. It is known that, below a specific edge-density threshold, the k-core is empty with high probability. We show that, with high probability, below this threshold, only 1 log((k-1)(r-1)) log log n+ O(1) rounds of peeling are needed to obtain the empty k-core for r-uniform hypergraphs. This bound is tight up to an additive constant. Interestingly, we show that, above this threshold, Ω(log n) rounds of peeling are required to find the nonempty k-core. Since most algorithms and data structures aim to peel to an empty k-core, this asymmetry appears fortunate. We verify the theoretical results both with simulation and with a parallel implementation using graphics processing units (GPUS). Our implementation provides insights into how to structure parallel peeling algorithms for efficiency in practice. © 2016 ACM.
引用
收藏
相关论文
共 22 条
  • [11] Karp R.M., Luby M., Meyer F., Efficient PRAM simulation on a distributed memory machine, Algorithmica, 16, 4-5, pp. 517-542, (1996)
  • [12] Kirsch A., Mitzenmacher M., Wieder U., More robust hashing: Cuckoo hashing with a stash, SIAM Journal on Computing, 39, 4, pp. 1543-1561, (2009)
  • [13] Le Cam L., An approximation theorem for the Poisson binomial distribution, Pacific Journal of Mathematics, 10, 4, pp. 1181-1197, (1960)
  • [14] Luby M., Mitzenmacher M., Shokrollahi M.A., Spielman D.A., Efficient erasure correcting codes, IEEE Transactions on Information Theory, 47, 2, pp. 569-584, (2001)
  • [15] Mitzenmacher M., The power of two choices in randomized load balancing, IEEE Transactions on Parallel Distributed Systems, 12, 10, pp. 1094-1104, (2001)
  • [16] Mitzenmacher M., Upfal E., Probability and Computing - Randomized Algorithms and Probabilistic Analysis, (2005)
  • [17] Mitzenmacher M., Varghese G., Biff (Bloom filter) codes: Fast error correction for large data sets, Proceedings of the International Symposium on Information Theory (ISIT'12, pp. 483-487, (2012)
  • [18] Mitzenmacher M., Vocking B., The asymptotics of selecting the shortest of two, improved, Proceedings of the 37th Annual Allerton Conference on Communication Control and Computing, pp. 326-327, (1999)
  • [19] Molloy M., Cores in random hypergraphs and Boolean formulas, Random Structures and Algorithms, 27, 1, pp. 124-135, (2005)
  • [20] Pagh R., Rodler F.F., Cuckoo hashing, Journal of Algorithms, 51, 2, pp. 122-144, (2004)
123