Dynamic Graphs

Kineograph

Presented by Ravikant
Updates only to graph structure, not metadata/properties. Add/remove vertices/edges.
Ingest nodes convert input data into transactions, with a unique sequence no. assigned to the subset of transactions applied to a data node. Once a transaction is completed, a progress table maintains the latest seq no. that has been completed (including all prior transactions) for that ingest node.
Ordering of sequence nos across ingest is not considered.
Creation of snapshots commits a particular seq no for each ingest node at each data node.
Snapshots are taken periodically. Applications operate on the snapshots.
After creating a snapshot, each partition decides if each of its vertex was changed (a lot) or not, and based on that calls the compute method on that vertex.
Vertex centric algo, with both push (message passing) and pull (async).
Incremental execution of algo when each new snapshot is created.
Desiderata:
Is this similar to "creating" timeseries graphs rather than being a dynamic graph?
Topo update
Property update
Distributed update
Consistent temporal snapshots
Incremental algorithms
TODO
Additional Reading: Time evolving graphs [RD], dynamic graphs [RD], incremental algorithms [DK]