Counting Triangles under Updates in Worst-Case Optimal Time

Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publication22nd International Conference on Database Theory (ICDT 2019)
EditorsPablo Barcelo, Marco Calautti
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages4:1-4:18
Number of pages18
ISBN (Electronic)978-3-95977-101-6
DOIs
Publication statusPublished - 19 Mar 2019
Event22nd International Conference on Database Theory - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019
http://edbticdt2019.inesc-id.pt/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume127
ISSN (Electronic)1868-8969

Conference

Conference22nd International Conference on Database Theory
Abbreviated titleICDT 2019
Country/TerritoryPortugal
CityLisbon
Period26/03/1929/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.

Cite this