A variety of types of data, such as relational, XML and HTML data
can be naturally represented using a graph model of data,
with entities as nodes and relationships as edges.
Graph representations are also a natural choice for representing
information extracted from unstructured data, and for
representing information integrated from heterogeneous sources of data.

Keyword search is a natural way to retrieve information from graph
representations of data, especially in the common situation where
the graphs do not have a well-defined schema.
Unlike text or Web search, there is no natural notion of a document,
and information about a single conceptual entity may be split across
multiple nodes.   Answers to queries are therefore usually modeled
as trees that connect nodes matching the keywords, with each answer
tree having an associated score.  The goal of keyword search then is
to find answers with the highest scores.  A number of systems, including
the BANKS system developed at IIT Bombay, are based on such a model
for answering keyword queries.

In this talk we first outline background material on keyword
querying on graph data, including models for ranking of answer trees.
We then focus on search algorithms for finding top-ranked answers.
We outline key issues in finding top-ranked answers, and present
algorithms that address the problem in the context of in-memory graphs.
We then consider the problem of search on external memory graphs,
and briefly outline our on-going work on external memory
graph search based on a multi-granular graph representation.