Model Counting meets F0 Estimation
Model Counting meets F0 Estimation
复制标题
DOI：
10.1145/3452021.3458311
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
中科院分区：
文献类型：
--
作者：
A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
约束满足问题（CSP）和数据流模型是两个强大的抽象概念，可以捕获计算机科学不同领域中出现的各种问题。两个社区的发展大多是独立发生的，彼此之间很少有互动。在这项工作中，我们试图调查弥合两个社区之间看似沟通的差距是否可以为获得更丰富的基本见解铺平道路。为此，我们关注两个基本问题：CSP 的模型计数和数据流的零频矩 F0 的计算。我们的研究使我们观察到算法框架中采用的核心技术具有惊人的相似性，这些算法框架是分别为模型计数和 F0 计算而发展的。我们设计了一种方法，用于将 F0 估计开发的算法转换为模型计数算法，从而产生新的模型计数算法。然后我们观察到分布式流上下文中的算法可以转换为用于模型计数的分布式算法。接下来，我们将注意力转向从计数的角度观察流媒体，并表明将 F0 估计框架为 #DNF 计数的特殊情况，使我们能够获得丰富的流媒体问题的通用方法，这些问题在之前的工作中已经过具体案例的分析。特别是，我们的观点产生了一种最先进的算法，用于通过更简单的分析进行多维范围有效 F0 估计。
Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments F0 for data streams. Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and F0 computation. We design a recipe for translation of algorithms developed for F0 estimation to that of model counting, resulting in new algorithms for model counting. We then observe that algorithms in the context of distributed streaming can be transformed to distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing F0 estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields a state-of-the art algorithm for multidimensional range efficient F0 estimation with a simpler analysis.