Prof. Dr. Srikanta Bedathur is an associate professor at the Department of Computer Science and Engineering at IIT Delhi, and an adjunct faculty member at IIIT Delhi. Until recently he worked as a research scientist at IBM Research as part of their AI Research team. Before joining IBM in 2014, he worked as a faculty member at IIIT Delhi, where I founded the Max-Planck Partner Group on Large-scale Graph Search and Mining. Even before joining IIIT-D, he was a senior researcher at the Max-Planck Institute for Informatics (MPII) as part of the Databases and Informatics Systems department. My PhD (2005) was from the Indian Institute of Science, Bangalore.

AG 1, AG 2, AG 3, INET, AG 4, AG 5, SWS, RG1, MMCI   Info

MPI Audience

English

60 Minutes

Saarbrücken

Reachability queries are commonly used on directed graphs to answer a simple decision problem - are given two vertices s and t connected? There has been a lot of work in data management community to build indexes to answer them efficiently over large graphs. But most real-world graphs have edge/vertex labels and temporal annotations which are used to constrain the kind of reachability one is interested in. Further, most graphs are also highly dynamic, making expensive repeated index construction impractical.

In this talk, I present our recent practical approach in using random walks on graphs for addressing these issues at scale albeit with small reduction in accuracy. First I present ARROW, which operates on dynamic and temporally annotated graphs to answer a variety of reachability queries with no preprocessing of the network. Next, I will present ARRIVAL, an adaptation to operate on labeled graphs to answer regular simple path reachability queries --known to be NP-complete in general-- with near-exact accuracy. I conclude with ideas on how we can extend ARROW and ARRIVAL further to make even more sophisticated reachability queries scalable in practice.

Gerhard Weikum

+49 681 9325-5000

--email hidden

passcode not visible

logged in users only