Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

article · ACM Transactions on Parallel Computing · 2016

Parallel Peeling Algorithms

Jiayang Jiang, Michael Mitzenmacher, Justin Thaler

Cited by 17Open access

Abstract

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.

Cite this paper

APA 7

Jiang, J., Mitzenmacher, M., & Thaler, J. (2016). Parallel Peeling Algorithms. ACM Transactions on Parallel Computing, 3(1), 1–27. https://doi.org/10.1145/2938412

MLA 9

Jiang, Jiayang, et al. “Parallel Peeling Algorithms.” ACM Transactions on Parallel Computing, vol. 3, no. 1, 2016, pp. 1–27, https://doi.org/10.1145/2938412.

Chicago

Jiang, Jiayang, Michael Mitzenmacher, and Justin Thaler. 2016. “Parallel Peeling Algorithms.” ACM Transactions on Parallel Computing 3 (1): 1–27. https://doi.org/10.1145/2938412.

Harvard

Jiang, J., Mitzenmacher, M. and Thaler, J. (2016) ‘Parallel Peeling Algorithms’, ACM Transactions on Parallel Computing, 3(1), pp. 1–27. Available at: https://doi.org/10.1145/2938412.

BibTeX
@article{jiang2016parallel,
  title = {{Parallel Peeling Algorithms}},
  author = {Jiang, Jiayang and Mitzenmacher, Michael and Thaler, Justin},
  journal = {ACM Transactions on Parallel Computing},
  volume = {3},
  number = {1},
  pages = {1--27},
  year = {2016},
  doi = {10.1145/2938412}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers