storage overhead of self-adjusting computation depends on the granularity at which dependencies are tracked, which is in the control of the programmer. my post above provides more information.
- It is not true that self-adjusting computation necessarily leads to large space overheads.
For example recent paper on InCoop (SOCC 2011) and iThreads (ASPLOS 2015) show small space overheads even for very large datasets. If my memory is not failing me I recall space overheads to be less that 20% in many cases. Another paper in ICFP 2014 on DeltaML shows techniques for reducing space overheads.
All of the papers above use the following idea: in self-adjusting computation, the programmer has full control over the granularity of dependency tracking. In one extreme, all dependencies are tracked and even fine grained updates can be updated efficiently but such fine-grained dependency tracking can lead to 10-100x space overheads. In the other extreme, the dependency on the input as a whole is tracked, leading to essentially no space overhead but then any change to the input triggers a whole recomputation. In principle anything in between is possible. For example in InCoop dependencies are tracked at the level of large disk blocks. In iThreads, dependencies are tracked at the level of OS pages. In DeltaML (ICFP 2014) paper, dependencies are tracked at a level blocks determined by the programmer.
- Self-adjusting computation does not assume that a small change has to lead to a small change in the execution path. The change in the execution path however determines the update time. This is the cost model that self-adjusting computation offers. There are many techniques for controlling the size of the change in the execution path, as can be seen by some of the more sophisticated applications of self-adjusting computation on large data sets (incoop, ithreads, deltaML), machine learning (inference), and computational geometry. In all of these cases, self-adjusting computation leads to asymptotic improvements compared to batch computation.
One ultimately powerful technique that allows the programmer/designer to control the efficiency is traceable data structures (PLDI 2010 paper), which allows application specific logic to be exploited as desired.
Traceable data structures also allow defining domain-specific solutions (by using the appropriately designed traceable data structures).
Paper on traceable data structures:
www.umut-acar.org/publications/pldi2010.pdf