Document Open Access Logo

Simple Concurrent Labeling Algorithms for Connected Components

Authors Sixue Liu, Robert E. Tarjan

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.3.pdf
  • Filesize: 0.66 MB
  • 20 pages

Document Identifiers

Author Details

Sixue Liu
Robert E. Tarjan

Cite As Get BibTex

Sixue Liu and Robert E. Tarjan. Simple Concurrent Labeling Algorithms for Connected Components. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.3

Abstract

We present new concurrent labeling algorithms for finding connected components, and we study their theoretical efficiency. Even though many such algorithms have been proposed and many experiments with them have been done, our algorithms are simpler. We obtain an O(lg n) step bound for two of our algorithms using a novel multi-round analysis. We conjecture that our other algorithms also take O(lg n) steps but are only able to prove an O(lg^2 n) bound. We also point out some gaps in previous analyses of similar algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.

Subject Classification

Keywords
  • Connected Components
  • Concurrent Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 674-685, 2018. Google Scholar
  2. Baruch Awerbuch and Yossi Shiloach. New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM. IEEE Trans. Computers, 36(10):1258-1263, 1987. Google Scholar
  3. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query Processing. J. ACM, 64(6):40:1-40:58, 2017. Google Scholar
  4. Paul Burkhardt. Graph connectivity in log-diameter steps using label propagation. CoRR, 2018. URL: http://arxiv.org/abs/1808.06705.
  5. Stephen A. Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM J. Comput., 15(1):87-97, 1986. Google Scholar
  6. Steve Goddard, Subodh Kumar, and Jan F. Prins. Connected components algorithms for mesh-connected parallel computers. In Parallel Algorithms, Proceedings of a DIMACS Workshop, Brunswick, New Jersey, USA, October 17-18, 1994, pages 43-58, 1994. Google Scholar
  7. John Greiner. A Comparison of Parallel Algorithms for Connected Components. In SPAA, pages 16-25, 1994. Google Scholar
  8. Shay Halperin and Uri Zwick. An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM. J. Comput. Syst. Sci., 53(3):395-416, 1996. Google Scholar
  9. Shay Halperin and Uri Zwick. Optimal randomized EREW PRAM algorithms for finding spanning forests. Journal of Algorithms, 39(1):1-46, 2001. Google Scholar
  10. Tsan-Sheng Hsu, Vijaya Ramachandran, and Nathaniel Dean. Parallel implementation of algorithms for finding connected components in graphs. Parallel Algorithms: Third DIMACS Implementation Challenge, October 17-19, 1994, 30:20, 1997. Google Scholar
  11. Siddhartha V. Jayanti and Robert E. Tarjan. A Randomized Concurrent Algorithm for Disjoint Set Union. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 75-82, 2016. Google Scholar
  12. Donald B. Johnson and Panagiotis Takis Metaxas. A Parallel Algorithm for Computing Minimum Spanning Trees. J. Algorithms, 19(3):383-401, 1995. Google Scholar
  13. Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, pages 135-146, 2010. Google Scholar
  14. Frank McSherry, Michael Isard, and Derek Gordon Murray. Scalability! But at what COST? In 15th Workshop on Hot Topics in Operating Systems, HotOS XV, Kartause Ittingen, Switzerland, May 18-20, 2015, 2015. Google Scholar
  15. Vibhor Rastogi, Ashwin Machanavajjhala, Laukik Chitnis, and Anish Das Sarma. Finding connected components in map-reduce in logarithmic rounds. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pages 50-61, 2013. Google Scholar
  16. John H Reif. Optimal Parallel Algorithms for Graph Connectivity. Technical report, Harvard University Cambridge, MA, Aiken Computation Lab, 1984. Google Scholar
  17. Yossi Shiloach and Uzi Vishkin. An O(log n) Parallel Connectivity Algorithm. J. Algorithms, 3(1):57-67, 1982. Google Scholar
  18. Stergios Stergiou, Dipen Rughwani, and Kostas Tsioutsiouliklis. Shortcutting Label Propagation for Distributed Connected Components. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018, pages 540-546, 2018. Google Scholar
  19. Robert Endre Tarjan and Jan van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, 31(2):245-281, 1984. Google Scholar
  20. Leslie G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103-111, 1990. Google Scholar
  21. Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, and Yingyi Bu. Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees. PVLDB, 7(14):1821-1832, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact