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.
Authors: Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang. 2019.
In Proceedings of the 22nd International Conference on Database Theory (ICDT ‘19). (Best Paper Award).
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.
Read the PDF: Counting Triangles under Updates in Worst-Case Optimal Time (opens in a new tab)
Related Posts
From the Lab to Production: A Case Study of Session-Based Recommendations in the Home-Improvement Domain
E-commerce applications rely heavily on session-based recommendation algorithms to improve the shopping experience of their customers. Recent progress in session-based recommendation algorithms shows great promise. However, translating that promise to real-world outcomes is a challenging task for several reasons, but mostly due to the large number and varying characteristics of the available models. In this paper, we discuss the approach and lessons learned from the process of identifying and deploying a successful session-based recommendation algorithm for a leading e-commerce application in the home-improvement domain. To this end, we initially evaluate fourteen session-based recommendation algorithms in an offline setting using eight different popular evaluation metrics on three datasets.
Next-Paradigm Programming Languages: What Will They Look Like and What Changes Will They Bring?
What will be the common principles behind next-paradigm, high-productivity programming languages, and how will they change everyday program development? I would like to focus on a question with an answer that can be, surprisingly, clearer: what will be the common principles behind next-paradigm, high-productivity programming languages, and how will they change everyday program development?