Exact Top-k Nearest Keyword Search in Large Networks

Summary: Exact top-k nearest keyword search in large networks; introduces algorithms that yield exact results rather than approximations for keyword-containing vertex queries. Scalable to very large graphs, with experiments on real datasets comparing against best-known approximations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5064
Venue: SIGMOD
Year: 2015
Pagerank: 4.7794907e-05
Overall Rank: 7,277 | 49.38%
DOI: 10.1145/2723372.2749447

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,932	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2670741e-05
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-05
11,239	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.1945683e-05
11,774	Query Processing Techniques for Big Spatial-Keyword Data	2017	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
301	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028370644
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
945	Path Oracles for Spatial Networks	2009	VLDB	0.00015137526
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
1,453	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00011917976
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
2,770	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.1437191e-05
3,588	Keyword-aware Optimal Route Search	2012	VLDB	6.9428691e-05
3,748	Collective Spatial Keyword Queries: A Distance Owner-Driven Approach	2013	SIGMOD	6.7912604e-05
4,786	Collective Spatial Keyword Querying	2011	SIGMOD	5.9235651e-05
4,960	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.7987607e-05
7,315	Nearest Keyword Search in XML Documents	2011	SIGMOD	4.7645064e-05
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,453	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00011917976
2,770	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.1437191e-05
9,589	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD	4.3209273e-05
1,641	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00011047924
5,946	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2616887e-05
10,171	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD	4.1945683e-05
6,503	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0357715e-05
9,898	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	4.2600049e-05
1,073	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014264992
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05