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. Jan 29 2019 13.00 - 14.00 Lab Lunch: 29 January 2019 - Milos Nikolic Speaker: Milos Nikolic MF2 level 4
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. Jan 29 2019 13.00 - 14.00 Lab Lunch: 29 January 2019 - Milos Nikolic Speaker: Milos Nikolic MF2 level 4
