Counting Triangles under Updates in Worst-Case Optimal Time
- Submitting institution
-
University of Edinburgh
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 84961547
- Type
- E - Conference contribution
- DOI
-
10.4230/LIPIcs.ICDT.2019.4
- Title of conference / published proceedings
- 22nd International Conference on Database Theory (ICDT 2019)
- First page
- 4:1
- Volume
- 127
- Issue
- -
- ISSN
- 1868-8969
- Open access status
- Compliant
- Month of publication
- March
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
B - Data Science and Artificial Intelligence
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Triangle queries serve as prime examples that showcase the suboptimality of mainstream join algorithms used by virtually all commercial database systems. This work presents the first-ever sublinear algorithm for evaluating the triangle count query over a changing database. This novel algorithm is also worst-case optimal, meaning that no lower running time is possible. This work won the best paper award at ICDT 2019, one of the top two database theory conferences, and led to multiple follow-up papers in PODS, TODS, and ICDT, generalising its ideas to a broader class of queries.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -