Document Open Access Logo

Enumerating Subgraphs of Constant Sizes in External Memory

Authors Shiyuan Deng, Francesco Silvestri, Yufei Tao

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.4.pdf
  • Filesize: 0.93 MB
  • 20 pages

Document Identifiers

Author Details

Shiyuan Deng
  • The Chinese University of Hong Kong, China
Francesco Silvestri
  • University of Padova, Italy
Yufei Tao
  • The Chinese University of Hong Kong, China

Funding

Shiyuan Deng and Yufei Tao were supported in part by GRF Projects 14207820, 14203421, and 14222822 from HKRGC. Francesco Silvestri was supported in part by PRIN 20174LF3T8 AHeAD and Uni-Impresa Big-Mobility projects, and by the Italian National Center for HPC, Big Data, and Quantum Computing.

Cite AsGet BibTex

Shiyuan Deng, Francesco Silvestri, and Yufei Tao. Enumerating Subgraphs of Constant Sizes in External Memory. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICDT.2023.4

Abstract

We present an indivisible I/O-efficient algorithm for subgraph enumeration, where the objective is to list all the subgraphs of a massive graph G : = (V, E) that are isomorphic to a pattern graph Q having k = O(1) vertices. Our algorithm performs O((|E|^{k/2})/(M^{{k/2}-1} B) log_{M/B}(|E|/B) + (|E|^ρ)/(M^{ρ-1} B) I/Os with high probability, where ρ is the fractional edge covering number of Q (it always holds ρ ≥ k/2, regardless of Q), M is the number of words in (internal) memory, and B is the number of words in a disk block. Our solution is optimal in the class of indivisible algorithms for all pattern graphs with ρ > k/2. When ρ = k/2, our algorithm is still optimal as long as M/B ≥ (|E|/B)^ε for any constant ε > 0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Information systems → Join algorithms
Keywords
  • Subgraph Enumeration
  • Conjunctive Queries
  • External Memory
  • Algorithms

Metrics

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

References

  1. Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of the ACM (CACM), 31(9):1116-1127, 1988. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  4. Kaleb Alway, Eric Blais, and Semih Salihoglu. Box covers and domain orderings for beyond worst-case join processing. In Proceedings of International Conference on Database Theory (ICDT), pages 3:1-3:23, 2021. Google Scholar
  5. 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 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2315-2332, 2021. Google Scholar
  6. Andreas Bjorklund, Petteri Kaski, and Lukasz Kowalik. Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Transactions on Algorithms, 13(4):48:1-48:26, 2017. Google Scholar
  7. Andreas Bjorklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 223-234, 2014. Google Scholar
  8. N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal of Computing, 14(1):210-223, 1985. Google Scholar
  9. Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 151-158, 1971. Google Scholar
  10. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 210-223, 2017. Google Scholar
  11. David Eppstein. Arboricity and bipartite subgraph listing algorithms. Information Processing Letters (IPL), 51(4):207-211, 1994. Google Scholar
  12. David Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl., 3(3):1-27, 1999. Google Scholar
  13. David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Manuel R. Torres. 2-3 cuckoo filters for faster triangle listing and set intersection. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 247-260, 2017. Google Scholar
  14. David Eppstein, Maarten Loffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In International Symposium on Algorithms and Computation (ISAAC), volume 6506, pages 403-414, 2010. Google Scholar
  15. Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Detecting and counting small pattern graphs. SIAM J. Discret. Math., 29(3):1322-1339, 2015. Google Scholar
  16. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. Journal of Computer and System Sciences (JCSS), 78(3):698-706, 2012. Google Scholar
  17. Pierre-Louis Giscard, Nils M. Kriege, and Richard C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 81(7):2716-2737, 2019. Google Scholar
  18. Chinh T. Hoang, Marcin Kaminski, Joe Sawada, and R. Sritharan. Finding and listing induced paths and cycles. Discrete Applied Mathematics, 161(4-5):633-641, 2013. Google Scholar
  19. Xiao Hu and Ke Yi. Towards a worst-case i/o-optimal algorithm for acyclic joins. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 135-150, 2016. Google Scholar
  20. Xiaocheng Hu, Miao Qiao, and Yufei Tao. I/O-efficient join dependency testing, loomis-whitney join, and triangle enumeration. Journal of Computer and System Sciences (JCSS), 82(8):1300-1315, 2016. Google Scholar
  21. Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung. I/O-Efficient Algorithms on Triangle Listing and Counting. ACM Transactions on Database Systems (TODS), 39(4):27:1-27:30, 2014. Google Scholar
  22. Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures and Algorithms, 24(3):234-248, 2004. Google Scholar
  23. Bas Ketsman, Dan Suciu, and Yufei Tao. A near-optimal parallel algorithm for joining binary relations. Log. Methods Comput. Sci., 18(2), 2022. Google Scholar
  24. Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst-case and beyond. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 213-228, 2015. Google Scholar
  25. Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Re, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems (TODS), 41(4):22:1-22:45, 2016. Google Scholar
  26. Ton Kloks, Dieter Kratsch, and Haiko Müller. Finding and counting small induced subgraphs efficiently. Information Processing Letters (IPL), 74(3-4):115-121, 2000. Google Scholar
  27. Paraschos Koutris, Paul Beame, and Dan Suciu. Worst-case optimal algorithms for parallel query processing. In Proceedings of International Conference on Database Theory (ICDT), pages 8:1-8:18, 2016. Google Scholar
  28. Gonzalo Navarro, Juan L. Reutter, and Javiel Rojas-Ledesma. Optimal joins using compact data structures. In Proceedings of International Conference on Database Theory (ICDT), volume 155, pages 21:1-21:21, 2020. Google Scholar
  29. Jaroslav Nesetril and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  30. Hung Q. Ngo, Dung T. Nguyen, Christopher Re, and Atri Rudra. Beyond worst-case analysis for joins with minesweeper. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 234-245, 2014. Google Scholar
  31. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-Case Optimal Join Algorithms: [Extended Abstract]. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 37-48, 2012. Google Scholar
  32. Hung Q. Ngo, Ely Porat, Christopher Re, and Atri Rudra. Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):16:1-16:40, 2018. Google Scholar
  33. Hung Q. Ngo, Christopher Re, and Atri Rudra. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec., 42(4):5-16, 2013. Google Scholar
  34. Anna Pagh and Rasmus Pagh. Scalable computation of acyclic joins. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 225-232, 2006. Google Scholar
  35. Rasmus Pagh and Francesco Silvestri. The input/output complexity of triangle enumeration. In Proceedings of ACM Symposium on Principles of Database Systems (PODS), pages 224-233, 2014. Google Scholar
  36. Edward R. Scheinerman and Daniel H. Ullman. Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Wiley, New York, 1997. Google Scholar
  37. Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of International Conference on Database Theory (ICDT), pages 96-106, 2014. Google Scholar
  38. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal of Computing, 42(3):831-854, 2013. 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 Imprint Privacy Contact