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: 9937
Venue: VLDB
Year: 2008
Pagerank: 7.4038805e-05
Overall Rank: 3,450 | 76.34%
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,163	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.00011865557
1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010370683
2,631	FastQRE: Fast Query Reverse Engineering	2018	SIGMOD	8.3231158e-05
3,239	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD	7.6078324e-05
10,052	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.1685424e-05
12,461	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	5.093636e-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
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.000247733
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
285	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00022365284
302	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021963347
748	Effective Keyword Search in Relational Databases	2006	SIGMOD	0.00014381224
930	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001312728
2,609	The SphereSearch Engine for Unified Ranked Retrieval of Heterogeneous XML and Web Documents	2005	VLDB	8.3476234e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
2	8,333	Efficient Keyword Search over Virtual XML Views	2007	VLDB
3	7,773	A System for Keyword Proximity Search on XML Databases	2003	VLDB
4	12,434	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
5	9,791	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
6	5,849	Summarizing Answer Graphs Induced by Keyword Queries	2013	VLDB
7	302	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB
8	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
10	187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS