Class EliasFanoCumulativeOutdegreeList


  • public final class EliasFanoCumulativeOutdegreeList
    extends java.lang.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.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • 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,
                                                int 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 Detail

      • currentIndex

        public int 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.