DBScholar

Back to papers

k-Nearest Neighbors in Uncertain Graphs

Summary: Framework for k-NN search over probabilistic graphs, introducing uncertainty-aware extensions of shortest-path distance. Sampling-based computation and novel pruning scale to tens of millions of edges, improving true-neighbor identification on biological networks. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hf083642b4ecc5186
Venue
VLDB
Year
2010
Pagerank
0.00012164865
Overall Rank
1,069 | 92.84%
DOI
10.14778/1920841.1920967

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{potamias_vldb10,
        title = {{k-Nearest Neighbors in Uncertain Graphs}},
        author = {Potamias, Michalis and Bonchi, Francesco and Gionis, Aristides and Kollios, George},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {997--1008},
        doi = {10.14778/1920841.1920967},
        url = {https://doi.org/10.14778/1920841.1920967},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
1,266 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.00011256294
2,072 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 9.0668141e-05
3,046 Injecting Uncertainty in Graphs for Identity Obfuscation 2012 VLDB 7.7023081e-05
3,612 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 7.1436297e-05
3,644 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.1224321e-05
3,804 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 6.9907371e-05
3,826 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 6.9787375e-05
4,753 Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach 2022 SIGMOD 6.4218566e-05
4,997 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 6.3093118e-05
5,322 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.1663105e-05
5,768 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 5.9831541e-05
5,966 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.9142578e-05
5,997 Querying Uncertain Data with Aggregate Constraints 2011 SIGMOD 5.9036298e-05
6,180 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.8425819e-05
6,489 Clustering Uncertain Graphs 2018 VLDB 5.7517943e-05
7,613 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 5.4675059e-05
8,986 Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks 2018 SIGMOD 5.2311279e-05
9,126 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 5.208561e-05
9,275 Shortest Paths Discovery in Uncertain Networks via Transfer Learning 2023 SIGMOD 5.1860131e-05
9,491 Sage: A System for Uncertain Network Analysis 2022 VLDB 5.1549931e-05
9,884 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1037285e-05
10,173 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.0559291e-05
11,820 Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem 2023 VLDB 4.9605343e-05
12,199 Top-k Queries over Digital Traces 2019 SIGMOD 4.9605343e-05
12,321 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.9605343e-05
12,445 Indexing Metric Uncertain Data for Range Queries 2015 SIGMOD 4.9605343e-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
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042804864
245 MCDB: A Monte Carlo Approach to Managing Uncertain Data 2008 SIGMOD 0.00023188414
340 Trio: A System for Data, Uncertainty, and Lineage 2006 VLDB 0.00020548826
845 BayesStore: Managing Large, Uncertain Data Repositories with Probabilistic Graphical Models 2008 VLDB 0.00013493631
1,367 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00010878876
1,403 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD 0.00010753743
2,096 Orion 2.0: Native Support for Uncertain Data 2008 SIGMOD 9.0406786e-05
2,319 Approximation Algorithms for Clustering Uncertain Data 2008 PODS 8.6376033e-05
3,116 Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers 2009 SIGMOD 7.6157273e-05
3,337 Sliding-Window Top-k Queries on Uncertain Streams 2008 VLDB 7.3950425e-05
4,232 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.7043637e-05
7,991 Periscope/GQ: A Graph Querying Toolkit 2008 VLDB 5.3949937e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,602 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD
2 3,826 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD
3 5,264 Top-k Nearest Neighbor Search In Uncertain Data Series 2015 VLDB
4 5,966 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB
5 6,180 On Uncertain Graphs Modeling and Queries 2015 VLDB
6 7,186 Nearest Neighbor Searching Under Uncertainty II 2013 PODS
7 4,828 Nearest-Neighbor Searching Under Uncertainty 2012 PODS
8 6,123 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
9 6,489 Clustering Uncertain Graphs 2018 VLDB
10 1,641 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB