An Indexing Framework for Queries on Probabilistic Graphs

Abstract : Information in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs. In many cases, such information is uncertain. We study the problem of querying a probabilistic graph, in which vertices are connected to each other probabilistically. In particular, we examine “source-to-target” queries (or ST-queries), such as computing the shortest path between two vertices. The major difference with the deterministic setting is that query answers are enriched with probabilistic annotations. Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of “possible worlds” – database instances generated from the probabilistic graph. Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) a possible world can be very large and (ii) many samples are needed for reasonable accuracy. To tackle these issues, we study the ProbTree, a data structure that stores a succinct, or indexed, version of the possible worlds of the graph. Existing ST-query solutions are executed on top of this structure, with the number of samples and sizes of the possible worlds reduced. We examine lossless and lossy methods for generating the ProbTree, which reflect the trade-off between the accuracy and efficiency of query evaluation. We analyze the correctness and complexity of these approaches. Our extensive experiments on real datasets show that the ProbTree is fast to generate and small in size. It also enhances the accuracy and efficiency of existing ST-query algorithms significantly.
Type de document :
Article dans une revue
ACM Trans. Datab. Syst, 2017
Liste complète des métadonnées

Littérature citée [47 références]  Voir  Masquer  Télécharger
Contributeur : Pierre Senellart <>
Soumis le : mardi 17 janvier 2017 - 13:29:05
Dernière modification le : mardi 19 juin 2018 - 10:44:02


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01437580, version 1


Silviu Maniu, Reynold Cheng, Pierre Senellart. An Indexing Framework for Queries on Probabilistic Graphs. ACM Trans. Datab. Syst, 2017. 〈hal-01437580〉



Consultations de la notice


Téléchargements de fichiers