Live data from Hacker News

Differential Dataflow but at what cost? (2017)

github.com

11–14 of 14 posts

Re: Differential Dataflow but at what cost? (2017)

#11
post #9

Earlier quoted context omitted.

Incremental. I think the problem is this: you have an input that you want to change a bunch of times input = ...; input += d1; input += d2; input += d3; and you have some output that depends on the input. Whenever the input changes, the output needs to be recomputed, like this input = ...; output = f(input); input += d1; output = f(input); input += d2; output = f(input); input += d3; output = f(input); The idea here…

How would writing f using combinators yield the ability to derive g?

Each combinator knows how to produce the output diff from an input diff; the computation is then just a matter of stringing these combinators together.

For example, consider a map combinator. The output diff is just the input diff with a function applied to the data. More formally, for every incoming (data, time, diff) triple, an output triple (f(data), time, diff) is produced.

For a filter combinator, the output is (data, time, diff) if f(data) is true, or (data, time, 0) if f(data) is false.

A computation that wants to filter and map some data then just requires piping together these operators.

Things get interesting when you want to aggregate and join data, but Frank’s blog posts and documentation explain how you build that in a dataflow system far better than I can here.

Re: Differential Dataflow but at what cost? (2017)

#12
post #10
post #7

Earlier quoted context omitted.

Where did you learn how it worked? Was it just through his other blog posts?

Frank’s written a tutorial style mdbook on Differential [0] that I highly recommend in addition to his blog posts. There’s also the research paper on the spawned the Timely and Differential projects, Naiad [1]. If you get into it, the library itself is well documented on docs.rs and there’s an active Gitter channel. (Disclaimer: I work with Frank at his company, Materialize.) [0]: https://timelydataflow.github.io/dif…

Obviously computing output-diffs from input-diffs looks a lot like automatic differentiation. Is there a precise relationship?

Re: Differential Dataflow but at what cost? (2017)

#13
post #3

Is differential a synonym for "dynamic" (or "incremental") here?

The main distinction that led to a different name is that (unlike most instances of dynamic or incremental algorithms) differential dataflow allows you to move through a partial order of updates, rather than a sequence of updates. This is important for automatically updating iterative computations, if you want to do multi-temporal streaming computation, and a few other reasons.

It appeared at the time analogous to multivariate calculus, though the better analogy appears to be to Moebius inversion (roughly: integration and differentiation on partial orders). Read more here: https://en.wikipedia.org/wiki/Möbius_inversion_formula

"Moebius dataflow" would have been a pretty bad-ass name, I think we can all agree. And it might have done a better job of preparing the reader for what was about to happen to their brain.

Re: Differential Dataflow but at what cost? (2017)

#14
post #3

Is differential a synonym for "dynamic" (or "incremental") here?

The main distinction that led to a different name is that (unlike most instances of dynamic or incremental algorithms) differential dataflow allows you to move through a partial order of updates, rather than a sequence of updates. This is important for automatically updating iterative computations, if you want to do multi-temporal streaming computation, and a few other reasons. It appeared at the time analogous to mu…

Wow thanks a ton, looks like I have some more reading to do! :)
Post reply on HN