Counting triangles under updates in worst-case optimal time
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2019
|
| _version_ | 1797084575831162880 |
|---|---|
| author | Kara, A Ngo, H Nikolic, M Olteanu, D Zhang, H |
| author_facet | Kara, A Ngo, H Nikolic, M Olteanu, D Zhang, H |
| author_sort | Kara, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:57:04Z |
| format | Conference item |
| id | oxford-uuid:9c10651b-ba83-4aea-af4a-34d4c92d28d5 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:57:04Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:9c10651b-ba83-4aea-af4a-34d4c92d28d52022-03-27T00:33:31ZCounting triangles under updates in worst-case optimal timeConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9c10651b-ba83-4aea-af4a-34d4c92d28d5Symplectic Elements at OxfordSchloss Dagstuhl2019Kara, ANgo, HNikolic, MOlteanu, DZhang, HWe 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. |
| spellingShingle | Kara, A Ngo, H Nikolic, M Olteanu, D Zhang, H Counting triangles under updates in worst-case optimal time |
| title | Counting triangles under updates in worst-case optimal time |
| title_full | Counting triangles under updates in worst-case optimal time |
| title_fullStr | Counting triangles under updates in worst-case optimal time |
| title_full_unstemmed | Counting triangles under updates in worst-case optimal time |
| title_short | Counting triangles under updates in worst-case optimal time |
| title_sort | counting triangles under updates in worst case optimal time |
| work_keys_str_mv | AT karaa countingtrianglesunderupdatesinworstcaseoptimaltime AT ngoh countingtrianglesunderupdatesinworstcaseoptimaltime AT nikolicm countingtrianglesunderupdatesinworstcaseoptimaltime AT olteanud countingtrianglesunderupdatesinworstcaseoptimaltime AT zhangh countingtrianglesunderupdatesinworstcaseoptimaltime |