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: h75f997bc55838b7d
Venue: SIGMOD
Year: 2015
Pagerank: 5.6000241e-05
Overall Rank: 7,031 | 52.88%
DOI: 10.1145/2723372.2749447

Incoming Non-self Citations Over Time

Authors

1. Minhao Jiang (Hong Kong University of Science and Technology)
2. Ada Wai-Chee Fu (Chinese University of Hong Kong)
3. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{jiang_sigmod15,
        title = {{Exact Top-k Nearest Keyword Search in Large Networks}},
        author = {Jiang, Minhao and Fu, Ada Wai-Chee and Wong, Raymond Chi-Wing},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2749447},
        url = {https://dl.acm.org/doi/10.1145/2723372.2749447},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,142	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	6.2420637e-05
5,699	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0139119e-05
8,364	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3304544e-05
11,802	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.9605343e-05
12,326	Query Processing Techniques for Big Spatial-Keyword Data	2017	SIGMOD	4.9605343e-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
192	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025740385
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022559588
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019655871
449	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018112854
993	Path Oracles for Spatial Networks	2009	VLDB	0.00012620373
1,250	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011325987
1,566	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010183731
1,577	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010155939
1,653	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9588776e-05
1,859	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.4722343e-05
2,736	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.0611294e-05
3,535	Collective Spatial Keyword Queries: A Distance Owner-Driven Approach	2013	SIGMOD	7.203751e-05
3,877	Keyword-aware Optimal Route Search	2012	VLDB	6.9345973e-05
4,592	Collective Spatial Keyword Querying	2011	SIGMOD	6.5016975e-05
4,821	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.3876508e-05
7,344	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5321368e-05
8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	5.2733276e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,653	Efficient kNN Search in Public Transportation Networks	2024	VLDB
2	2,736	Keyword Search in Graphs: Finding r-cliques	2011	VLDB
3	10,011	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
4	1,407	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB
5	5,928	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
6	10,719	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
7	6,073	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
8	10,283	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD
9	1,450	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
10	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB