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: 10486
Venue: VLDB
Year: 2011
Pagerank: 8.2499521e-05
Overall Rank: 2,691 | 81.54%
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
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
1,454	Diversifying Top-K Results	2012	VLDB	0.00010739504
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
6,567	MeanKS: Meaningful Keyword Search in Relational Databases with Complex Schema	2014	SIGMOD	5.8380657e-05
6,940	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.7331991e-05
8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	5.4142883e-05
8,920	Full-Power Graph Querying: State of the Art and Challenges	2023	VLDB	5.3483178e-05
11,918	GExp: Cost-aware Graph Exploration with Keywords	2018	SIGMOD	5.093636e-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.00022695855
302	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021963347
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD	0.00010421046

Semantically Similar Papers

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