Incremental computation concerns the re-computation of output after a change in the input. Incremental algorithms, also called dynamic or on-line algorithms, process a change in the input by identifying the "affected output", that is, the part of the previous output that is no longer "correct", and "updating" it.
This thesis presents results--upper bound results, lower bound results, and experimental results--for several incremental computation problems. The common theme in all these results is that the complexity of an algorithm or problem is analyzed in terms of a parameter $\Vert\delta\Vert$ that measures the size of the change in the input and output. An incremental algorithm is said to be bounded if the time it takes to update the output depends only on the size of the change in the input and output (i.e., $\Vert\delta\Vert),$ and not on the size of the entire current input. A problem is said to be bounded (unbounded) if it has (does not have) a bounded incremental algorithm. The results in this thesis, summarized below, illustrate a complexity hierarchy for incremental computation from this point of view.
We present $O(\Vert\delta\Vert\log\Vert\delta\Vert)$ incremental algorithms for several shortest-path problems and a generalization of the shortest-path problem, establishing that these problems are polynomially bounded.
We present an $O(2\sp{\Vert\delta\Vert})$ incremental algorithm for the circuit value annotation problem, which matches a previous $\Omega(2\sp{\Vert\delta\Vert})$ lower bound for this problem and establishes that the circuit value annotation problem is exponentially bounded. We also present experimental results that show that our algorithm, in spite of a worst-case complexity of $\Theta(2\sp{\Vert\delta\Vert}),$ appears to work well in practice.
We present lower bounds showing that a number of problems, including graph reachability, dataflow analysis, and algebraic path problems, are unbounded with respect to a model of computation called the sparsely-aliasing pointer machine model.
We present an $O(\Vert\delta\Vert\log\ n)$ incremental algorithm for the reachability problem in reducible flowgraphs, and an algorithm for maintaining the dominator tree of a reducible flowgraph.
Cited By
- Hentenryck P, Michel L and Liu L (2005). Contraint-Based Combinators for Local Search, Constraints, 10:4, (363-384), Online publication date: 1-Oct-2005.
- Michel L and Hentenryck P A constraint-based architecture for local search Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, (83-100)
- Chandrachoodan N, Bhattacharyya S and Liu K (2002). High-level synthesis of DSP applications using adaptive negative cycle detection, EURASIP Journal on Advances in Signal Processing, 2002:1, (893-907), Online publication date: 1-Jan-2002.
- Michel L and Hentenryck P (2019). A constraint-based architecture for local search, ACM SIGPLAN Notices, 37:11, (83-100), Online publication date: 17-Nov-2002.
- Alberts D, Cattaneo G and Italiano G (1997). An empirical study of dynamic graph algorithms, Journal of Experimental Algorithmics (JEA), 2, (5-es), Online publication date: 1-Jan-1997.
- Alberts D, Cattaneo G and Italiano G An empirical study of dynamic graph algorithms Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, (192-201)
- Sreedhar V, Gao G and Lee Y Incremental computation of dominator trees Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, (1-12)
- Sreedhar V, Gao G and Lee Y (1995). Incremental computation of dominator trees, ACM SIGPLAN Notices, 30:3, (1-12), Online publication date: 1-Mar-1995.
- Wirén M Minimal change and bounded incremental parsing Proceedings of the 15th conference on Computational linguistics - Volume 1, (461-467)
Index Terms
- Bounded incremental computation
Recommendations
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
On Packing Two Graphs with Bounded Sum of Sizes and Maximum Degree
A packing of graphs $G_1$ and $G_2$, both on $n$ vertices, is a set $\{H_1,H_2\}$ such that $H_1\cong G_1$, $H_2\cong G_2$, and $H_1$ and $H_2$ are edge disjoint subgraphs of $K_n$. In 1978, Sauer and Spencer [J. Combin. Theory Ser. B, 25 (1978), pp. 295--...