2026-08-06T00:27:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17746 2024-03-06T11:00:23Z ddc:004 open_access

Enumerating Subgraphs of Constant Sizes in External Memory Deng, Shiyuan Silvestri, Francesco Tao, Yufei Subgraph Enumeration Conjunctive Queries External Memory Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiyuan Deng and Francesco Silvestri and Yufei Tao 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.4 urn:nbn:de:0030-drops-177460 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.4 eng https://creativecommons.org/licenses/by/4.0/legalcode