public final class EliasFanoCumulativeOutdegreeList extends Object
A contentaddressable representation of the cumulative function of outdegrees that uses a strippeddown
implementation of Elias–Fano's representation of monotone sequences partially taken from EliasFanoMonotoneLongBigList
.
The purpose of this class is that of storing quasisuccinctly the outdegrees of a graph so that it is easy to find quickly a batch of nodes whose overall outdegree is a given quantity. It is most effective in multicore computations depending on the outdegree, as usually the transposed graph has some very highdegree nodes, and often in web graphs, due to crawling artifacts, these nodes are very close. As a result, a nodebased job assignment ends up in creating batches of nodes that are incredibly expensive, which in turns produced an unbalanced iteration (e.g., in the last part few processors are actually working).
The main access method is skipTo(long)
, which will return a value of the cumulative function larger than or equal to
its argument. At that point, currentIndex()
returns the index of the node that realize that value.
Constructor and Description 

EliasFanoCumulativeOutdegreeList(ImmutableGraph graph)
Creates a cumulative outdegree list with no rounding mask.

EliasFanoCumulativeOutdegreeList(ImmutableGraph graph,
long numArcs)
Creates a cumulative outdegree list with no rounding mask.

EliasFanoCumulativeOutdegreeList(ImmutableGraph graph,
long numArcs,
long roundingMask)
Creates a cumulative outdegree list with specified rounding mask.

Modifier and Type  Method and Description 

long 
currentIndex()
Returns the index realizing the last value returned by
skipTo(long) , that is,
an index x such that the sum of the outdegrees of the nodes of index (strictly) smaller
than x is equal to the last value returned by skipTo(long) . 
long 
skipTo(long lowerBound)
Returns the first value of the cumulative function of outdegrees that is larger than or equal to the provided bound and
that respect the rounding mask provided at construction time.

public EliasFanoCumulativeOutdegreeList(ImmutableGraph graph)
graph
 a graph.public EliasFanoCumulativeOutdegreeList(ImmutableGraph graph, long numArcs)
graph
 a graph.numArcs
 the number of arcs in the graph (this parameter can be useful as some ImmutableGraph
implementations
do not support ImmutableGraph.numArcs()
).public EliasFanoCumulativeOutdegreeList(ImmutableGraph graph, long numArcs, long roundingMask)
graph
 a graph.numArcs
 the number of arcs in the graph (this parameter can be useful as some ImmutableGraph
implementations
do not support ImmutableGraph.numArcs()
).roundingMask
 a number of the form 2^{k} − 1. After each call to skipTo(long)
,
currentIndex()
is guaranteed to return a multiple of 2^{k}, unless currentIndex()
is
equal to the number of nodes in graph
.public long currentIndex()
skipTo(long)
, that is,
an index x such that the sum of the outdegrees of the nodes of index (strictly) smaller
than x is equal to the last value returned by skipTo(long)
.skipTo(long)
, or 1 if skipTo(long)
has never been called.public long skipTo(long lowerBound)
lowerBound
 a lower bound on the returned value.lowerBound
and
that respect the rounding mask provided at construction time.