Answering Top-k Representative Queries on Graph Databases
Summary: Top-k representative queries on graph databases; cast as Set Cover, solved by a greedy algorithm with provable approximation guarantees. NB-Index indexes theta-neighborhoods via Lipschitz embedding and agglomerative clustering, delivering up to two orders of magnitude speedups on real graphs. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sayan Ranu (Indian Institute of Technology Madras)
- 2. Minh Hoang (University of California Santa Barbara)
- 3. Ambuj Singh (University of California Santa Barbara)
BibTeX Citation
@inproceedings{ranu_sigmod14,
title = {{Answering Top-k Representative Queries on Graph Databases}},
author = {Ranu, Sayan and Hoang, Minh and Singh, Ambuj},
series = {{SIGMOD} '14},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2588555.2610524},
url = {https://dl.acm.org/doi/10.1145/2588555.2610524},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,084 | Comprehensive and Efficient Workload Compression | 2021 | VLDB | 6.9151691e-05 |
| 5,869 | ISUM: Efficiently Compressing Large and Complex Workloads for Scalable Index Tuning | 2022 | SIGMOD | 6.0610922e-05 |
| 8,206 | Mining Top-k Pairs of Correlated Subgraphs in a Large Network | 2020 | VLDB | 5.4666548e-05 |
| 10,037 | Graph Exploration: From Users to Large Graphs | 2017 | SIGMOD | 5.1729561e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 591 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.0001603683 |
| 776 | Distance-Join: Pattern Match Query In a Large Graph Database | 2009 | VLDB | 0.00014110016 |
| 1,115 | Comparing Stars: On Approximating Graph Edit Distance | 2009 | VLDB | 0.00012117375 |
| 1,153 | Efficient Diversity-Aware Search | 2011 | SIGMOD | 0.0001193423 |
| 1,454 | Diversifying Top-K Results | 2012 | VLDB | 0.00010739504 |
| 1,807 | DisC Diversity: Result Diversification based on Dissimilarity and Coverage | 2013 | VLDB | 9.7054469e-05 |
| 4,122 | Efficient Diversification of Web Search Results | 2011 | VLDB | 6.8879418e-05 |
| 4,321 | Efficiently Answering Top-k Typicality Queries on Large Databases | 2007 | VLDB | 6.7617825e-05 |
| 12,331 | Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions | 2012 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,703 | Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers | 2014 | VLDB |
| 2 | 6,631 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD |
| 3 | 5,849 | Summarizing Answer Graphs Induced by Keyword Queries | 2013 | VLDB |
| 4 | 93 | Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph | 2019 | VLDB |
| 5 | 12,308 | Optimal Top-k Generation of Attribute Combinations based on Ranked Lists | 2012 | SIGMOD |
| 6 | 12,331 | Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions | 2012 | VLDB |
| 7 | 4,321 | Efficiently Answering Top-k Typicality Queries on Large Databases | 2007 | VLDB |
| 8 | 9,791 | A Graph Method for Keyword-based Selection of the top-K Databases | 2008 | SIGMOD |
| 9 | 8,493 | Top-K Nearest Keyword Search on Large Graphs | 2013 | VLDB |
| 10 | 5,370 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |