2 ms·
Do note that the existing name in the CS literature for algorithms that can cheaply provide an "updated" result given a change in the input is dynamic, not diff
by zozbot234 4y ago
Do note that the existing name in the CS literature for algorithms that can cheaply provide an "updated" result given a change in the input is dynamic, not differential. "Differential" actually refers to something else altogether, namely being able to automatically compute the gradient of some general calculation on continuous-valued inputs! (The intersection of differential and dynamic problems, where the point is to recompute answers quickly when some continuous-valued input changes, is called "kinetic".)
"Incremental" is actually a special case of dynamic, where all updates are restricted to 'adding' input data only. (Thus "incremental" algorithms, properly understood, are closely related to "online" algorithms, e.g. those which process input data in a streaming fashion as opposed to assuming a "complete" input to begin with.)
- dan-robertson 4y agoI figured the name was a pun on differential dataflow, and the readme seems to agree. Differential dataflow is a framework for doing "dynamic" computations by modelling them as dataflow with diffs of values rather than values flowing between nodes. The main user, materialize, has bags of tuples on most nodes and diffs are then tulles and the change to their counts. Differential data flow has a system called timely dataflow at its core and timely dataflow sends timestamp-like metadata with values to allow loops and for the output of the dynamic computation to be internally consistent
- namibj 4y agoDifferential here comes from differentiating map/reduce type multiset operators, which are then run/executed using Timely Dataflow.
- a-saleh 4y agoA.f.a.i.k the name is based on the underlying library and research on Dfferential Dataflow by F. McSherry https://www.microsoft.com/en-us/research/publication/differential-dataflow/ https://www.microsoft.com/en-us/research/publication/differe... and https://timelydataflow.github.io/differential-dataflow/ https://timelydataflow.github.io/differential-dataflow/ ... I think the pitch is that this concept is enough improvement on incremental approaches it warrants a new name. But I love these. From Functional Reactive Programming through propagator networks and embedding functional languages in datalog datafun-style, there seems to be this new-ish approach to computation that maybe somebody finally cleaves out of academia! The eve-lang guys were close but too ambitious. Maybe VMWare has less ambitious, more focused tool in mind. Because datalogs are so cool! But only time I see them in practice are bespoke implementations for like ... compiler optimization tuning?