Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Index-free Approximation of Reachability Queries on Graphs
Speaker:Srikanta Bedathur
coming from:IIT Delhi
Speakers Bio: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.
Event Type:Colloquium Lecture
Visibility:D1, D2, D3, INET, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Monday, 8 July 2019
Time:15:15
Duration:60 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Gerhard Weikum
Phone:+49 681 9325-5000
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Uwe Brahm, 07/05/2019 11:05 AM
  • Uwe Brahm, 07/05/2019 11:03 AM -- Created document.