com.bigdata.rdf.graph

Interface IGASProgram<VS,ES,ST>

Type Parameters:

VS - The generic type for the per-vertex state. This is scoped to the computation of the IGASProgram.

ES - The generic type for the per-edge state. This is scoped to the computation of the IGASProgram.

ST - The generic type for the SUM. This is often directly related to the generic type for the per-edge state, but that is not always true. The SUM type is scoped to the GATHER + SUM operation (NOT the computation).

All Superinterfaces:

IBindingExtractor<VS,ES,ST>, IGASOptions<VS,ES,ST>

All Known Implementing Classes:

BaseGASProgram, BFS, CC, PATHS, PR, SSSP

public interface IGASProgram<VS,ES,ST>
extends IGASOptions<VS,ES,ST>, IBindingExtractor<VS,ES,ST>

Abstract interface for GAS programs.

Author:

Bryan Thompson TODO DESIGN: The broad problem with this approach is that it is overly coupled with the Java object model. Instead it needs to expose an API that is aimed at vectored (for GPU) execution with 2D partitioning (for out-of-core, multi-node).

Method Summary

Methods

Modifier and Type	Method and Description
VS	apply(IGASState<VS,ES,ST> state, org.openrdf.model.Value u, ST sum) Apply the reduced aggregation computed by GATHER + SUM to the vertex.
void	before(IGASContext<VS,ES,ST> ctx) One time initialization before the IGASProgram is executed.
ST	gather(IGASState<VS,ES,ST> state, org.openrdf.model.Value u, org.openrdf.model.Statement e) GATHER is a map/reduce over the edges of the vertex.
void	initVertex(IGASContext<VS,ES,ST> ctx, IGASState<VS,ES,ST> state, org.openrdf.model.Value u) Callback to initialize the state for each vertex in the initial frontier before the first iteration.
boolean	isChanged(IGASState<VS,ES,ST> state, org.openrdf.model.Value u) Return true iff the vertex should run its SCATTER phase.
boolean	nextRound(IGASContext<VS,ES,ST> ctx) Return true iff the algorithm should continue.
void	scatter(IGASState<VS,ES,ST> state, IGASScheduler sch, org.openrdf.model.Value u, org.openrdf.model.Statement e)
ST	sum(IGASState<VS,ES,ST> state, ST left, ST right) SUM is a pair-wise reduction that is applied during the GATHER.

Methods inherited from interface com.bigdata.rdf.graph.IGASOptions

getEdgeStateFactory, getGatherEdges, getInitialFrontierEnum, getSampleEdgesFilter, getScatterEdges, getVertexStateFactory

Methods inherited from interface com.bigdata.rdf.graph.IBindingExtractor

getBinderList

Method Detail

before

void before(IGASContext<VS,ES,ST> ctx)

One time initialization before the IGASProgram is executed.

Parameters:

ctx - The evaluation context.

initVertex

void initVertex(IGASContext<VS,ES,ST> ctx,
              IGASState<VS,ES,ST> state,
              org.openrdf.model.Value u)

Callback to initialize the state for each vertex in the initial frontier before the first iteration. A typical use case is to set the distance of the starting vertex to ZERO (0).

Parameters:

u - The vertex. TODO We do not need both the IGASContext and the IGASState. The latter is available from the former.

gather

ST gather(IGASState<VS,ES,ST> state,
        org.openrdf.model.Value u,
        org.openrdf.model.Statement e)

GATHER is a map/reduce over the edges of the vertex. The SUM provides pair-wise reduction over the edges visited by the GATHER.

Parameters:

u - The vertex for which the gather is being performed. The gather will be invoked for each edge indident on u (as specified by IGASOptions.getGatherEdges()).

e - An edge (s,p,o).

Returns:

The new edge state accumulant. FIXME DESIGN: The problem with pushing the ISPO onto the ES is that we are then forced to maintain edge state (for the purposes of accessing those ISPO references) even if the algorithm does not require any memory for the edge state!

Note: by lazily resolving the vertex and/or edge state in the GAS callback methods we avoid eagerly materializing data that we do not need. [Lazy resolution does not work on a cluster. The only available semantics there are lazy resolution of state that was materialized in order to support a gather() or scatter() for a vertex.]

Note: The state associated with the source/target vertex and the edge should all be immutable for the GATHER. The vertex state should only be mutable for the APPLY(). The target vertex state and/or edge state MAY be mutable for the SCATTER, but that depends on the algorithm. How can we get these constraints into the API?

sum

ST sum(IGASState<VS,ES,ST> state,
     ST left,
     ST right)

SUM is a pair-wise reduction that is applied during the GATHER.

Parameters:

left - An edge state accumulant.

right - Another edge state accumulant.

Returns:

Their "sum". TODO DESIGN: Rather than pair-wise reduction, why not use vectored reduction? That way we could use an array of primitives as well as objects. TODO DESIGN: This should be a reduced interface since we only need access to the comparator semantics while the [state] provides random access to vertex and edge state. The comparator is necessary for MIN semantics for the Value implementation of the backend. E.g., Value versus IV.

apply

VS apply(IGASState<VS,ES,ST> state,
       org.openrdf.model.Value u,
       ST sum)

Apply the reduced aggregation computed by GATHER + SUM to the vertex.

Parameters:

u - The vertex.

sum - The aggregated accumulate across the edges as computed by GATHER and SUM -or- null if there is no accumulant (this will happen if the GATHER did not find any edges to visit).

Returns:

The new state for the vertex. TODO How to indicate if there is no state change? return the same object? This only matters with secondary storage for the vertex state. Alternative is to side-effect the vertex state, but then we can not manage the barriers (BFS versus asynchronous). Except for indicating that the state is dirty, we do not need a return value. [The pattern appears to be that a vertex leaves a marker on its vertex state object indicating whether or not it was changed and then tests that state when deciding whether or not to scatter]. TODO There could be a big win here if we are able to detect when a newly initialized vertex state does not "escape" and simply not store it. For some graphs, the vertexState map grows very rapidly when compared to either the frontier or the set of states that have been in the frontier during the computation.

isChanged

boolean isChanged(IGASState<VS,ES,ST> state,
                org.openrdf.model.Value u)

Return true iff the vertex should run its SCATTER phase. This may be used to avoid visiting the edges if it is known (e.g., based on the APPLY) that the vertex has not changed. This can save a substantial amount of effort.

Parameters:

state -

u - The vertex.

Returns:

scatter

void scatter(IGASState<VS,ES,ST> state,
           IGASScheduler sch,
           org.openrdf.model.Value u,
           org.openrdf.model.Statement e)

Parameters:

state -

u - The vertex for which the scatter will being performed.

e - The edge.

nextRound

boolean nextRound(IGASContext<VS,ES,ST> ctx)

Return true iff the algorithm should continue. This is invoked after every iteration, once the new frontier has been computed and IGASState.round() has been advanced. An implementation may simply return true, in which case the algorithm will continue IFF the current frontier is not empty.

Note: While this can be used to make custom decisions concerning the halting criteria, it can also be used as an opportunity to handshake with a custom IGraphAccessor in order to process a dynamic graph.

Parameters:

ctx - The evaluation context.

Returns:

true if the algorithm should continue (as long as the frontier is non-empty).