Lab Lunch: 29 January 2019 - Milos Nikolic

Title: Counting Triangles under Update in Worst Case Optimal Time

Abstract:

We consider the problem of incrementally maintaining the triangle count query under single-tuple updates to the input relations.

We introduce an approach that exhibits a space-time tradeoff such that the update time can be as low as the square root of the size of the input database. This lowest update time is worst-case optimal conditioned on the Online Matrix-Vector Multiplication conjecture. Existing incremental view maintenance approaches are recovered as special, yet suboptimal, cases of our approach within the space-time tradeoff.

Note by the speaker: This work has won the best paper award at ICDT (International Conference on Database Theory) 2019.