Title: Versatile and Efficient Keyword Search on Large-Scale Graph-Structured Data

Speaker: Heasoo Hwang

Abstract:

Link-based search models, such as personalized PageRank and ObjectRank, have been
shown to generate effective top-K lists for keyword search on graph-structured data.
In particular, ObjectRank produces semantically meaningful results with high quality
by exploiting schema information and domain knowledge to model the data of a certain
domain into an annotated graph.

In this talk we focus on two main topics: the need for a scalable search algorithm
and the need for a specificity metric. We observed that it is prohibitively
expensive to execute ObjectRank on a huge graph at query time in order to produce a
top-K list. We also observed that top-K lists sometimes are dominated by nodes with
generic content. To improve the quality of the search results, we want to introduce
a specificity metric and combine it with the relevance scores computed with
ObjectRank.

To address the above two problems, we propose “BinRank” for scalable search and
“Inverse ObjectRank” to compute specificity scores. In addition, we discuss about
the future research directions on search on evolving graphs over time.