Document Open Access Logo

Massively Parallel Algorithms for Small Subgraph Counting

Authors Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrović

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.39.pdf
  • Filesize: 0.97 MB
  • 28 pages

Document Identifiers

Author Details

Amartya Shankha Biswas
  • CSAIL, MIT, Cambridge, MA, USA
Talya Eden
  • CSAIL, MIT, Cambridge MA, USA
  • Boston University, MA, USA
Quanquan C. Liu
  • Northwestern University, Evanston, IL, USA
Ronitt Rubinfeld
  • CSAIL, MIT, Cambridge, MA, USA
Slobodan Mitrović
  • University of California Davis, CA, USA

Funding

  • Mitrović, Slobodan: S. Mitrović was supported by the Swiss NSF grant No. P400P2_191122/1 and FinTech@CSAIL.

Cite As Get BibTex

Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović. Massively Parallel Algorithms for Small Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 39:1-39:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.39

Abstract

Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing prevalence of large network datasets. The Massively Parallel Computation (MPC) model is the de-facto standard for studying graph algorithms in these frameworks theoretically. Subgraph counting is one such fundamental problem in analyzing massive graphs, with the main algorithmic challenges centering on designing methods which are both scalable and accurate.
Given a graph G = (V, E) with n vertices, m edges and T triangles, our first result is an algorithm that outputs a (1+ε)-approximation to T, with asymptotically optimal round and total space complexity provided any S ≥ max{(√ m, n²/m)} space per machine and assuming T = Ω(√{m/n}). Our result gives a quadratic improvement on the bound on T over previous works. We also provide a simple extension of our result to counting any subgraph of k size for constant k ≥ 1. Our second result is an O_δ(log log n)-round algorithm for exactly counting the number of triangles, whose total space usage is parametrized by the arboricity α of the input graph. We extend this result to exactly counting k-cliques for any constant k. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most 5 can be implemented in the MPC model in Õ_δ(√{log n}) rounds, O(n^δ) space per machine and O(mα³) total space.
In addition to our theoretical results, we simulate our triangle counting algorithms in real-world graphs obtained from the Stanford Network Analysis Project (SNAP) database. Our results show that both our approximate and exact counting algorithms exhibit improvements in terms of round complexity and approximation ratio, respectively, compared to two previous widely used algorithms for these problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Computing methodologies → Massively parallel algorithms
Keywords
  • triangle counting
  • massively parallel computation
  • clique counting
  • approximation algorithms
  • subgraph counting

Metrics

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

Related Versions

References

  1. GraphChallenge. URL: http://graphchallenge.mit.edu/.
  2. Foto N Afrati, Dimitris Fotakis, and Jeffrey D Ullman. Enumerating subgraph instances using map-reduce. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 62-73. IEEE, 2013. Google Scholar
  3. Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, Nick G. Duffield, and Theodore L. Willke. Graphlet decomposition: framework, algorithms, and applications. Knowl. Inf. Syst., 50(3):689-722, 2017. Google Scholar
  4. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In SPAA, pages 202-211, 2015. Google Scholar
  5. Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. Sublinear-time algorithms for counting star subgraphs via edge sampling. Algorithmica, 80(2):668-697, 2018. Google Scholar
  6. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544-556, 2009. URL: https://doi.org/10.1007/s00453-008-9204-0.
  7. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  8. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In STOC, pages 574-583, 2014. Google Scholar
  9. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 14:1-14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.14.
  10. Shaikh Arifuzzaman, Maleq Khan, and Madhav Marathe. Patric: A parallel algorithm for counting triangles in massive networks. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 529-538, 2013. Google Scholar
  11. Sepehr Assadi. Simple round compression for parallel vertex cover. arXiv preprint, 2017. URL: http://arxiv.org/abs/1709.04599.
  12. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. Google Scholar
  13. Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. In ITCS, volume 124 of LIPIcs, pages 6:1-6:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  14. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.02974.
  15. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 461-470. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331596.
  16. Ziv Bar-Yossef, Ravi Kumar, and D Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 623-632. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  17. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32Nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 273-284, 2013. Google Scholar
  18. Paul Beame, Paraschos Koutris, and Dan Suciu. Skew in parallel query processing. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 212-223, 2014. Google Scholar
  19. Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively parallel computation of matching and MIS in sparse graphs. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 481-490. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331609.
  20. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Semi-mapreduce meets congested clique. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.10297.
  21. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and massively parallel algorithms for edge coloring. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 15:1-15:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.15.
  22. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab Mirrokni, and Warren Schudy. Massively parallel computation via remote memory access. ACM Transactions on Parallel Computing, 8(3):1-25, 2021. Google Scholar
  23. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. Exponentially faster massively parallel maximal matching. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1637-1649. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00096.
  24. Suman K Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. In 34th Symposium on Theoretical Aspects of Computer Science, 2017. Google Scholar
  25. Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.38.
  26. Suman K Bera, Noujan Pashanasangi, and C Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: the barrier of long induced cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2315-2332. SIAM, 2021. Google Scholar
  27. Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrovic, and Ronitt Rubinfeld. Parallel algorithms for small subgraph counting. CoRR, abs/2002.08299, 2020. URL: http://arxiv.org/abs/2002.08299.
  28. Andreas Bjöklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting paths and packings in halves. Algorithms - ESA 2009, pages 578-586, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_52.
  29. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: quantum and MapReduce. In SODA, pages 1170-1189, 2018. Google Scholar
  30. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Breaking the linear-memory barrier in MPC: Fast MIS on trees with n^ε memory per machine. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.06748.
  31. Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In International Colloquium on Automata, Languages, and Programming, pages 244-254. Springer, 2013. Google Scholar
  32. Marco Bressan. Faster subgraph counting in sparse graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  33. Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. Distributed Computing, 32(6):461-478, 2019. Google Scholar
  34. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (Δ+1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 471-480. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331607.
  35. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on computing, 14(1):210-223, 1985. Google Scholar
  36. Shumo Chu and James Cheng. Triangle listing in massive networks and its applications. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 672-680, 2011. Google Scholar
  37. Jonathan Cohen. Graph twiddling in a mapreduce world. Computing in Science & Engineering, 11(4):29-41, 2009. Google Scholar
  38. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. SIAM J. Comput., 49(5), 2020. URL: https://doi.org/10.1137/18M1197655.
  39. Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs*. In Proceedings of the 2018 World Wide Web Conference, WWW ’18, pages 589-598, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. URL: https://doi.org/10.1145/3178876.3186125.
  40. V. S. Dave, N. K. Ahmed, and M. Hasan. PE-CLoG: Counting edge-centric local graphlets. In IEEE International Conference on Big Data, pages 586-595, 2017. Google Scholar
  41. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107-113, 2008. Google Scholar
  42. Laxman Dhulipala, Quanquan C. Liu, Julian Shun, and Shangdi Yu. Parallel batch-dynamic k-clique counting. In Michael Schapira, editor, 2nd Symposium on Algorithmic Principles of Computer Systems, APOCS 2020, Virtual Conference, January 13, 2021, pages 129-143. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976489.10.
  43. Danny Dolev, Christoph Lenzen, and Shir Peled. “Tri, Tri again”: Finding triangles and small subgraphs in a distributed setting. Distributed Computing, pages 195-209, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_14.
  44. Talya Eden, Amit Levi, Dana Ron, and C Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, 46(5):1603-1646, 2017. Google Scholar
  45. Talya Eden, Dana Ron, and C. Seshadhri. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1467-1478, 2020. URL: https://doi.org/10.1137/1.9781611975994.89.
  46. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci., 326(1–3):57-67, October 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009.
  47. Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. Distributed estimation of graph 4-profiles. In International Conference on World Wide Web (WWW), pages 483-493, 2016. Google Scholar
  48. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. ACM Journal of Experimental Algorithms, 18(3):364-375, 2013. URL: https://doi.org/10.1145/2543629.
  49. Irene Finocchi, Marco Finocchi, and Emanuele G Fusco. Clique counting in mapreduce: Algorithms and experiments. Journal of Experimental Algorithmics (JEA), 20:1-20, 2015. Google Scholar
  50. Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted matchings via unweighted augmentations. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 491-500. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331603.
  51. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In PODC. https://arxiv.org/abs/1802.08237, 2018.
  52. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1650-1663. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00097.
  53. Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrović. Improved parallel algorithms for density-based network clustering. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2201-2210, Long Beach, California, USA, 09-15 June 2019. PMLR. URL: http://proceedings.mlr.press/v97/ghaffari19a.html.
  54. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1260-1279. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.77.
  55. Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1636-1653. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.99.
  56. Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, pages 159-167, 2006. URL: https://doi.org/10.1007/11917496_15.
  57. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Proceedings of the 22Nd International Conference on Algorithms and Computation, ISAAC'11, pages 374-383, Berlin, Heidelberg, 2011. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-25591-5_39.
  58. Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. Greedy and local ratio algorithms in the MapReduce model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 43-52, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3210377.3210386.
  59. James W Hegeman and Sriram V Pemmaraju. Lessons from the congested clique applied to MapReduce. Theoretical Computer Science, 608:268-281, 2015. Google Scholar
  60. Tomaz Hocevar and Janez Demsar. A combinatorial approach to graphlet counting. Bioinformatics, pages 559-65, 2014. Google Scholar
  61. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In STOC, pages 798-811, 2017. Google Scholar
  62. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In ACM SIGOPS operating systems review, volume 41(3), pages 59-72. ACM, 2007. Google Scholar
  63. Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, and Nikos Parotsidis. Dynamic algorithms for the massively parallel computation model. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 49-58. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323202.
  64. Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Proceedings of the 26th International Conference on World Wide Web, pages 441-449, 2017. Google Scholar
  65. Madhav Jha, Comandur Seshadhri, and Ali Pinar. A space efficient streaming algorithm for triangle counting using the birthday paradox. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 589-597, 2013. Google Scholar
  66. Daniel M Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In International Colloquium on Automata, Languages, and Programming, pages 598-609. Springer, 2012. Google Scholar
  67. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In SODA, pages 938-948, 2010. Google Scholar
  68. Tamara G Kolda, Ali Pinar, Todd Plantenga, C Seshadhri, and Christine Task. Counting triangles in massive graphs with mapreduce. SIAM Journal on Scientific Computing, 36(5):S48-S77, 2014. Google Scholar
  69. Mihail N Kolountzakis, Gary L Miller, Richard Peng, and Charalampos E Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics, 8(1-2):161-185, 2012. Google Scholar
  70. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1272-1287. SIAM, 2016. Google Scholar
  71. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. CoRR, abs/1907.05391, 2019. URL: http://arxiv.org/abs/1907.05391.
  72. Longbin Lai, Lu Qin, Xuemin Lin, and Lijun Chang. Scalable subgraph enumeration in mapreduce. Proceedings of the VLDB Endowment, 8(10):974-985, 2015. Google Scholar
  73. Matthieu Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science, 407(1-3):458-473, 2008. Google Scholar
  74. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in MapReduce. In SPAA, pages 85-94, 2011. Google Scholar
  75. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in o (log log n) communication rounds. SIAM Journal on Computing, 35(1):120-131, 2005. Google Scholar
  76. Andrew McGregor, Sofya Vorotnikova, and Hoa T Vu. Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 401-411, 2016. Google Scholar
  77. Krzysztof Onak. Round compression for parallel graph algorithms in strongly sublinear space. CoRR, abs/1807.08745, 2018. URL: http://arxiv.org/abs/1807.08745.
  78. Rasmus Pagh and Charalampos E Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112(7):277-281, 2012. Google Scholar
  79. Ha-Myung Park and Chin-Wan Chung. An efficient mapreduce algorithm for counting triangles in a very large graph. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 539-548, 2013. Google Scholar
  80. Ha-Myung Park, Francesco Silvestri, U Kang, and Rasmus Pagh. Mapreduce triangle enumeration with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 1739-1748, 2014. Google Scholar
  81. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610, 2010. URL: https://doi.org/10.1145/1806689.1806772.
  82. Ali Pinar, C. Seshadhri, and Vaidyanathan Vishal. ESCAPE: Efficiently counting all 5-vertex subgraphs. In International Conference on World Wide Web (WWW), pages 1431-1440, 2017. Google Scholar
  83. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits: (on lower bounds for modern parallel computation). In SPAA, pages 1-12, 2016. Google Scholar
  84. Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Experimental and Efficient Algorithms, pages 606-609. Springer, 2005. Google Scholar
  85. Comandur Seshadhri, Ali Pinar, and Tamara G Kolda. Triadic measures on graphs: The power of wedge sampling. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 10-18. SIAM, 2013. Google Scholar
  86. Jessica Shi, Laxman Dhulipala, and Julian Shun. Parallel clique counting and peeling algorithms. CoRR, abs/2002.10047, 2020. URL: http://arxiv.org/abs/2002.10047.
  87. Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. Patterns and anomalies in k-cores of real-world graphs with applications. Knowledge and Information Systems, 54(3):677-710, 2018. Google Scholar
  88. J. Shun and K. Tangwongsan. Multicore triangle computations without tuning. In 2015 IEEE 31st International Conference on Data Engineering, pages 149-160, April 2015. URL: https://doi.org/10.1109/ICDE.2015.7113280.
  89. Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In Proceedings of the 20th international conference on World wide web, pages 607-614, 2011. Google Scholar
  90. Charalampos E Tsourakakis, U Kang, Gary L Miller, and Christos Faloutsos. Doulion: counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 837-846, 2009. Google Scholar
  91. Virginia Vassilevska. Efficient algorithms for clique problems. Information Processing Letters, 109(4):254-257, 2009. URL: https://doi.org/10.1016/j.ipl.2008.10.014.
  92. Mark N Wegman and J Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of computer and system sciences, 22(3):265-279, 1981. Google Scholar
  93. Tom White. Hadoop: The definitive guide. " O'Reilly Media, Inc.", 2012. Google Scholar
  94. Jin-Hyun Yoon and Sung-Ryul Kim. Improved sampling for triangle counting with mapreduce. In International Conference on Hybrid Information Technology, pages 685-689. Springer, 2011. Google Scholar
  95. Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. HotCloud, 10(10-10):95, 2010. 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