Engineering an Efficient Approximate DNF-Counter
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929440455393280 |
|---|---|
| author | Soos, Mate Sarkar, Uddalok Aggarwal, Divesh Chakraborty, Sourav Meel, Kuldeep S. Obremski, Maciej |
| author_facet | Soos, Mate Sarkar, Uddalok Aggarwal, Divesh Chakraborty, Sourav Meel, Kuldeep S. Obremski, Maciej |
| contents | Model counting is a fundamental problem in many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In this work, we focus on a variant of this problem where the underlying formula is expressed in the Disjunctive Normal Form (DNF), also known as #DNF. This problem has been shown to be #P-complete, making it often intractable to solve exactly. Much research has therefore focused on obtaining approximate solutions, particularly in the form of $(\varepsilon, δ)$ approximations.
The primary contribution of this paper is a new approach, called pepin, an approximate #DNF counter that significantly outperforms prior state-of-the-art approaches. Our work is based on the recent breakthrough in the context of the union of sets in the streaming model. We demonstrate the effectiveness of our approach through extensive experiments and show that it provides an affirmative answer to the challenge of efficiently computing #DNF. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19946 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Engineering an Efficient Approximate DNF-Counter Soos, Mate Sarkar, Uddalok Aggarwal, Divesh Chakraborty, Sourav Meel, Kuldeep S. Obremski, Maciej Data Structures and Algorithms Model counting is a fundamental problem in many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In this work, we focus on a variant of this problem where the underlying formula is expressed in the Disjunctive Normal Form (DNF), also known as #DNF. This problem has been shown to be #P-complete, making it often intractable to solve exactly. Much research has therefore focused on obtaining approximate solutions, particularly in the form of $(\varepsilon, δ)$ approximations. The primary contribution of this paper is a new approach, called pepin, an approximate #DNF counter that significantly outperforms prior state-of-the-art approaches. Our work is based on the recent breakthrough in the context of the union of sets in the streaming model. We demonstrate the effectiveness of our approach through extensive experiments and show that it provides an affirmative answer to the challenge of efficiently computing #DNF. |
| title | Engineering an Efficient Approximate DNF-Counter |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.19946 |