Package dev.frostlake.functions.aggregate

Class TopKSummary

java.lang.Object
dev.frostlake.functions.aggregate.TopKSummary
public class TopKSummary extends Object
The Space-Saving summary behind the APPROX_TOP_K family: a bounded set of (value, count) counters that names the most frequent values of a stream without holding every distinct one.

The rules, all live-verified:

  • a value already counted increments its counter;
  • a new value arriving while the summary is full takes over the counter with the SMALLEST count (the least recently touched one among equals) and inherits that count plus one — so APPROX_TOP_K(n, 2, 1) over four values reports the last one with count 4, and seven cycling values over four counters all end at 25 after a hundred rows;
  • the summary lists by count descending and, among equal counts, the most recently touched value first;
  • a merge (APPROX_TOP_K_COMBINE) adds the counts of equal values with no inheritance and then drops, from the smallest count upward and the most recently touched first, until the summary fits its capacity again.

The serialised state is {"counters":C,"datatype":T,"precision":P,"scale":S,"state":[[value, count], …],"type":"approx_top_k"}, its pairs in the listing order above; reading one back keeps that order as the recency order, so an estimate over a state ranks as the state was written.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEFAULT_COUNTERS
    The default number of counters — the largest a call may ask for, too.
    static final int
    DEFAULT_PRECISION
    The width a state reports for every non-numeric input, and for an empty one.
    static final String
    MISSING_DATATYPE
    The datatype of a state that has seen no value.
    static final String
    STATE_TYPE
    The type member a state carries.

  • Constructor Summary

    Constructors
    Constructor
    Description
    TopKSummary(int capacity)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    absorb(tools.jackson.databind.JsonNode state)
    Reads a state's pairs into this summary as a merge, last pair first, so that the state's own listing order (most recently touched first) is what the clock records.
    void
    add(Object value)
    Counts one occurrence of a value, taking over the least counter when the summary is full.
    int
    capacity()
     
    static int
    countersOf(tools.jackson.databind.JsonNode state)
    The counters member of a state, or the default when it carries none.
    void
    fit(int limit)
    Drops counters until at most limit remain: the smallest count first, the most recently touched among equals.
    boolean
    isEmpty()
     
    void
    merge(Object value, long count)
    Adds a whole counter, as a merge does: an equal value adds its count, a new one is admitted whatever the capacity — fit(int) trims afterwards.
    static VariantValue
    pairsOf(List<TopKCounter> ranked)
    The [value, count] pairs of some counters as an ARRAY value.
    List<TopKCounter>
    ranked()
    The counters ranked: count descending, then the most recently touched first.
    int
    size()
     
    static tools.jackson.databind.JsonNode
    stateNode(Object value)
    A state as an object node, or the refusal live gives an argument that is not one.
    static VariantValue
    stateOf(int counters, String datatype, int precision, int scale, List<TopKCounter> ranked)
    The serialised state of a summary.
    List<TopKCounter>
    top(int items)
    The first items of ranked().

    Methods inherited from class java.lang.Object

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

  • Field Details

    • DEFAULT_COUNTERS

      public static final int DEFAULT_COUNTERS
      The default number of counters — the largest a call may ask for, too.
      See Also:

    • STATE_TYPE

      public static final String STATE_TYPE
      The type member a state carries.
      See Also:

    • MISSING_DATATYPE

      public static final String MISSING_DATATYPE
      The datatype of a state that has seen no value.
      See Also:

    • DEFAULT_PRECISION

      public static final int DEFAULT_PRECISION
      The width a state reports for every non-numeric input, and for an empty one.
      See Also:

  • Constructor Details

    • TopKSummary

      public TopKSummary(int capacity)

  • Method Details

    • capacity

      public int capacity()

    • isEmpty

      public boolean isEmpty()

    • size

      public int size()

    • add

      public void add(Object value)
      Counts one occurrence of a value, taking over the least counter when the summary is full.

    • merge

      public void merge(Object value, long count)
      Adds a whole counter, as a merge does: an equal value adds its count, a new one is admitted whatever the capacity — fit(int) trims afterwards.

    • fit

      public void fit(int limit)
      Drops counters until at most limit remain: the smallest count first, the most recently touched among equals.

    • ranked

      public List<TopKCounter> ranked()
      The counters ranked: count descending, then the most recently touched first.

    • top

      public List<TopKCounter> top(int items)
      The first items of ranked().

    • pairsOf

      public static VariantValue pairsOf(List<TopKCounter> ranked)
      The [value, count] pairs of some counters as an ARRAY value.

    • stateOf

      public static VariantValue stateOf(int counters, String datatype, int precision, int scale, List<TopKCounter> ranked)
      The serialised state of a summary.
      Parameters:
      counters - the counters member
      datatype - the input's type in the catalog's internal vocabulary (FIXED, TEXT, REAL, …)
      precision - the precision member
      scale - the scale member
      ranked - the counters to list, in listing order
      Returns:
      the OBJECT value

    • stateNode

      public static tools.jackson.databind.JsonNode stateNode(Object value)
      A state as an object node, or the refusal live gives an argument that is not one.
      Parameters:
      value - the argument
      Returns:
      the state's node

    • absorb

      public void absorb(tools.jackson.databind.JsonNode state)
      Reads a state's pairs into this summary as a merge, last pair first, so that the state's own listing order (most recently touched first) is what the clock records.

    • countersOf

      public static int countersOf(tools.jackson.databind.JsonNode state)
      The counters member of a state, or the default when it carries none.