Differential dataflow roadmap | Hacker News Reader

Differential dataflow roadmap

github.com

88 pointsdmit4 comments

Frank McSherry was a researcher at MSR Silicon Valley; when the office was closed in 2014, most (all?) of the researchers were also let go. Frank was a member of a research group working on differential dataflow; not long before the office was closed they released a really awesome open-source library, Naiad [0], which looked extremely promising as a means for efficiently implementing certain stream-processing tasks.

The team had a nice blog [1] going too, explaining how different aspects of Naiad make it more efficient than other stream-processing systems (at least, for certain classes of algorithms).

[0]: https://github.com/MicrosoftResearch/Naiad/

[1]: https://bigdataatsvc.wordpress.com/

So... After following the link I am dropped in the middle of the development diary of some project. After skimming the notes I can see that the project is

a) related to data processing

b) has not yet reached the stage of practical applicability

c) is fun to hack on

And not much more. Could someone provide more context?

A short answer: It's a recent approach to incremental computation geared towards data-science/db people. Imagine you want to maintain the connected components of a graph where edges are being added and removed. It turns out you can express this using dataflow and get reasonable looking runtimes (30,000 edge ins/del per second) [1]. You could probably do much better with a careful implementation of parallel union-find for just edge-insertions but part of the appeal of data-flow is that you express your computation using functional primitives like joins, maps and filters and then the incremental stuff 'just works'.

[1] http://www.frankmcsherry.org/differential/dataflow/2015/05/1...

this kind of thing might be interesting for local search algorithms where you want to explore different variations / adjustments of a particular structure and want to maintain some kind of topological invariants while you are doing so. E.g. search the neighbourhood of a given tree by adding / deleting edges, while preserving that what you get is in fact still a tree

Reply on news.ycombinator.com