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
10284
Venue
VLDB
Year
2011
Pagerank
0.00011645677
Overall Rank
1,234 | 91.43%
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,331 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.819467e-05
2,547 K-Reach: Who is in Your Small World 2012 VLDB 8.5018215e-05
2,924 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 8.0259394e-05
3,246 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.6740413e-05
3,499 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 7.4344243e-05
3,512 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.4217824e-05
3,675 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.2707439e-05
5,112 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.4242898e-05
5,497 Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach 2022 SIGMOD 6.2648243e-05
5,758 Querying Uncertain Data with Aggregate Constraints 2011 SIGMOD 6.1615566e-05
5,801 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 6.1430353e-05
5,802 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.1430353e-05
5,951 On Uncertain Graphs Modeling and Queries 2015 VLDB 6.0919742e-05
6,266 Clustering Uncertain Graphs 2018 VLDB 5.9974199e-05
7,451 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 5.6770416e-05
8,934 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.4076395e-05
9,140 Sage: A System for Uncertain Network Analysis 2022 VLDB 5.3752938e-05
9,523 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.3218384e-05
9,786 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.2719963e-05
11,049 Efficient Stochastic Routing in Path-Centric Uncertain Road Networks 2024 VLDB 5.1725247e-05
11,261 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 5.1725247e-05
11,912 Indexing Metric Uncertain Data for Range Queries 2015 SIGMOD 5.1725247e-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
270 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022892419
671 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.0001525358
1,032 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012602512
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
736 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.0001459447
3,246 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.6740413e-05
8,934 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.4076395e-05
5,801 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 6.1430353e-05
5,951 On Uncertain Graphs Modeling and Queries 2015 VLDB 6.0919742e-05
1,032 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012602512
2,449 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 8.6321542e-05
5,802 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.1430353e-05
6,266 Clustering Uncertain Graphs 2018 VLDB 5.9974199e-05
3,675 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.2707439e-05