标题： 超图流中的三角形计数：一种完整且实用的方法 显示英文标题

标题： Triangle Counting in Hypergraph Streams: A Complete and Practical Approach

摘要： 在超图流中进行三角形计数，包括超顶点和超边三角形，是超图分析中的一个基本问题，具有广泛的应用。 然而，现有方法面临两个关键限制：(i) 对超顶点三角形结构的分类不完整，通常仅考虑内部或外部三角形；以及 (ii) 采样方案不够灵活，预先定义了采样的超边数量，在严格内存约束下由于超边大小高度可变而不切实际。 为了解决这些挑战，我们首先引入了超顶点三角形的完整分类，包括内部、混合和外部三角形。 基于此，我们开发了 HTCount，这是一种基于水库的算法，能够根据可用内存 M 动态调整样本大小。为了进一步提高内存利用率并减少估计误差，我们开发了 HTCount-P，这是一种基于分区的变体，能够自适应地将未使用的内存划分为独立的样本子集。 我们提供了所提出算法无偏性和方差界限的理论分析。 案例研究展示了我们的三角形结构在揭示有意义的交互模式方面的表达能力。 在现实世界超图上的大量实验表明，我们的算法在严格内存约束下都能实现高精度的三角形计数估计，相对误差比现有方法低 1 到 2 个数量级，并且保持了稳定的高吞吐量。 显示英文摘要

摘要： Triangle counting in hypergraph streams, including both hyper-vertex and hyper-edge triangles, is a fundamental problem in hypergraph analytics, with broad applications. However, existing methods face two key limitations: (i) an incomplete classification of hyper-vertex triangle structures, typically considering only inner or outer triangles; and (ii) inflexible sampling schemes that predefine the number of sampled hyperedges, which is impractical under strict memory constraints due to highly variable hyperedge sizes. To address these challenges, we first introduce a complete classification of hyper-vertex triangles, including inner, hybrid, and outer triangles. Based on this, we develop HTCount, a reservoir-based algorithm that dynamically adjusts the sample size based on the available memory M. To further improve memory utilization and reduce estimation error, we develop HTCount-P, a partition-based variant that adaptively partitions unused memory into independent sample subsets. We provide theoretical analysis of the unbiasedness and variance bounds of the proposed algorithms. Case studies demonstrate the expressiveness of our triangle structures in revealing meaningful interaction patterns. Extensive experiments on real-world hypergraphs show that both our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors that are 1 to 2 orders of magnitude lower than those of existing methods and consistently high throughput.