Model Counting Meets Distinct Elements in a Data Stream
Model Counting Meets Distinct Elements in a Data Stream
复制标题
DOI：
10.1145/3542700.3542721
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
中科院分区：
文献类型：
--
作者：
A. Pavan;N. V. Vinodchandran;Arnab Bhattacharyya;Kuldeep S. Meel
约束满足问题（csp）和数据流模型是捕获计算机科学不同领域中出现的各种问题的两个强大的抽象。两个社区的发展大多是独立发生的，它们之间很少相互作用。在这项工作中，我们试图调查弥合两个社区之间表面上的沟通差距是否可以为更丰富的基本见解铺平道路。为此，我们关注两个基本问题：csp的模型计数和数据流的零频率矩（F0）计算。
Constraint satisfaction problems (CSPs) 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 CSPs and computation of zeroth frequency moments (F0) for data streams.