PhD Seminar • Data Systems — Differential Computation Optimizations for Path Queries

Khaled Ammar, PhD candidate
David R. Cheriton School of Computer Science

Differential Computation (DC) has shown strong performance for maintaining the answer of different data flow queries as data change over time. 

In this talk, we are using DC to answer BFS queries in an active graph database. We show that a BFS module is generic and can answer different path queries, such as SSSP, SPSP, and variable path queries. In our active graph database, a user would register her queries and the database actively maintains its answer as the graph changes. DC is a great fit for this setting because of its throughput performance, but it has a serious scalability issues due to storing all changes in the input and output of every operation. We study the possibility of dropping some of these changes and show how to gain linear scalability without a significant impact on its throughput.