File Download
Supplementary

Conference Paper: ProbTree: a query-efficient representation of probabilistic graphs

TitleProbTree: a query-efficient representation of probabilistic graphs
Authors
Issue Date2014
Citation
The 1st International Workshop on Big Uncertain Data (BUDA 2014) in conjunction with SIGMOD/PODS 2014, Snowbird, UT., 22 June 2014. How to Cite?
AbstractInformation in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs, in many cases uncertain. We study the problem of querying a probabilistic graph; in particular, we examine source-to-target' queries, such as computing the shortest path between two vertices. Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of possible worlds'. Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) many samples are needed for reasonable accuracy, and (ii) a possible world can be very large. To tackle these issues, we study the ProbTree, a data structure that stores a succinct representation of the probabilistic graph. Existing ST-query solutions are executed on top of this structure, with the number of samples and possible world sizes reduced.
DescriptionTechnical Paper
Persistent Identifierhttp://hdl.handle.net/10722/203649

 

DC FieldValueLanguage
dc.contributor.authorManiu, Sen_US
dc.contributor.authorCheng, Ren_US
dc.contributor.authorSenellart, Pen_US
dc.date.accessioned2014-09-19T15:49:10Z-
dc.date.available2014-09-19T15:49:10Z-
dc.date.issued2014en_US
dc.identifier.citationThe 1st International Workshop on Big Uncertain Data (BUDA 2014) in conjunction with SIGMOD/PODS 2014, Snowbird, UT., 22 June 2014.en_US
dc.identifier.urihttp://hdl.handle.net/10722/203649-
dc.descriptionTechnical Paper-
dc.description.abstractInformation in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs, in many cases uncertain. We study the problem of querying a probabilistic graph; in particular, we examine source-to-target' queries, such as computing the shortest path between two vertices. Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of possible worlds'. Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) many samples are needed for reasonable accuracy, and (ii) a possible world can be very large. To tackle these issues, we study the ProbTree, a data structure that stores a succinct representation of the probabilistic graph. Existing ST-query solutions are executed on top of this structure, with the number of samples and possible world sizes reduced.-
dc.languageengen_US
dc.relation.ispartof1st International Workshop on Big Uncertain Data, BUDA 2014en_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleProbTree: a query-efficient representation of probabilistic graphsen_US
dc.typeConference_Paperen_US
dc.identifier.emailManiu, S: smaniu@cs.hku.hken_US
dc.identifier.emailCheng, R: ckcheng@cs.hku.hken_US
dc.identifier.authorityCheng, R=rp00074en_US
dc.description.naturepostprint-
dc.identifier.hkuros239389en_US
dc.customcontrol.immutablesml 141014-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats