Jan 22th 2010, 1pm DB-talk , ICICS 206

Presenter : Prof. Peter Wood

Title : 
Ranking approximate answers to regular path queries

Abstract :

We consider the problem of a user querying graph-structured
data without knowing its structure.  Regular expressions
provide a certain amount of flexibility in these circumstances,
but it is also helpful if the querying system can perform an
approximate matching of the user's query to the data and can rank
the answers in terms of how closely they match the original query.

The query language we adopt comprises conjunctions of regular
path queries.  We show that our approximate matching framework
allows us to incorporate standard notions of approximation such
as edit distance.  We provide an incremental query evaluation
algorithm which runs in polynomial time and returns answers to
the user in ranked order.

Bio of Prof. Peter Wood :

Peter Wood received his PhD in Computer Science from the University of
Toronto in 1989, having previously obtained BSc and MSc degrees in
Computer Science from the University of Cape Town, South Africa.
He is currently a Senior Lecturer at Birkbeck, University of London, where he is
a member of the Information Management and Web Technologies research group.
His research interests include database, XML and semantic web query languages,
query optimisation, and active and deductive rule languages.