ACM Transactions on Database Systems · 2020 · 26 citations · 27 references
ComputingComputer ScienceAlgorithmsData StructuresDatabasesOnline AlgorithmsQuery OptimizationQuery ProcessingRelational AlgebraIncremental View MaintenanceMatrix MultiplicationPareto Optimal SolutionStrong Pareto OptimalityView UpdatingWeak Pareto OptimalityWorst-case ComplexityWorst-case Optimization
We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations. We introduce an approach called IVMϵ that exhibits a trade-off between the update time, the space, and the delay for the enumeration of the query result, such that the update time ranges from the square root to linear in the database size while the delay ranges from constant to linear time. IVMϵ achieves Pareto worst-case optimality in the update-delay space conditioned on the Online Matrix-Vector Multiplication conjecture. It is strongly Pareto optimal for the triangle queries with no or three free variables and weakly Pareto optimal for the remaining triangle queries with one or two free variables. IVMϵ recovers prior work such as the suboptimal classical view maintenance approach that uses delta query processing and the worst-case optimal approach that computes all triangles in a static database.
27
Arboricity and Subgraph Listing Algorithms
Norishige Chiba, Takao Nishizeki · SIAM Journal on Computing · 1985 · 665 citations
Finding and counting given length cycles
Noga Alon, Raphael Yuster, Uri Zwick · Algorithmica · 1997 · 613 citations
Finding a Minimum Circuit in a Graph
Alon Itai, Michael Rodeh · SIAM Journal on Computing · 1978 · 397 citations