Name
Abstract | ||
|---|---|---|
A fundamental research problem concerning edge-labeled uncertain graphs is called label and distance-constraint reachability query (LDCR): Given two vertices u and v, query the probability that u can reach v through paths whose labels and lengths are constrained by a label set and a distance threshold separately. Considering LDCR is not tractable as a #P-complete problem, we aim to propose effective and efficient approximate solutions for it. We first introduce a subpath-based filtering strategy which combines divide-conquer algorithm and branch path pruning to compress the original graph and reduce the scale of DC-tree. Then to approximate LDCR, several estimators are presented based on different sampling mechanisms and a path/cut bound is proposed to prune large-deviation values. An extensive experimental evaluation on both real and synthetic datasets demonstrates that our approaches exhibit prominent performance in term of query time and accuracy. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-05810-8_13 | DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, DASFAA 2014, PT I |
Field | DocType | Volume |
Graph,Vertex (geometry),Computer science,Filter (signal processing),Reachability,Theoretical computer science,Sampling (statistics),Approximate solution,Estimator | Conference | 8421 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.43 |
References | Authors | |
14 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minghan Chen | 1 | 5 | 0.43 |
| Yu Gu | 2 | 201 | 34.98 |
| Yubin Bao | 3 | 80 | 16.78 |
| Ge Yu | 4 | 27 | 2.54 |