Estimating the Size of Union of Sets in Streaming Models
Estimating the Size of Union of Sets in Streaming Models
复制标题
DOI：
10.1145/3452021.3458333
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Kuldeep S. Meel;N. V. Vinodchandran;Sourav Chakraborty
中科院分区：
文献类型：
--
作者：
Kuldeep S. Meel;N. V. Vinodchandran;Sourav Chakraborty
在本文中，我们研究的问题，估计的大小的联合集$S_1，\dots，S_M$，其中每个集$S_i \subseteq mega $（对于一些离散的宇宙$mega $）是隐含的，并在流的方式。我们定义的概念，德尔菲集捕捉类的流问题的成员，采样和计数调用集是有效的。特别是，我们展示了我们的概念的德尔菲集捕获三个众所周知的问题：克利的措施问题（离散版本），测试覆盖率估计，和模型计数的DNF公式。Klee测度问题对应于多维轴对齐矩形的体积计算，即，每个d维轴对齐的矩形可以被定义为$[a_1，b_1] \times [a_2，b_2] \times [a_d，B_d]$。测试覆盖率估计问题主要研究组合测试中给定测试数组的覆盖率计算问题，是软硬件测试中的一项基本技术。最后，给定一个DNF公式$\varphi = T_1 \vee T_2 \vee_dots\vee T_M$，模型计数问题试图计算满足$\varphi$的分配的数量。我们的工作的主要贡献是一个简单而有效的基于采样的算法，称为\混合，估计的并集流设置。该算法的空间复杂度为O（R）log|梅加|）$和更新时间为$O（R \cdot R \cdot R\（M/δ）\cdot R\（M/δ））|梅加|）$其中，$R = Oleft（Oleog（M/δ）\cdot \varepsilon^2 \right）。$因此，我们的算法提供了第一个算法与线性依赖于d的Klee的测量问题，在流设置为$d>1$，从而解决了开放的问题Tirthpura和Woodruff（PODS-12）。此外，一个简单的应用程序，我们的算法借给一个有效的算法，在流媒体设置的覆盖估计问题。然后，我们调查是否覆盖估计的空间复杂度可以进一步提高，在这种情况下，我们提出了另一种流算法，使用接近最佳的$O（txlogn/\varepsilon^2）$空间复杂度，但使用的更新算法是在$\rmP ^\rmNP $，从而展示了一个有趣的时间与空间的权衡流设置。最后，我们证明了我们的德尔菲集的一般性，通过获得一个流式算法的DNF公式的模型计数。值得一提的是，我们认为我们的工作的一个关键优势是算法及其理论分析的简单性，这使得它适合实际实施和易于采用。
In this paper we study the problem of estimating the size of the union of sets $S_1, \dots, S_M$ where each set $S_i \subseteq Ømega$ (for some discrete universe $Ømega$) is implicitly presented and comes in a streaming fashion. We define the notion of Delphic sets to capture class of streaming problems where membership, sampling, and counting calls to the sets are efficient. In particular, we show our notion of Delphic sets capture three well known problems: Klee's measure problem (discrete version), test coverage estimation, and model counting of DNF formulas. The Klee's measure problem corresponds to computation of volume of multi-dimension axis aligned rectangles, i.e., every d-dimension axis-aligned rectangle can be defined as $[a_1,b_1] \times [a_2,b_2] \times łdots \times [a_d, b_d]$. The problem of test coverage estimation focuses on the computation of coverage measure for a given testing array in the context of combinatorial testing, which is a fundamental technique in the context of hardware and software testing. Finally, given a DNF formula $\varphi = T_1 \vee T_2 \vee łdots \vee T_M$, the problem of model counting seeks to compute the number of satisfying assignments of $\varphi$. The primary contribution of our work is a simple and efficient sampling-based algorithm, called \hybrid, for estimating the of union of sets in streaming setting. Our algorithm has the space complexity of $O(Rłog |Ømega|)$ and update time is $O(Rłog R \cdot łog(M/δ) \cdot łog|Ømega|)$ where, $R = Ołeft(łog (M/δ)\cdot \varepsilon^2 \right).$ Consequently, our algorithm provides the first algorithm with linear dependence on d for Klee's measure problem in streaming setting for $d>1$, thereby settling the open problem of Tirthpura and Woodruff (PODS-12). Furthermore, a straightforward application of our algorithm lends to an efficient algorithm for coverage estimation problem in streaming setting. We then investigate whether the space complexity for coverage estimation can be further improved, and in this context, we present another streaming algorithm that uses near-optimal $O(tłog n/\varepsilon^2)$ space complexity but uses an update algorithm that is in $\rm P ^\rm NP $, thereby showcasing an interesting time vs space trade-off in the streaming setting. Finally, we demonstrate the generality of our Delphic sets by obtaining a streaming algorithm for model counting of DNF formulas. It is worth remarking that we view a key strength of our work is the simplicity of both the algorithm and its theoretical analysis, which makes it amenable to practical implementation and easy adoption.