Talks & Seminars
Keyword Search on Graph-Structured Data
Prof. S. Sudarshan, Dept. of Computer Science & Engg., IIT Bombay
Date & Time: January 23, 2008 15:00
Venue: F. C. Kohli Auditorium, ‘B’ Block, 01st floor, Kanwal Rekhi Building
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.

Work done jointly with Soumen Chakrabarti, numerous BTech/MTech students, and 1 research scholar.

Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback