27.03.2017, 16 Uhr c.t. TU Berlin, EN building, seminar room EN 719 (7th floor), Einsteinufer 17, 10587 Berlin: "Monitoring motifs in graph streams" (Frank McSherry)
Imagine you are in charge of a high-volume stream of social interactions, and you would like to watch for certain graph structures in the stream of interactions. For example, Twitter recommends "who to follow" by looking for accounts followed by at least two accounts you follow, a structure which can be described by a four node graph. There can be a substantial number of these motifs in a graph, but what if you only need to observe the changes as they happen, rather than enumerate all instances at once?
This work is an instance of the more general problem of maintaining cyclic (non-treelike) joins as the underlying relations change. We will first summarize recent work in worst-case optimal join evaluation (Ngo et al., 2014) which shows how to evaluate cyclic joins using resources asymptotically bounded by the largest possible output of the join (a property standard trees of binary joins cannot satisfy). We then build up a dataflow version of this algorithm, extend it to efficiently respond to changes in its inputs, and describe and evaluate its implementation in timely dataflow*.
This project is joint work with Khaled Ammar and Semih Salihoglu, both of University of Waterloo.
*: Timely dataflow's cycles are not required for this implementation, so it could also be suitable for other, less crazy streaming systems.