Bidirectional Expansion For Keyword Search on Graph Databases

Summary: Introduces bidirectional keyword search over graph databases, combining backward expansion from keyword matches with forward exploration from candidate roots. A spreading-activation frontier prioritization mitigates high-match and high-degree bottlenecks, substantially outperforming backward-only search. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h472980e4a360798e
Venue: VLDB
Year: 2005
Pagerank: 0.00021943678
Overall Rank: 293 | 98.04%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Varun Kacholia (Indian Institute of Technology Mumbai; University of California Berkeley)
2. Shashank Pandit (Carnegie Mellon University; Indian Institute of Technology Mumbai)
3. Soumen Chakrabarti (Indian Institute of Technology Mumbai)
4. Rushi Desai (Indian Institute of Technology Mumbai; Microsoft)
5. Hrishikesh Karambelkar (Indian Institute of Technology Mumbai; Oracle)

BibTeX Citation

@article{kacholia_vldb05,
        title = {{Bidirectional Expansion For Keyword Search on Graph Databases}},
        author = {Kacholia, Varun and Pandit, Shashank and Chakrabarti, Soumen and Desai, Rushi and Karambelkar, Hrishikesh},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {505},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 51 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,870	Relaxation in Text Search using Taxonomies	2008	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
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
290	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021955068
482	Query Optimization for XML	1999	VLDB	0.00017598607
505	Schema-Free XQuery	2004	VLDB	0.00017161757

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS
2	8,391	Query Expansion Based on Clustered Results	2011	VLDB
3	217	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB
4	768	Effective Keyword Search in Relational Databases	2006	SIGMOD
5	7,934	A System for Keyword Proximity Search on XML Databases	2003	VLDB
6	9,098	Toward Scalable Keyword Search over Relational Data	2010	VLDB
7	9,974	A Graph Method for Keyword-based Selection of the top-K Databases	2008	SIGMOD
8	1,565	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
9	12,725	Exploratory Keyword Search on Data Graphs	2010	SIGMOD
10	3,509	Keyword Search on External Memory Data Graphs	2008	VLDB