Class EliasFanoCumulativeOutdegreeList
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 Summary
Constructors Constructor 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, int roundingMask)
Creates a cumulative outdegree list with specified rounding mask. 
Method Summary
Modifier and Type Method Description int
currentIndex()
Returns the index realizing the last value returned byskipTo(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 byskipTo(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.

Constructor Details

EliasFanoCumulativeOutdegreeList
Creates a cumulative outdegree list with no rounding mask. Parameters:
graph
 a graph.

EliasFanoCumulativeOutdegreeList
Creates a cumulative outdegree list with no rounding mask. Parameters:
graph
 a graph.numArcs
 the number of arcs in the graph (this parameter can be useful as someImmutableGraph
implementations do not supportImmutableGraph.numArcs()
).

EliasFanoCumulativeOutdegreeList
Creates a cumulative outdegree list with specified rounding mask. Parameters:
graph
 a graph.numArcs
 the number of arcs in the graph (this parameter can be useful as someImmutableGraph
implementations do not supportImmutableGraph.numArcs()
).roundingMask
 a number of the form 2^{k} − 1. After each call toskipTo(long)
,currentIndex()
is guaranteed to return a multiple of 2^{k}, unlesscurrentIndex()
is equal to the number of nodes ingraph
.


Method Details

currentIndex
public int currentIndex()Returns the index realizing the last value returned byskipTo(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 byskipTo(long)
. Returns:
 the index of the node realizing the last value returned by
skipTo(long)
, or 1 ifskipTo(long)
has never been called.

skipTo
public 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. Parameters:
lowerBound
 a lower bound on the returned value. Returns:
 the first value of the cumulative function of outdegrees that is larger than or equal to
lowerBound
and that respect the rounding mask provided at construction time.
