Abstract / Description of output
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 space-time product is quadratic in the size of the input database and the update time can be as low as the square root of this size. This lowest update time is worst-case optimal conditioned on the Online Matrix-Vector Multiplication conjecture.
The classical and factorized incremental view maintenance approaches are recovered as special cases of our approach within the space-time tradeoff. In particular, they require linear-time maintenance under updates, which is suboptimal. Our approach can also count all triangles in a static database in the worst-case optimal time needed for enumerating them.
The classical and factorized incremental view maintenance approaches are recovered as special cases of our approach within the space-time tradeoff. In particular, they require linear-time maintenance under updates, which is suboptimal. Our approach can also count all triangles in a static database in the worst-case optimal time needed for enumerating them.
Original language | English |
---|---|
Title of host publication | 22nd International Conference on Database Theory (ICDT 2019) |
Editors | Pablo Barcelo, Marco Calautti |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany |
Pages | 4:1-4:18 |
Number of pages | 18 |
ISBN (Electronic) | 978-3-95977-101-6 |
DOIs | |
Publication status | Published - 19 Mar 2019 |
Event | 22nd International Conference on Database Theory - Lisbon, Portugal Duration: 26 Mar 2019 → 29 Mar 2019 http://edbticdt2019.inesc-id.pt/ |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 127 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | 22nd International Conference on Database Theory |
---|---|
Abbreviated title | ICDT 2019 |
Country/Territory | Portugal |
City | Lisbon |
Period | 26/03/19 → 29/03/19 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- incremental view maintenance
- amortized analysis
- data skew
Fingerprint
Dive into the research topics of 'Counting Triangles under Updates in Worst-Case Optimal Time'. Together they form a unique fingerprint.Profiles
-
Milos Nikolic
- School of Informatics - Lecturer in Database Systems
- Laboratory for Foundations of Computer Science
- Data Science and Artificial Intelligence
Person: Academic: Research Active