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 条
  • [1] Achlioptas D., Molloy M., The solution space geometry of random linear equations, Random Structures and Algorithms, 46, 2, pp. 197-231, (2015)
  • [2] Azar Y., Broder A.Z., Karlin A.R., Upfal E., Balanced allocations, SIAM Journal on Computing, 29, 1, pp. 180-200, (1999)
  • [3] Broder A.Z., Frieze A.M., Upfal E., On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the 4th Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pp. 322-330, (1993)
  • [4] Chazelle B., Kilian J., Rubinfeld R., Tal A., The Bloomier filter: An efficient data structure for static support lookup tables, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04, pp. 30-39, (2004)
  • [5] Chung F.R.K., Lincoln Lu., Survey: Concentration inequalities and Martingale inequalities: A survey, Internet Mathematics, 3, 1, pp. 79-127, (2006)
  • [6] Colin C., The cores of random hypergraphs with a given degree sequence, Random Structures and Algorithms, 25, 4, pp. 353-375, (2004)
  • [7] Dietzfelbinger M., Goerdt A., Mitzenmacher M., Montanari A., Pagh R., Rink M., Tight thresholds for cuckoo hashing via XORSAT, Proceedings of the 37th International Colloquium of Automata, Languages and Programming (ICALP'10), Part I. Lecture Notes in Computer Science, Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis (Eds.), 6198, pp. 213-225, (2010)
  • [8] Eppstein D., Goodrich M.T., Uyeda F., Varghese G., What's the difference? Efficient set reconciliation without prior context, Proceedings of the ACM SIGCOMM 2011 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Srinivasan Keshav, Jörg Liebeherr, John W. Byers, and Jeffrey C. Mogul (Eds, pp. 218-229, (2011)
  • [9] Gao P., Analysis of the Parallel Peeling Algorithm: A Short Proof., (2014)
  • [10] Goodrich M.T., Mitzenmacher M., Invertible Bloom lookup tables, 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 792-799, (2011)
123