Event: A New Approach for Fast Indexing and Querying of Graphs
Speaker: Praveen Rao, Assistant Professor of Computer Science and Electrical Engineering, University of Missouri – Kansas City
Date: September 26, 2011
Time: 1:10 p.m.
Location: 3043 ECpE Building Addition
Abstract: Graphs are used to model data in numerous domains such as biology (e.g., protein contact maps, protein interaction networks), chemistry (e.g., chemical compounds), WWW (e.g., social networks, RDF graphs), and computer vision (e.g., image feature graphs). In recent years, there has been a great deal of interest within the database community to develop efficient methods for indexing and query processing graphs. In this talk, I will present a new way of indexing a large database of graphs and processing exact subgraph matching (or subgraph
isomorphism) and approximate graph matching queries. Rather than decomposing a graph into smaller units (e.g., paths, trees, graphs) for indexing purposes, we represent each graph in the database by its graph signature, which is essentially a multiset, and each signature is then indexed. During query processing, a query graph is also mapped into its signature. Consequently, exact subgraph matching and approximate graph matching queries can be processed by performing operations such as intersection and union over the data and query graph signatures. To improve the precision of exact subgraph matching, we have developed a new method based on the concept of line graphs. To speed up query processing, we build a disk-resident index on the graph signatures. Finally, I will present experimental results to show the efficacy our of approach compared with state-of-the-art techniques in graph indexing.
Speaker biography: Praveen Rao is an assistant professor of Computer Science Electrical Engineering at University of Missouri-Kansas City. His research interests are in the areas of data management and health informatics. More specifically, his work focuses on indexing and query processing for data models popular on the Web, namely, XML and RDF. He received the IBM Smarter Planet Faculty Innovation Award in 2010 to develop a new health IT curriculum. His research is funded by National Science Foundation and University of Missouri Research Board. His work is also supported by Intel Single-chip Cloud Computer Research program. Rao received his BE degree in Computer Engineering from University of Pune in 1999, and he received his MS and PhD degrees in Computer Science from University of Arizona in 2001 and 2007, respectively. He also worked as a software engineer at Amazon.com from 2001 to 2002.
If you are interested in meeting Dr. Rao, please contact Srikanta Tirthapura at 294-3546 to schedule a meeting.