3 ms·
Incremental computation is an interesting idea, and could be very useful to big data processing. However, the particular incremental technique of self-adjusting
by finch_ 11y ago
Incremental computation is an interesting idea, and could be very useful to big data processing. However, the particular incremental technique of self-adjusting computation has two big flaws:
- There is a significant storage overhead due to all of the data that is collected about the computation (the "dynamic dependency graph").
- It makes the assumption that if the input to your algorithm changes a little, the execution path and intermediate variable values will still be the same for most of the computation. This is not true for many algorithms you might wish to make incremental.
I'm not necessarily saying these issues couldn't be overcome, but a lot more research is needed.
For some other alternatives to incremental computation that avoid these flaws (while introducing other problems of their own), you could look into:
DBToaster: http://www.dbtoaster.org/ http://www.dbtoaster.org/
LINVIEW: http://dl.acm.org/citation.cfm?id=2588555.2610519 http://dl.acm.org/citation.cfm?id=2588555.2610519
- assface 11y agoThere is a significant storage overhead due to all of the data that is collected about the computation (the "dynamic dependency graph"). The storage overhead is massive. It's a non-starter with this approach. Our experiments with self-adjusting computation were in the range of 30-100x for simple algorithms. That means if you have a 1TB data set, you need 30TB just to store the intermediate results. A relational database with materialized views or the special purpose systems that you cite (DBToaster, LINVIEW) are better approaches.
- umutacar 11y agostorage 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.