Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling
Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling
复制标题
通过边缘采样计算星子图的次线性时间算法
DOI：
10.1007/s00453-017-0287-3
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
Yodpinyanee, Anak
中科院分区：
文献类型：
--
作者：
Aliakbarpour, Maryam;Biswas, Amartya Shankha;Gouleakis, Themis;Peebles, John;Rubinfeld, Ronitt;Yodpinyanee, Anak
本文研究了当有能力以与其大小成比例的概率抽样时，$$S_p \triangleq \sum \left（{\开始{array}{c}x_i\\ p\end{array}}\right）$$形式的和的值的估计问题。这个问题等价于在数据库系统中可以随机抽取行时估计自连接查询的选择性。我们还研究了图的度序列的特殊情况，这对应于当一个图有能力随机抽取边时计算图中p星的数量。我们的算法的a-乘法近似的查询和时间复杂度。这里，是图中的边数，或者等价地，是数据库表中记录数的一半。类似地，nis表示图形中的顶点数和数据库表中唯一值的数目。我们还提供了严格的下限（多对数因子）在几乎所有的情况下，即使是一个度序列，并允许使用图的结构，试图得到一个更好的估计。我们不知道任何先前的下限问题的连接选择性估计。对于图问题，假设仅对顶点均匀采样的能力的先前工作给出了具有匹配下界的算法（Gonen等人，SIAM J Comput 25：1365-1411，2011）。与随机采样边缘的能力，我们可以实现更快的算法近似的数量的星星子图，绕过在此之前的工作的下限。例如，在，和的情况下，我们的上限是，与没有随机边查询时的下限相反。此外，我们考虑了当图是有向图时，长度为2的有向路的数目的计数问题。这个问题等价于估计两个不同表之间的连接查询的选择性。我们证明了这个问题的一般版本不能在次线性时间内解决。然而，当入度和出度之间的比率是有界的，或者等价地，当两列中的值的出现次数之间的比率是有界的，我们通过减少到无向的情况下，给出了一个次线性时间算法。
We study the problem of estimating the value of sums of the form $$S_p \triangleq \sum \left( {\begin{array}{c}x_i\\ p\end{array}}\right) $$ when one has the ability to samplewith probability proportional to its magnitude. When, this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case whenis the degree sequence of a graph, which corresponds to counting the number ofp-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a-multiplicative approximation ofhas query and time complexities. Here,is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly,nis the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even whenis a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample onlyverticesuniformly gave algorithms with matching lower bounds (Gonen et al. in SIAM J Comput 25:1365–1411, 2011). With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where, and, our upper bound is, in contrast to theirlower bound when no random edge queries are available. In addition, we consider the problem of counting the number of directed paths of length two when the graph is directed. This problem is equivalent to estimating the selectivity of a join query between two distinct tables. We prove that the general version of this problem cannot be solved in sublinear time. However, when the ratio between in-degree and out-degree is bounded—or equivalently, when the ratio between the number of occurrences of values in the two columns being joined is bounded—we give a sublinear time algorithm via a reduction to the undirected case.
登录
查看更多内容
DOI：
10.1016/j.tcs.2009.08.006
发表时间：
2009-11
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Tugkan Batu;P. Berenbrink;C. Sohler
通讯作者：
Tugkan Batu;P. Berenbrink;C. Sohler
QPATH：一种在蛋白质 - 蛋白质相互作用网络中查询途径的方法。
影响因子：
3
作者：
Shlomi, T;Segal, D;Ruppin, E;Sharan, R
通讯作者：
Sharan, R
DOI：
10.1109/focs.2015.44
发表时间：
2015-04
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
通讯作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
关于连接结果大小的估计
影响因子：
--
作者：
A. Swami;K. Schiefer
通讯作者：
K. Schiefer
计算数据流中的任意子图
DOI：
--
发表时间：
2012
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
D. Kane;K. Mehlhorn;Thomas Sauerwald;He Sun
通讯作者：
He Sun