Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Differential Dataflow but at what cost? (2017)

github.com

Post reply on HN
Print view View original

1–10 of 14 posts

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

#4

Post by edflsafoiewq »

mehrdadn wrote: post #3

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

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 is to, instead of recomputing the output every time from scratch, find a function g that will compute the output-difference from the input-difference

    input = ...;     output = f(input);
    input += d1;     output += g(d1);
    input += d2;     output += g(d2);
    input += d3;     output += g(d3);
And I think if you write f using the combinators from the differential dataflow framework it will be able to find g automatically for you.

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

#5

Post by mehrdadn »

edflsafoiewq wrote: post #4
mehrdadn wrote: post #3

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

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…

Yeah, makes sense. Dynamic breadth first search has been a thing for a while; it seems like they're just introducing it with a new name. The automatic part seems cool though!

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

#6

Post by hexane360 »

mehrdadn wrote: post #5
edflsafoiewq wrote: post #4

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…

Yeah, makes sense. Dynamic breadth first search has been a thing for a while; it seems like they're just introducing it with a new name. The automatic part seems cool though!

The idea is that it isn't limited to breadth first searches. It provides a way to write algorithms such that they are automatically differential in nature.

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

#7

Post by iamwil »

edflsafoiewq wrote: post #4
mehrdadn wrote: post #3

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

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…

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

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

#8

Post by [deleted] »

hexane360 wrote: post #6
mehrdadn wrote: post #5

Earlier quoted context omitted.

Yeah, makes sense. Dynamic breadth first search has been a thing for a while; it seems like they're just introducing it with a new name. The automatic part seems cool though!

The idea is that it isn't limited to breadth first searches. It provides a way to write algorithms such that they are automatically differential in nature.

[deleted]

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

#9

Post by iamwil »

edflsafoiewq wrote: post #4
mehrdadn wrote: post #3

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

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?

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

#10

Post by benesch »

iamwil wrote: post #7
edflsafoiewq wrote: post #4

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…

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/differential-dataflow/

[1]: http://sigops.org/s/conferences/sosp/2013/papers/p439-murray...

Post reply on HN