Class EliasFanoCumulativeOutdegreeList

java.lang.Object
it.unimi.dsi.big.webgraph.algo.EliasFanoCumulativeOutdegreeList

public final class EliasFanoCumulativeOutdegreeList
extends Object

A content-addressable representation of the cumulative function of outdegrees that uses a stripped-down implementation of Elias–Fano's representation of monotone sequences partially taken from EliasFanoMonotoneLongBigList.

The purpose of this class is that of storing quasi-succinctly 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 high-degree nodes, and often in web graphs, due to crawling artifacts, these nodes are very close. As a result, a node-based 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 Details

    • EliasFanoCumulativeOutdegreeList

      public EliasFanoCumulativeOutdegreeList​(ImmutableGraph graph)
      Creates a cumulative outdegree list with no rounding mask.
      Parameters:
      graph - a graph.
    • EliasFanoCumulativeOutdegreeList

      public EliasFanoCumulativeOutdegreeList​(ImmutableGraph graph, long numArcs)
      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 some ImmutableGraph implementations do not support ImmutableGraph.numArcs()).
    • EliasFanoCumulativeOutdegreeList

      public EliasFanoCumulativeOutdegreeList​(ImmutableGraph graph, long numArcs, long roundingMask)
      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 some ImmutableGraph implementations do not support ImmutableGraph.numArcs()).
      roundingMask - a number of the form 2k − 1. After each call to skipTo(long), currentIndex() is guaranteed to return a multiple of 2k, unless currentIndex() is equal to the number of nodes in graph.
  • Method Details

    • currentIndex

      public 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).
      Returns:
      the index of the node realizing the last value returned by skipTo(long), or -1 if skipTo(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.