Keyword Search in Graphs: Finding r-cliques

Summary: Defines r-cliques for keyword search: nodes covering all keywords with distance ≤ r, yielding tighter results than trees. Offers exact r-clique enumeration and a polynomial-delay 2-approximation; experiments on two real datasets show efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha8a19b53f9158995
Venue: VLDB
Year: 2011
Pagerank: 8.0611294e-05
Overall Rank: 2,736 | 81.67%
DOI: 10.14778/2021017.2021025

Incoming Non-self Citations Over Time

Authors

1. Mehdi Kargar (York University)
2. Aijun An (York University)

BibTeX Citation

@article{kargar_vldb11,
        title = {{Keyword Search in Graphs: Finding r-cliques}},
        author = {Kargar, Mehdi and An, Aijun},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {10},
        pages = {681--692},
        doi = {10.14778/2021017.2021025},
        url = {https://doi.org/10.14778/2021017.2021025},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
696	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014671367
1,478	Diversifying Top-K Results	2012	VLDB	0.00010511781
1,577	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010155939
2,251	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7460227e-05
6,595	MeanKS: Meaningful Keyword Search in Relational Databases with Complex Schema	2014	SIGMOD	5.7221191e-05
7,031	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6000241e-05
8,204	Full-Power Graph Querying: State of the Art and Challenges	2023	VLDB	5.3617539e-05
8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	5.2733276e-05
12,266	GExp: Cost-aware Graph Exploration with Keywords	2018	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022559588
294	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021884041
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011777466
1,566	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010183731

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	195	Algorithmics and Applications of Tree and Graph Searching	2002	PODS
2	4,825	Efficient Algorithms for Answering the m-Closest Keywords Query	2015	SIGMOD
3	12,627	Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data	2013	VLDB
4	696	Effective Community Search for Large Attributed Graphs	2016	VLDB
5	3,512	Keyword Search on External Memory Data Graphs	2008	VLDB
6	7,031	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
7	1,566	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
8	1,450	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
9	5,937	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
10	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB