Database Paper Browser

Back to papers

k-Nearest Neighbors in Uncertain Graphs

Summary: Framework for k-NN queries in probabilistic graphs using novel distance functions extending shortest-paths. Sampling-based computation with pruning to locate neighbors; outperforms prior measures on real biological data and scales to tens of millions of edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10145
Venue
VLDB
Year
2010
Pagerank
0.00013584223
Overall Rank
1,159 | 91.95%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,448 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011928845
2,685 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.314724e-05
3,106 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 7.5550946e-05
3,622 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 6.9021704e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.673504e-05
4,158 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 6.3898204e-05
4,165 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 6.3843974e-05
4,959 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 5.7992713e-05
5,355 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 5.5518336e-05
5,909 Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach 2022 SIGMOD 5.2722596e-05
6,083 Querying Uncertain Data with Aggregate Constraints 2011 SIGMOD 5.2173276e-05
6,164 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.1731827e-05
6,165 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 5.1731827e-05
6,373 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.0875991e-05
6,522 Clustering Uncertain Graphs 2018 VLDB 5.0230003e-05
7,540 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 4.7111607e-05
8,626 Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks 2018 SIGMOD 4.4774498e-05
8,762 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 4.4520434e-05
8,909 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 4.4229886e-05
9,135 Sage: A System for Uncertain Network Analysis 2022 VLDB 4.3846727e-05
9,523 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3273374e-05
9,796 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 4.2777144e-05
11,261 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 4.1905499e-05
11,660 Top-k Queries over Digital Traces 2019 SIGMOD 4.1905499e-05
11,777 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1905499e-05
11,912 Indexing Metric Uncertain Data for Range Queries 2015 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
74 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00057797415
300 Trio: A System for Data, Uncertainty, and Lineage 2006 VLDB 0.00028503742
322 MCDB: A Monte Carlo Approach to Managing Uncertain Data 2008 SIGMOD 0.00027523667
974 BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models 2008 VLDB 0.00014882804
1,612 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011142757
1,703 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD 0.00010820803
1,863 Approximation Algorithms for Clustering Uncertain Data 2008 PODS 0.00010287379
2,334 Orion 2.0: Native Support for Uncertain Data 2008 SIGMOD 9.01132e-05
3,190 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.413338e-05
4,328 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 6.2765138e-05
4,439 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.1806955e-05
7,321 Periscope/GQ: A Graph Querying Toolkit 2008 VLDB 4.7577703e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,907 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010130702
4,165 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 6.3843974e-05
5,763 Top-k Nearest Neighbor Search In Uncertain Data Series 2015 VLDB 5.3358283e-05
6,164 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.1731827e-05
6,373 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.0875991e-05
7,080 Nearest Neighbor Searching Under Uncertainty II 2013 PODS 4.8353058e-05
4,721 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 5.9647585e-05
6,865 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.9002126e-05
6,522 Clustering Uncertain Graphs 2018 VLDB 5.0230003e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371