Name
Abstract | ||
|---|---|---|
Relational, XML and HTML data can be represented as graphs with entities as nodes and relationships as edges. Text is associated with nodes and possibly edges. Keyword search on such graphs has received much attention lately. A central problem in this scenario is to efficiently extract from the data graph a small number of the "best" answer trees. A Backward Expanding search, starting at nodes matching keywords and working up toward confluent roots, is commonly used for predominantly text-driven queries. But it can perform poorly if some keywords match many nodes, or some node has very large degree.In this paper we propose a new search algorithm, Bidirectional Search, which improves on Backward Expanding search by allowing forward search from potential roots towards leaves. To exploit this flexibility, we devise a novel search frontier prioritization technique based on spreading activation. We present a performance study on real data, establishing that Bidirectional Search significantly outperforms Backward Expanding search. |
Year | Venue | Keywords |
|---|---|---|
2005 | VLDB | data graph,bidirectional expansion,new search algorithm,central problem,keyword search,novel search frontier prioritization,backward expanding search,html data,graph databases,answer tree,bidirectional search,spreading activation |
Field | DocType | ISBN |
Data mining,Search algorithm,Phrase search,Exponential search,Computer science,Beam search,Theoretical computer science,Jump search,Bidirectional search,Database,Best-first search,Iterative deepening depth-first search | Conference | 1-59593-154-6 |
Citations | PageRank | References |
271 | 8.72 | 13 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Varun Kacholia | 1 | 360 | 12.20 |
| Shashank Pandit | 2 | 597 | 21.57 |
| S. Chakrabarti | 3 | 4703 | 999.55 |
| S. Sudarshan | 4 | 2690 | 601.76 |
| Rushi Desai | 5 | 273 | 9.13 |
| Hrishikesh Karambelkar | 6 | 273 | 9.13 |