Keyword Search on External Memory Data Graphs
Source: VLDB Endowment
Keyword search on graph structured data has attracted a lot of attention in recent years. Graphs are a natural "Lowest common denominator" representation which can combine relational, XML and HTML data. Responses to key-word queries are usually modeled as trees that connect nodes matching the keywords. In this paper the authors address the problem of keyword search on graphs that may be significantly larger than memory. They propose a graph representation technique that combines a condensed version of the graph (the "Supernode graph") which is always memory resident, along with whatever parts of the detailed graph are in a cache, to form a multi-granular graph representation.