Keyword Search on External Memory Data Graphs

Summary: Introduces a multi-granular representation for keyword search over graphs exceeding memory: an always-resident supernode graph plus cached detailed regions. Two IO-aware search extensions exploit this hierarchy to target promising subgraphs, substantially outperforming virtual memory. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h75d1c94617fb7eb2
Venue: VLDB
Year: 2008
Pagerank: 7.2474338e-05
Overall Rank: 3,509 | 76.41%
DOI: 10.14778/1454159.1454163

Incoming Non-self Citations Over Time

Authors

1. Bhavana Bharat Dalvi (Google; Indian Institute of Technology Mumbai)
2. Meghana Kshirsagar (Indian Institute of Technology Mumbai; Yahoo)
3. S. Sudarshan (Indian Institute of Technology Mumbai)

BibTeX Citation

@article{dalvi_vldb08,
        title = {{Keyword Search on External Memory Data Graphs}},
        author = {Dalvi, Bhavana Bharat and Kshirsagar, Meghana and Sudarshan, S.},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {1},
        pages = {1189--1200},
        doi = {10.14778/1454159.1454163},
        url = {https://doi.org/10.14778/1454159.1454163},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,187	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.00011606901
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010461358
2,679	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.1453935e-05
3,312	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD	7.4385614e-05
10,247	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.0525742e-05
12,752	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00047394041
81	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00036346781
217	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.00024465994
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
290	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021955068
293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021943678
768	Effective Keyword Search in Relational Databases	2006	SIGMOD	0.00014105849
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012956137
2,643	The SphereSearch Engine for Unified Ranked Retrieval of Heterogeneous XML and Web Documents	2005	VLDB	8.177657e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,445	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
2	8,501	Efficient Keyword Search over Virtual XML Views	2007	VLDB
3	7,934	A System for Keyword Proximity Search on XML Databases	2003	VLDB
4	12,725	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
5	9,974	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
6	5,924	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
7	293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB
8	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	1,565	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
10	192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS