Model Counting Meets Distinct Elements in a Data Stream

被引:0
作者
Pavan, A. [1 ]
Vinodchandran, N. V. [2 ]
Bhattacharyya, Arnab [3 ]
Meel, Kuldeep S. [3 ]
机构
[1] Iowa State Univ, Ames, IA 50011 USA
[2] Univ Nebraska, Lincoln, NE USA
[3] Natl Univ Singapore, Singapore, Singapore
关键词
ALGORITHMS; ENUMERATION; COMPLEXITY;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 (F-0) 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 F-0 computation. We design a recipe for translation of algorithms developed for F-0 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 F-0 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.
引用
收藏
页码:87 / 94
页数:8
相关论文
共 50 条
  • [21] On the Impact of Junction-Tree Topology on Weighted Model Counting
    Kenig, Batya
    Gal, Avigdor
    SCALABLE UNCERTAINTY MANAGEMENT (SUM 2015), 2015, 9310 : 83 - 98
  • [22] Counting Arbitrary Subgraphs in Data Streams
    Kane, Daniel M.
    Mehlhorn, Kurt
    Sauerwald, Thomas
    Sun, He
    AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II, 2012, 7392 : 598 - 609
  • [23] Approximately Counting Subgraphs in Data Streams
    Fichtenberger, Hendrik
    Peng, Pan
    PROCEEDINGS OF THE 41ST ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS (PODS '22), 2022, : 413 - 425
  • [24] Perfect Lp Sampling in a Data Stream
    Jayaram, Rajesh
    Woodruff, David P.
    2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 544 - 555
  • [25] Incremental Learning from Stream Data
    He, Haibo
    Chen, Sheng
    Li, Kang
    Xu, Xin
    IEEE TRANSACTIONS ON NEURAL NETWORKS, 2011, 22 (12): : 1901 - 1914
  • [26] A survey on data stream clustering and classification
    Hai-Long Nguyen
    Woon, Yew-Kwong
    Ng, Wee-Keong
    KNOWLEDGE AND INFORMATION SYSTEMS, 2015, 45 (03) : 535 - 569
  • [27] PERFECT Lp SAMPLING IN A DATA STREAM
    Jayaram, Rajesh
    Woodruff, David
    SIAM JOURNAL ON COMPUTING, 2021, 50 (02) : 382 - 439
  • [28] Simulating Quantum Circuits by Model Counting
    Mei, Jingyi
    Bonsangue, Marcello
    Laarman, Alfons
    COMPUTER AIDED VERIFICATION, PT III, CAV 2024, 2024, 14683 : 555 - 578
  • [29] From Weighted to Unweighted Model Counting
    Chakraborty, Supratik
    Fried, Dror
    Meel, Kuldeep S.
    Vardi, Moshe Y.
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 689 - 695
  • [30] Data structures for categorical path counting queries
    He, Meng
    Kazi, Serikzhan
    THEORETICAL COMPUTER SCIENCE, 2022, 938 : 97 - 111