Personal tools
You are here: Home Events Lab Lunch Talk: Counting triangles under updates in worst-case optimal time

Lab Lunch Talk: Counting triangles under updates in worst-case optimal time

— filed under:

Speaker: Milos Nikolic

What
  • Lab Lunch
When Jan 29, 2019
from 01:00 PM to 02:00 PM
Where MF2, Level 4
Add event to calendar vCal
iCal

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.

 

Document Actions