Class HeavyKeeper<T>

java.lang.Object
org.infinispan.commons.stat.HeavyKeeper<T>
public class HeavyKeeper<T> 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.

This class is not designed for arbitrary extension. Subclassing is permitted solely to support serialization in modules that cannot access internal state through the public API.

Since:
16.3

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final record 
    HeavyKeeper.KeyFrequency<T>
    A key and its associated frequency count.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
     
    HeavyKeeper(int k, int width, int depth, double decay, ToLongBiFunction<T,Integer> hash)
    Creates a new HeavyKeeper tracker.
    protected
    HeavyKeeper(int k, int width, int depth, double decay, ToLongBiFunction<T,Integer> hash, long[][] fingerprints, long[][] counters, Map<T,Long> topItems)
    Reconstructs a HeavyKeeper from previously serialized state.

  • Method Summary

    Modifier and Type
    Method
    Description
    final T
    add(T key)
    Adds an item with a count of one.
    protected final long[][]
    counters()
    Returns the counter array.
    protected final long[][]
    fingerprints()
    Returns the sketch fingerprint array.
    final long
    getCount(T key)
    Returns the estimated count of an item.
    final double
    getDecay()
     
    final int
    getDepth()
     
    final int
    getK()
     
    final int
    getWidth()
     
    final T
    incrBy(T key, long increment)
    Increments the count of an item using HeavyKeeper insertion.
    final List<HeavyKeeper.KeyFrequency<T>>
    list()
    Returns the current top-k items sorted by count in descending order.
    final boolean
    query(T key)
    Checks whether an item is currently in the top-k.
    final void
    reset()
    Resets the tracker to its initial empty state, clearing both the sketch and the top-k map.
    protected final Map<T,Long>
    topItems()
    Returns the top-k map of items to their counts.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • HeavyKeeper

      public HeavyKeeper(int k, int width, int depth, double decay, ToLongBiFunction<T,Integer> hash)
      Creates a new HeavyKeeper tracker.
      Parameters:
      k - number of top items to track
      width - number of buckets per row in the sketch
      depth - number of rows in the sketch
      decay - decay constant for probabilistic aging, between 0 exclusive and 1 exclusive
      hash - hash function mapping (key, seed) to a long hash value

    • HeavyKeeper

      protected HeavyKeeper(int k, int width, int depth, double decay, ToLongBiFunction<T,Integer> hash, long[][] fingerprints, long[][] counters, Map<T,Long> topItems)
      Reconstructs a HeavyKeeper from previously serialized state.
      Parameters:
      k - number of top items to track
      width - number of buckets per row in the sketch
      depth - number of rows in the sketch
      decay - decay constant for probabilistic aging
      hash - hash function mapping (key, seed) to a long hash value
      fingerprints - the sketch fingerprint array, indexed by [depth][width]
      counters - the sketch counter array, indexed by [depth][width]
      topItems - the top-k entries mapping items to their counts

  • Method Details

    • add

      public final T add(T key)
      Adds an item with a count of one.
      Parameters:
      key - the item to add
      Returns:
      the displaced item if one was expelled from the top-k, or null

    • incrBy

      public final T incrBy(T key, 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:
      key - the item to increment
      increment - the amount to add
      Returns:
      the expelled item, or null if no item was expelled

    • getCount

      public final long getCount(T key)
      Returns the estimated count of an item. For items currently in the top-k, the count is exact from the moment of promotion onward.
      Parameters:
      key - the item to query
      Returns:
      the estimated count, or zero if the item has not been observed

    • query

      public final boolean query(T key)
      Checks whether an item is currently in the top-k.
      Parameters:
      key - the item to check
      Returns:
      true if the item is in the top-k

    • list

      public final List<HeavyKeeper.KeyFrequency<T>> list()
      Returns the current top-k items sorted by count in descending order.
      Returns:
      a list of key-frequency pairs, highest count first

    • reset

      public final void reset()
      Resets the tracker to its initial empty state, clearing both the sketch and the top-k map.

    • getK

      public final int getK()
      Returns:
      the number of top items tracked

    • getWidth

      public final int getWidth()
      Returns:
      the number of buckets per row in the sketch

    • getDepth

      public final int getDepth()
      Returns:
      the number of rows in the sketch

    • getDecay

      public final double getDecay()
      Returns:
      the decay constant for probabilistic aging

    • fingerprints

      protected final long[][] fingerprints()
      Returns the sketch fingerprint array. Intended for serialization in subclasses.
      Returns:
      the fingerprint array indexed by [depth][width]

    • counters

      protected final long[][] counters()
      Returns the counter array. Intended for serialization in subclasses.
      Returns:
      the counter array indexed by [depth][width]

    • topItems

      protected final Map<T,Long> topItems()
      Returns the top-k map of items to their counts. Intended for serialization in subclasses.
      Returns:
      the top-k map