Class TopK

java.lang.Object
org.infinispan.server.resp.commands.topk.TopK
@ProtoTypeId(6162) public final class TopK extends Object
A Top-K implementation based on the HeavyKeeper algorithm.

HeavyKeeper is a probabilistic data structure that tracks the k most frequent items in a data stream. Each cell in the count array stores a fingerprint and a counter. During insertion, cells with matching fingerprints are incremented, while non-matching cells are probabilistically decayed with probability decay^counter, allowing frequent items (elephant flows) to persist while infrequent items (mouse flows) age out.

Since:
16.2

  • Field Details

  • Constructor Details

    • TopK

      public TopK(int k, int width, int depth, double decay)
      Creates a Top-K filter with specified parameters.
      Parameters:
      k - number of top items to track
      width - number of buckets per row
      depth - number of rows (hash functions)
      decay - decay constant for probabilistic aging

  • Method Details

    • getK

      @ProtoField(number=1, defaultValue="10") public int getK()

    • getWidth

      @ProtoField(number=2, defaultValue="8") public int getWidth()

    • getDepth

      @ProtoField(number=3, defaultValue="7") public int getDepth()

    • getDecay

      @ProtoField(number=4, defaultValue="0.9") public double getDecay()

    • getFlatCounters

      @ProtoField(number=5) public long[] getFlatCounters()

    • getEntries

      @ProtoField(number=6) public List<TopK.TopKEntry> getEntries()

    • getFlatFingerprints

      @ProtoField(number=7) public long[] getFlatFingerprints()

    • add

      public byte[] add(byte[] item)
      Adds an item to the Top-K. Returns the expelled item if one was removed.
      Parameters:
      item - the item to add
      Returns:
      the expelled item bytes, or null if no item was expelled

    • incrBy

      public byte[] incrBy(byte[] item, long increment)
      Increments the count of an item using HeavyKeeper insertion.

      For each CMS cell at the item's hash position:

      • If empty (counter=0): claim the cell with the item's fingerprint
      • If fingerprint matches: increment the counter
      • If fingerprint differs: with probability decay^counter, decrement; if counter reaches 0, replace with the new item's fingerprint
      Parameters:
      item - the item to increment
      increment - the amount to add
      Returns:
      the expelled item bytes, or null if no item was expelled

    • getCount

      public long getCount(byte[] item)
      Returns the estimated count of an item.

    • query

      public boolean query(byte[] item)
      Checks if an item is in the Top-K.

    • list

      public List<Object> list(boolean withCount)
      Returns the list of top-k items sorted by count descending.
      Parameters:
      withCount - if true, includes counts interleaved with items
      Returns:
      list of items (byte[]) and optionally counts (Long)