Graph processing

MapReduce doesn’t efficiently express data dependencies Ghost vertices maintain adjacency structure and replicate remote data

Distributed consistency Solution 1: Chromatic Engine - Edge Consistency via Graph Coloring Solution 2: Distributed Locking

GraphLab / PowerGraph

To achieve serializability, GraphLab prevents adjacent vertex-programs from running concurrently using a fine-grained locking protocol which requires sequentially grabbing locks on all neighboring vertices. Furthermore, the locking scheme used by GraphLab is unfair to high degree vertices.

PowerGraph retains the strong serializability guarantees of GraphLab while addressing its limitations. We address the problem of sequential locking by introducing a new parallel locking protocol which is fair to high degree vertices.

Chronograph [18] combines components of all these systems, providing a dynamic graph model which allows concurrent modifications via an unbound stream of updates. This is enabled by instantiating vertices as actors [19] and performing local event sourcing, where each vertex logs its changes and that of its outgoing edges. A global log is then only required to maintain vertex creation and deletion order, minimising bottlenecks. Various computation models may then execute on top of this, performing online approximations on the live dynamic graph and offline batch processing on consistent snapshots. However, whilst this permits temporal analysis via snapshot comparison, the history is not maintained in memory and snapshots must be recomputed from the stored logs.

As established distributed graph processing systems focus primarily on snapshot comparison for temporal analysis, it appeared appropriate to investigate how temporal graphs have been proposed and formalised, as well as understand the manner in which temporal information is traditionally stored. Having many multi-disciplinary applications, a range of models are available in the literature under various pseudonyms such as temporal networks [1] and evolving graphs [20]. These are, therefore, explored to discuss all desirable characteristics, noting possible expansions.

results matching ""

    No results matching ""