GExp: Cost-aware Graph Exploration with Keywords

Summary: GExp enables graph exploration via interleaved keyword queries and bounded-cost evaluation. Cost-aware incremental evaluation via substructure expansions enables tunable quality-cost tradeoffs with provable bounds across three keyword-query classes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf8558931f55979c0
Venue: SIGMOD
Year: 2018
Pagerank: 4.9793485e-05
Overall Rank: 12,217 | 17.86%
DOI: 10.1145/3183713.3193550

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mohammad Hossein Namaki (Washington State University)
2. Yinghui Wu (Washington State University)
3. Xin Zhang (Washington State University)

BibTeX Citation

@inproceedings{namaki_sigmod18,
        title = {{GExp: Cost-aware Graph Exploration with Keywords}},
        author = {Namaki, Mohammad Hossein and Wu, Yinghui and Zhang, Xin},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3193550},
        url = {https://dl.acm.org/doi/10.1145/3183713.3193550},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,154	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.9793485e-05
12,165	NAVIGATE: Explainable Visual Graph Exploration by Examples	2019	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021943678
1,317	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011050011
2,731	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.0838142e-05
4,307	Exploratory Keyword Search with Interactive Input	2015	SIGMOD	6.6747876e-05
4,365	Measure-driven Keyword-Query Expansion	2009	VLDB	6.6337428e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB
2	5,924	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
3	12,368	Graph-based Exploration of Non-graph Datasets	2016	VLDB
4	4,466	Schemaless and Structureless Graph Querying	2014	VLDB
5	9,974	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
6	8,391	Query Expansion Based on Clustered Results	2011	VLDB
7	12,165	NAVIGATE: Explainable Visual Graph Exploration by Examples	2019	SIGMOD
8	6,431	X2Q: Your Personal Example-based Graph Explorer	2018	VLDB
9	10,232	Graph Exploration: From Users to Large Graphs	2017	SIGMOD
10	12,725	Exploratory Keyword Search on Data Graphs	2010	SIGMOD