Module roaringbitmap
Package org.roaringbitmap

Class SuccinctRank

java.lang.Object
org.roaringbitmap.SuccinctRank
public class SuccinctRank extends Object
Succinct rank structure for RoaringBitmap providing O(1) rank queries.

A succinct data structure is one that uses space close to the information-theoretic minimum while still supporting efficient queries. Unlike auxiliary data structures that require O(n) extra space, succinct structures achieve o(n) (sub-linear) overhead. This implementation stores only small cumulative rank samples per container, enabling fast rank queries without duplicating the underlying bitmap data.

Rank(x) returns the count of elements less than or equal to x in the bitmap, matching the semantics of RoaringBitmap.rankLong(int).

How it works:

  • Pre-computes cumulative cardinalities per container at build time
  • For large bitmaps (>16 containers): uses a two-level index with high-bit lookup tables for O(1) container location
  • For small bitmaps: uses linear scan over containers
  • For BitmapContainers: stores packed cumulative ranks per 256-bit superblock

When to use:

  • Memory-constrained environments needing fast rank queries
  • Read-heavy workloads on immutable bitmaps
  • When you need both rank queries and the original bitmap

Trade-offs vs FastRankRoaringBitmap:

  • Lower memory overhead
  • Comparable rank performance
  • Immutable (rebuild required if bitmap changes)
Since:
Dec-2025
See Also:

  • Method Details

    • build

      public static SuccinctRank build(RoaringBitmap source)
      Builds a rank structure for the given bitmap. WARNING: Does not clone the bitmap - assumes it will not be modified.
      Parameters:
      source - the source bitmap
      Returns:
      a rank structure

    • rank

      public long rank(int x)
      Returns the number of integers invalid input: '<'= x.
      Parameters:
      x - upper limit
      Returns:
      the rank

    • cardinality

      public long cardinality()
      Returns the number of distinct integers added to the bitmap (e.g., number of bits set).
      Returns:
      the cardinality

    • getUnderlyingBitmap

      public RoaringBitmap getUnderlyingBitmap()
      Returns a reference to the underlying RoaringBitmap used by this SuccinctRank.

      Note: This does not return a copy. Modifications to the returned bitmap may affect the state of this SuccinctRank instance.

      Returns:
      the underlying RoaringBitmap instance

    • usesLinearScan

      public boolean usesLinearScan()
      Returns true if this rank structure uses a linear scan for rank queries, which occurs when the bitmap contains <= 16 containers. In this case, rank queries are performed by scanning each container sequentially, which is efficient for small bitmaps but less performant for larger ones.

      For bitmaps with more than 16 containers, a succinct rank structure is used, enabling faster rank queries via precomputed data structures at the cost of additional memory usage.

      The choice between linear scan and succinct structure impacts both query performance and memory footprint.

      Returns:
      true if linear scan is used; false if succinct structure is used

    • containerCount

      public int containerCount()
      Returns the number of containers in the bitmap.
      Returns:
      the number of containers