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: 5065
Venue: SIGMOD
Year: 2015
Pagerank: 4.7764555e-05
Overall Rank: 7,271 | 49.47%
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,933	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2620152e-05
7,827	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.6379617e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-05
11,241	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.1905499e-05
11,782	Query Processing Techniques for Big Spatial-Keyword Data	2017	SIGMOD	4.1905499e-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.00030020929
302	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00028343691
377	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025074538
434	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023277433
946	Path Oracles for Spatial Networks	2009	VLDB	0.00015117675
1,385	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012259478
1,453	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00011921738
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
2,774	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.140768e-05
3,336	Collective Spatial Keyword Queries: A Distance Owner-Driven Approach	2013	SIGMOD	7.2009826e-05
3,591	Keyword-aware Optimal Route Search	2012	VLDB	6.9362465e-05
4,693	Collective Spatial Keyword Querying	2011	SIGMOD	5.9867895e-05
4,880	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.8526687e-05
7,313	Nearest Keyword Search in XML Documents	2011	SIGMOD	4.7599924e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,068	Efficient kNN Search in Public Transportation Networks	2024	VLDB	4.1905499e-05
2,774	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.140768e-05
9,589	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD	4.3167828e-05
1,626	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.0001108491
5,945	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2583364e-05
10,171	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD	4.1905499e-05
6,497	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0324877e-05
9,897	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	4.2559233e-05
1,072	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014256848
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05