Database Paper Browser

Back to papers

Distance-Constraint Reachability Computation in Uncertain Graphs

Summary: Distance-Constraint Reachability (DCR) in uncertain graphs: probability dist(s,t) ≤ d; #P-Complete, motivating approximation. Two estimators - Horvitz-Thomson unequal sampling and a recursive sampling method blending deterministic recursion with sampling - achieve lower variance and higher efficiency, validated on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10283
Venue
VLDB
Year
2011
Pagerank
0.00011925844
Overall Rank
1,450 | 89.92%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
2,684 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.3136866e-05
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
3,101 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 7.5598015e-05
3,636 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 6.8976555e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.6779082e-05
4,179 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 6.3800553e-05
5,359 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 5.5485493e-05
5,908 Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach 2022 SIGMOD 5.2773278e-05
6,079 Querying Uncertain Data with Aggregate Constraints 2011 SIGMOD 5.2223439e-05
6,171 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.170101e-05
6,172 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 5.170101e-05
6,393 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.0837624e-05
6,545 Clustering Uncertain Graphs 2018 VLDB 5.0193115e-05
7,542 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 4.7156855e-05
8,907 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 4.427232e-05
9,135 Sage: A System for Uncertain Network Analysis 2022 VLDB 4.3888791e-05
9,580 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3234342e-05
9,793 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 4.2818172e-05
11,046 Efficient Stochastic Routing in Path-Centric Uncertain Road Networks 2024 VLDB 4.1945683e-05
11,259 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 4.1945683e-05
11,904 Indexing Metric Uncertain Data for Range Queries 2015 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
733 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017460741
1,162 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.0001358105
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
8,907 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 4.427232e-05
6,171 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.170101e-05
6,393 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.0837624e-05
1,162 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.0001358105
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
6,172 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 5.170101e-05
6,545 Clustering Uncertain Graphs 2018 VLDB 5.0193115e-05
4,179 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 6.3800553e-05