Counting Simplices in Hypergraph Streams
Counting Simplices in Hypergraph Streams
复制标题
DOI：
10.4230/lipics.esa.2022.32
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Amit Chakrabarti;Themistoklis K. Haris
中科院分区：
文献类型：
--
作者：
Amit Chakrabarti;Themistoklis K. Haris
我们考虑空间有效地估计超图流中单纯形数量的问题。这是对图流中三角形数量的估计问题的最自然的超图概括。我们的输入是一个 $k$ 均匀超图 $H$，具有 $n$ 个顶点和 $m$ 个超边。 $H$ 中的 $k$-单纯形是 $k+1$ 个顶点 $X$ 上的子超图，使得 $X$ 中所有 $k+1$ 可能的超边都存在于 $H$ 中。目标是处理 $H$ 的超边流并计算 $T_k(H)$ 的良好估计，即 $H$ 中 $k$-单纯形的数量。我们针对这个问题设计了一套算法。在 $T_k(H) \ge T$ 的承诺下，我们的算法最多使用四次传递，并且总共意味着每个固定 $k \ge 3$ 的空间界限为 $O( \epsilon^{-2} \log\delta^{-1} \text{polylog} n \cdot \min\{ m^{1+1/k}/T, m/T^{2/(k+1)} \} )$，以保证在$(1\pm\epsilon)T_k(H)$ 的概率至少为 $1-\delta$。我们还给出了一个更简单的 $1$-pass 算法，它实现了 $O(\epsilon^{-2} \log\delta^{-1} \log n\cdot (m/T) ( \Delta_E + \Delta_V^{1-1/k} ))$ 空间，其中 $\Delta_E$ （分别为 $\Delta_V$）表示共享超边的 $k$-单纯形的最大数量（分别为顶点）。我们用 $\Omega(\epsilon^{-2})$、$\Omega(m^{1+1/k}/T)$、$\Omega(m/T^{1-1/k})$ 和 $\Omega(m\Delta_V^{1/k}/T)$ 形式的空间下界补充这些算法结果（多通道算法）和 $\Omega(m\Delta_E/T)$ $1$-pass 算法，这表明对我们上限中的参数的一些依赖关系几乎是紧密的。我们的技术扩展并概括了先前为图中的三角形计数开发的几种不同的想法，使用适当的创新来处理更复杂的超图组合。
We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a $k$-uniform hypergraph $H$ with $n$ vertices and $m$ hyperedges. A $k$-simplex in $H$ is a subhypergraph on $k+1$ vertices $X$ such that all $k+1$ possible hyperedges among $X$ exist in $H$. The goal is to process a stream of hyperedges of $H$ and compute a good estimate of $T_k(H)$, the number of $k$-simplices in $H$. We design a suite of algorithms for this problem. Under a promise that $T_k(H) \ge T$, our algorithms use at most four passes and together imply a space bound of $O( \epsilon^{-2} \log\delta^{-1} \text{polylog} n \cdot \min\{ m^{1+1/k}/T, m/T^{2/(k+1)} \} )$ for each fixed $k \ge 3$, in order to guarantee an estimate within $(1\pm\epsilon)T_k(H)$ with probability at least $1-\delta$. We also give a simpler $1$-pass algorithm that achieves $O(\epsilon^{-2} \log\delta^{-1} \log n\cdot (m/T) ( \Delta_E + \Delta_V^{1-1/k} ))$ space, where $\Delta_E$ (respectively, $\Delta_V$) denotes the maximum number of $k$-simplices that share a hyperedge (respectively, a vertex). We complement these algorithmic results with space lower bounds of the form $\Omega(\epsilon^{-2})$, $\Omega(m^{1+1/k}/T)$, $\Omega(m/T^{1-1/k})$ and $\Omega(m\Delta_V^{1/k}/T)$ for multi-pass algorithms and $\Omega(m\Delta_E/T)$ for $1$-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.