Class FastAggregation

java.lang.Object
org.roaringbitmap.FastAggregation

public final class FastAggregation extends Object
Fast algorithms to aggregate many bitmaps.
Author:
Daniel Lemire
  • Method Details

    • and

      public static RoaringBitmap and(Iterator<? extends RoaringBitmap> bitmaps)
      Compute the AND aggregate. In practice, calls {#link naive_and}
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • and

      public static RoaringBitmap and(RoaringBitmap... bitmaps)
      Compute the AND aggregate.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • and

      public static RoaringBitmap and(long[] aggregationBuffer, RoaringBitmap... bitmaps)
      Compute the AND aggregate.
      Parameters:
      aggregationBuffer - a buffer for aggregation
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • andCardinality

      public static int andCardinality(RoaringBitmap... bitmaps)
      Compute cardinality of the AND aggregate.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated cardinality
    • orCardinality

      public static int orCardinality(RoaringBitmap... bitmaps)
      Compute cardinality of the OR aggregate.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated cardinality
    • horizontal_or

      @Deprecated public static RoaringBitmap horizontal_or(Iterator<? extends RoaringBitmap> bitmaps)
      Deprecated.
      Calls naive_or.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • horizontal_or

      public static RoaringBitmap horizontal_or(List<? extends RoaringBitmap> bitmaps)
      Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • horizontal_or

      public static RoaringBitmap horizontal_or(RoaringBitmap... bitmaps)
      Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • horizontal_xor

      public static RoaringBitmap horizontal_xor(RoaringBitmap... bitmaps)
      Minimizes memory usage while computing the xor aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • naive_and

      public static RoaringBitmap naive_and(Iterator<? extends RoaringBitmap> bitmaps)
      Compute overall AND between bitmaps two-by-two. Performance hint: if you have very large and tiny bitmaps, it may be beneficial performance-wise to put a tiny bitmap in first position. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • naive_and

      public static RoaringBitmap naive_and(RoaringBitmap... bitmaps)
      Compute overall AND between bitmaps two-by-two. Performance hint: if you have very large and tiny bitmaps, it may be beneficial performance-wise to put a tiny bitmap in first position. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • workShyAnd

      public static RoaringBitmap workShyAnd(long[] buffer, RoaringBitmap... bitmaps)
      Computes the intersection by first intersecting the keys, avoids materialising containers.
      Parameters:
      buffer - an 8KB buffer
      bitmaps - the inputs
      Returns:
      the intersection of the bitmaps
    • workAndMemoryShyAnd

      public static RoaringBitmap workAndMemoryShyAnd(long[] buffer, RoaringBitmap... bitmaps)
      Computes the intersection by first intersecting the keys, avoids materialising containers, limits memory usage. You must provide a long[] array of length at least 1024, initialized with zeroes. We do not check whether the array is initialized with zeros: it is the caller's responsability. You should expect this function to be slower than workShyAnd and the reduction in memory usage might be small.
      Parameters:
      buffer - should be a 1024-long array
      bitmaps - the inputs
      Returns:
      the intersection of the bitmaps
    • naive_or

      public static RoaringBitmap naive_or(Iterator<? extends RoaringBitmap> bitmaps)
      Compute overall OR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • naive_or

      public static RoaringBitmap naive_or(RoaringBitmap... bitmaps)
      Compute overall OR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • naive_xor

      public static RoaringBitmap naive_xor(Iterator<? extends RoaringBitmap> bitmaps)
      Compute overall XOR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • naive_xor

      public static RoaringBitmap naive_xor(RoaringBitmap... bitmaps)
      Compute overall XOR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • or

      public static RoaringBitmap or(Iterator<? extends RoaringBitmap> bitmaps)
      Compute overall OR between bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • or

      public static RoaringBitmap or(RoaringBitmap... bitmaps)
      Compute overall OR between bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • priorityqueue_or

      public static RoaringBitmap priorityqueue_or(Iterator<? extends RoaringBitmap> bitmaps)
      Uses a priority queue to compute the or aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • priorityqueue_or

      public static RoaringBitmap priorityqueue_or(RoaringBitmap... bitmaps)
      Uses a priority queue to compute the or aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • priorityqueue_xor

      public static RoaringBitmap priorityqueue_xor(RoaringBitmap... bitmaps)
      Uses a priority queue to compute the xor aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
      See Also:
    • xor

      public static RoaringBitmap xor(Iterator<? extends RoaringBitmap> bitmaps)
      Compute overall XOR between bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap
    • xor

      public static RoaringBitmap xor(RoaringBitmap... bitmaps)
      Compute overall XOR between bitmaps.
      Parameters:
      bitmaps - input bitmaps
      Returns:
      aggregated bitmap