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.