Approximating Queries on Probabilistic Graphs

Amarilli, Antoine; van Bremen, Timothy; Gaspard, Octave; Meel, Kuldeep S.

Type de document :

Pré-publication ou Document de travail

Titre :

Approximating Queries on Probabilistic Graphs

Auteur(s) :

Amarilli, Antoine [Auteur]
Linking Dynamic Data [LINKS]
Data, Intelligence and Graphs [DIG]
van Bremen, Timothy [Auteur]
Nanyang Technological University [Singapour] [NTU]
Gaspard, Octave [Auteur]
École polytechnique [X]
Meel, Kuldeep S. [Auteur]
University of Toronto

Mot(s)-clé(s) en anglais :

Queries on Probabilistic Graphs

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [en]

Query evaluation over probabilistic databases is notoriously intractable -- not only in combined complexity, but often in data complexity as well. This motivates the study of approximation algorithms, and particularly of ...
Lire la suite >Query evaluation over probabilistic databases is notoriously intractable -- not only in combined complexity, but often in data complexity as well. This motivates the study of approximation algorithms, and particularly of combined FPRASes, with runtime polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, i.e., probabilistic graphs, and study when we can devise combined FPRASes for probabilistic query evaluation. We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability results and (conditional) inapproximability results doubled with (unconditional) DNNF provenance circuit size lower bounds. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of Arenas et al. on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs: this was an open problem until now. We also show that one cannot extend a recent result of van Bremen and Meel that gives a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. We last show how our methods can give insights on the evaluation and approximability of regular path queries (RPQs) on probabilistic graphs in the data complexity perspective, showing in particular that some of them are (conditionally) inapproximable.Lire moins >

Langue :

Anglais

Projet ANR :

Réponse efficace aux requêtes sous mises à jour
Requêtes Ontologiques Complexes sur des Fédérations de Données Hétérogènese

Commentaire :

29 pages. Extended version of the ICDT'24 article

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

2309.13287
Accès libre
Accéder au document

Approximating Queries on Probabilistic Graphs BibTeX CSV Excel RIS

Fichiers

Approximating Queries on Probabilistic Graphs

BibTeX

CSV

Excel

RIS