Colloquium Details
Answering Reachability Query in Large Directed Graphs
| Author: | Ruoming Jin Kent State University |
|---|---|
| Date: | November 18, 2010 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Dejing Dou |
Abstract
Efficiently answering reachability query is a fundamental problem in graph database and has attracted much attention recently. In this talk, I will discuss two of our recent works (SIGMOD'09, SIGMOD'10) on addressing this problem. The first work is a new 3-hop reachability indexing scheme for directed graphs with higher density. The existing work either uses spanning structures, such as chains or trees, to compress the complete transitive closure, or utilizes the 2-hop strategy to describe the reachability. Almost all of these approaches work well for very sparse graphs. However, the challenging problem is that as the ratio of the number of edges to the number of vertices increases, the size of the compressed transitive closure grows very large. To solve this problem,we propose 3-hop indexing inspired by the highway system of the transportation network to construct high-compression indices on denser graphs. Empirical studies show that our 3-hop scheme has much smaller index size than state-of-the-art reachability query schemes such as 2-hop and path-tree when DAGs are not very sparse, while our query time is close to path-tree, which is considered to be one of the best reachability query schemes.
In the second work, we study the generalized reachability query on the edge labeled graph, which are very common in the real world graphs, such as social networks, biological networks, and the semantic web, etc. Here, each edge has a label that denotes the relationship between the two vertices connected by the edge. A fundamental research problem on these labeled graphs is how to handle the label-constraint reachability query: Can vertex u reach vertex v through a path whose edge labels are constrained by a set of labels? In this work, we introduce a novel tree-based index framework which utilizes the directed maximal weighted spanning tree algorithm and sampling techniques to maximally compress the generalized transitive closure for the labeled graphs.
Biography
Ruoming Jin is an Assistant Professor in the Department of Computer Science at Kent State University. He received the PhD degree in computer science from the Ohio State University in 2005. His research interests include data mining (especially graph mining), complex network analysis, graph databases, data stream processing, and high performance computing. He has published over 70 technical papers and many appear in the top data mining and database conferences and journals, including SIGKDD, ICDM, SDM, SIGMOD, VLDB, ICDE, etc. Two of his papers received best paper nominations at the IEEE ICDM conference, and were invited for journal submissions. He has served as senior PCs and PCs for various international data mining conferences and has co-chairs the four international workshops on mining multiple information sources. He is also a recipient of NSF CAREER award.