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: 5126
Venue: SIGMOD
Year: 2015
Pagerank: 5.7331991e-05
Overall Rank: 6,940 | 52.39%
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,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.1686653e-05
6,995	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.7301567e-05
9,776	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.2209769e-05
11,439	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	5.093636e-05
11,979	Query Processing Techniques for Big Spatial-Keyword Data	2017	SIGMOD	5.093636e-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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
968	Path Oracles for Spatial Networks	2009	VLDB	0.00012901559
1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011566372
1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010421046
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
2,691	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.2499521e-05
3,458	Collective Spatial Keyword Queries: A Distance Owner-Driven Approach	2013	SIGMOD	7.3961486e-05
3,794	Keyword-aware Optimal Route Search	2012	VLDB	7.1200794e-05
4,486	Collective Spatial Keyword Querying	2011	SIGMOD	6.6693992e-05
4,711	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.5506926e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05
8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	5.4142883e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
2	2,691	Keyword Search in Graphs: Finding r-cliques	2011	VLDB
3	9,791	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
4	1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB
5	5,815	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
6	10,460	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
7	5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
8	10,052	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD
9	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
10	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB