TEDI: Efficient Shortest Path Query Answering on Graphs

TEDI: Efficient Shortest Path Query Answering on Graphs

时间：2011年12月27日 地点：九龙湖校区计算机楼413会议室

报告简介：

Efficient shortest path query answering in large graphs is enjoying a growing number of applications, such as ranked keyword search in databases, social networks, ontology reasoning and bioinformatics. A shortest path query on a graph finds the shortest path for the given source and target vertices in the graph. Current techniques for efficient evaluation of such queries are based on the pre-computation of compressed Breadth First Search trees of the graph. However, they suffer from drawbacks of scalability. To address these problems, we propose TEDI, an indexing and query processing scheme for the shortest path query answering. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node (a.k.a. bag) contains more than one vertex from the graph. The shortest paths are stored in such bags and these local paths together with the tree are the components of the index of the graph. Based on this index, a bottom-up operation can be executed to find the shortest path for any given source and target vertices. Our experimental results show that TEDI offers orders-of-magnitude performance improvement over existing approaches on the index construction time, the index size and the query answering.

报告人简介：

Fang Wei is currently an assistant professor at Link?ping University, Sweden. She worked as researcher at the University of Freiburg, Germany from 2008 to 2011. Before that, she was a staff member of Information Systems Institute of the Vienna University of Technology from 2005 to 2007. She received her Ph.D from University of Freiburg and M.Sc from Dresden University of Technology, both in Computer Science. Her current research interests are graph databases, ontology reasoning and databases in general. She has published more than over 30 high quality papers in international conferences and journals, such as Artificial Intelligence Journal, ACM Transactions on Computational Logic, SIGMOD, PODS, KR, AAAI.

计算机网络和信息集成教育部重点实验室（东南大学）