Kolloq., Prof. M. Tamer Özsu, University of Waterloo, CA
4:15pm, FMI 00.12.019
Some Results in Graph Data Management
Graphs have always been important data types for database researchers. With the recent growth of social networks, Wikipedia, Linked Data, RDF, and other networks, the interest in managing very large graphs have again gained momentum. I will summarize some of our recent work in this area, focusing on two results: subgraph search over large graphs, and answering SPARQL queries over RDF graphs. The first problem deals with finding subgraphs of a large graph that match a query graph. We assume that there are distance-based constaints on the edges of the query graph. We formulate the problem as distance-based multiway join over the results of edge queries and propose techniques for reducing the cost of distance computation, and the join search space. The second problem focuses on evaluating SPARQL queries with wildcards over an RDF graph that sees frequent updates. Although it has similarities to the subgraph search problem, the same techniques cannot be used. We propose an approach that maps both the RDF data and the SPARQL query into graphs and converts the query evaluation problem to one of subgraph matching. In order to speed up query processing, we propose an indexing mechanism and pruning rules to reduce the search space.
M. Tamer Özsu is Professor of Computer Science at the David R. Cheriton School of Computer Science of the University of Waterloo. He was the Director of the Cheriton School of Computer Science from January 2007 to June 2010. His PhD is from the Ohio State University. He is currently on sabbatical leave at ETH Zürich.
His research is in data management focusing on large-scale data distribution and management of non-traditional data. His publications include the book Principles of Distributed Database Systems (co-authored with Patrick Valduriez), which is now in its third edition. He has also edited, with Ling Liu, the Encyclopedia of Database Systems. He serves as the Series Editor of Synthesis Lectures on Data Management (Morgan & Claypool) and on the editorial boards of three journals, and two book Series. He has served as the Program Chair and General Chair of a number of international conferences.
He is a Fellow of the Association for Computing Machinery (ACM), and of the Institute of Electrical and Electronics Engineers (IEEE), and a member of Sigma Xi. He has held a University Research Chair (2004-2011) and a Faculty Research Fellowship (2000 - 2003) at the University of Waterloo, and a McCalla Research Professorship (1993-1994) at the University of Alberta. He was awarded the ACM SIGMOD Contributions Award in 2006, and The Ohio State University College of Engineering Distinguished Alumnus Award in 2008.
phone: 089/ 289-17256