A Hybrid Sampling Scheme for Triangle Counting
A Hybrid Sampling Scheme for Triangle Counting
复制标题
三角形计数的混合采样方案
DOI：
10.1137/1.9781611974782.116
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Eric Price
中科院分区：
文献类型：
--
作者：
John Kallaugher;Eric Price
我们研究估计图流中三角形数量的问题。没有流算法可以在所有图上获得sublinear空间，因此该区域中的方法以输入图的参数（例如三角形的最大数量共享单个边缘）绑定了空间。我们给出了一种采样算法，该算法还通过共享一个顶点的最大三角形数量来参数化。我们的界限匹配所有图表中最著名的旋转门结果，并在诸如G（n，p）或一组独立三角形之类的简单图表上获得更好的性能。我们将上限与下限进行补充，表明没有采样算法可以在这些图表上做得更好，而不是对数因子。特别是，当所有三角形共享一个共同的顶点时，任何插入流算法都必须使用[方程]空间，并且当所有三角形都独立时，任何采样算法都必须采用T1/3样本。我们添加了另一个下限，还匹配算法的性能，该性能适用于所有图形类。该下限涵盖了“三角依赖性”采样算法，一个子类，包括我们的算法和所有先前的采样算法。
We study the problem of estimating the number of triangles in a graph stream. No streaming algorithm can get sublinear space on all graphs, so methods in this area bound the space in terms of parameters of the input graph such as the maximum number of triangles sharing a single edge. We give a sampling algorithm that is additionally parameterized by the maximum number of triangles sharing a single vertex. Our bound matches the best known turnstile results in all graphs, and gets better performance on simple graphs like G(n, p) or a set of independent triangles. We complement the upper bound with a lower bound showing that no sampling algorithm can do better on those graphs by more than a log factor. In particular, any insertion stream algorithm must use [EQUATION] space when all the triangles share a common vertex, and any sampling algorithm must take T1/3 samples when all the triangles are independent. We add another lower bound, also matching our algorithm's performance, which applies to all graph classes. This lower bound covers "triangle-dependent" sampling algorithms, a subclass that includes our algorithm and all previous sampling algorithms for the problem.