Personal tools
You are here: Home Events Lab Lunch: Yinghui Wu

Lab Lunch: Yinghui Wu

Abstract: Graph pattern matching has become a routine process in emerging applications. In practice the real life graphs are typically large, and are frequently updated with small changes. It is often prohibitively expensive to recompute the matches from scratch via batch algorithms each time the graphs are updated.

What
When Aug 02, 2011
from 01:00 PM to 02:00 PM
Where Informatics Forum MF2
Contact Name
Add event to calendar vCal
iCal

There is going to be a lab lunch on Tuesday next week, at 1pm in the mini-forum 2 on Level 4. Coffee and biscuits are provided as usual.

 

Yinghui Wu is going to be the speaker. Title and abstract are given below.

 

Title:   Incremental graph pattern matching

 

Abstract:  Graph pattern matching has become a routine process in emerging applications.

In practice the real life graphs are typically large, and are frequently updated with small changes.

It is often prohibitively expensive to recompute the matches from scratch via batch algorithms each time the graphs are updated.

 

Given a graph pattern P, a data graph G, a set of matches M and a set of updates to G,

the incremental graph pattern matching problem is to incrementally update Mn according to P and the updates.

In this talk I will introduce techniques for incremental graph pattern matching specifically for the patterns matching defined in terms of (a) graph simulation,

(b) bounded simulation, and (c) subgraph isomorphism. We first briefly go over the concepts of these patterns, as well as their (emerging) application areas.

We  then introduce techniques to handle single/multiple updates for these patterns, with corresponding complexity analysis, algorithms and experimental results.

 

Document Actions