论文标题
大约在数据流中计数子图
Approximately Counting Subgraphs in Data Streams
论文作者
论文摘要
估计数据流中的子图的数量是一个基本问题，在过去的十年中一直受到极大的关注。在本文中，我们给出了改进的流算法，以大约计算任意子图$ h $的出现数量（表示为$ \＃h $），当输入图$ g $表示为$ m $边缘的流。为了获得我们的算法，我们提供了一个通用转换，该转换将查询访问模型中的恒定转环sublinear-extrage算法转换为恒定的sublinear空间图形流算法。使用此转换，我们获得以下结果。 1。我们给出$（1 \pmε）$的$ 3 $ - 通道流算算法 - 近似于$ \＃h $中的$ \＃h $中的$ \ tilde {o}（\ frac {m^{ρ（h）}}} {ε^2 \ cdot \ cdot \＃h}）这改善了McGregor等人的结果。 [PODS 2016]，他给出了$（1 \ pmε）$的$ 3 $ - 通道插入算法 - 近似于$ \ tilde {o}的数字$ \＃t $的数字$ \＃t $获得学位。 2。我们为$（1 \ pmε）$ - 近似$ \＃k_r $ in $ \ \ tilde {o}（\ frac {\ frac {mλ^{r-2}} {ε^2 \ cdot \ cdot \＃k_r} $ ge $ r \ g g g g g g ge， $ k_r $是$ r $顶点的集团。这解决了Bera和Seshadhri [Pods 2020]的猜想。更笼统地，我们的还原将查询算法的适应性与相应流算法的通过复杂性相关联，并且适用于标准sublinear-time图查询模型中的所有算法，例如（增强）一般模型。
Estimating the number of subgraphs in data streams is a fundamental problem that has received great attention in the past decade. In this paper, we give improved streaming algorithms for approximately counting the number of occurrences of an arbitrary subgraph $H$, denoted $\# H$, when the input graph $G$ is represented as a stream of $m$ edges. To obtain our algorithms, we provide a generic transformation that converts constant-round sublinear-time graph algorithms in the query access model to constant-pass sublinear-space graph streaming algorithms. Using this transformation, we obtain the following results. 1. We give a $3$-pass turnstile streaming algorithm for $(1\pm ε)$-approximating $\# H$ in $\tilde{O}(\frac{m^{ρ(H)}}{ε^2\cdot \# H})$ space, where $ρ(H)$ is the fractional edge-cover of $H$. This improves upon and generalizes a result of McGregor et al. [PODS 2016], who gave a $3$-pass insertion-only streaming algorithm for $(1\pm ε)$-approximating the number $\# T$ of triangles in $\tilde{O}(\frac{m^{3/2}}{ε^2\cdot \# T})$ space if the algorithm is given additional oracle access to the degrees. 2. We provide a constant-pass streaming algorithm for $(1\pm ε)$-approximating $\# K_r$ in $\tilde{O}(\frac{mλ^{r-2}}{ε^2\cdot \# K_r})$ space for any $r\geq 3$, in a graph $G$ with degeneracy $λ$, where $K_r$ is a clique on $r$ vertices. This resolves a conjecture by Bera and Seshadhri [PODS 2020]. More generally, our reduction relates the adaptivity of a query algorithm to the pass complexity of a corresponding streaming algorithm, and it is applicable to all algorithms in standard sublinear-time graph query models, e.g., the (augmented) general model.
