org.apache.solr.util.hll

## Class HLL

- java.lang.Object
- - org.apache.solr.util.hll.HLL

- All Implemented Interfaces:
    Cloneable

      public class HLL
      extends Object
      implements Cloneable

  A probabilistic set of hashed `long` elements. Useful for computing the approximate cardinality of a stream of data in very small storage. A modified version of the 'HyperLogLog' data structure and algorithm is used, which combines both probabilistic and non-probabilistic techniques to improve the accuracy and storage requirements of the original algorithm. More specifically, initializing and storing a new `HLL` will allocate a sentinel value symbolizing the empty set (`HLLType.EMPTY`). After adding the first few values, a sorted list of unique integers is stored in a `HLLType.EXPLICIT` hash set. When configured, accuracy can be sacrificed for memory footprint: the values in the sorted list are "promoted" to a "`HLLType.SPARSE`" map-based HyperLogLog structure. Finally, when enough registers are set, the map-based HLL will be converted to a bit-packed "`HLLType.FULL`" HyperLogLog structure. This data structure is interoperable with the implementations found at:
  - postgresql-hll, and
  - js-hll
  when properly serialized.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static int` | `MAXIMUM_EXPLICIT_THRESHOLD`
    `static int` | `MAXIMUM_EXPTHRESH_PARAM`
    `static int` | `MAXIMUM_LOG2M_PARAM`
    `static int` | `MAXIMUM_REGWIDTH_PARAM`
    `static int` | `MINIMUM_EXPTHRESH_PARAM`
    `static int` | `MINIMUM_LOG2M_PARAM`
    `static int` | `MINIMUM_REGWIDTH_PARAM`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `HLL(int log2m, int regwidth)` Construct an empty HLL with the given `log2m` and `regwidth`.
    `HLL(int log2m, int regwidth, int expthresh, boolean sparseon, HLLType type)` NOTE: Arguments here are named and structured identically to those in the PostgreSQL implementation, which can be found here.

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addRaw(long rawValue)` Adds `rawValue` directly to the HLL.
    `long` | `cardinality()` Computes the cardinality of the HLL.
    `void` | `clear()` Clears the HLL.
    `HLL` | `clone()` Create a deep copy of this HLL.
    `static HLL` | `fromBytes(byte[] bytes)` Deserializes the HLL (in `toBytes(ISchemaVersion)` format) serialized into `bytes`.
    `HLLType` | `getType()`
    `byte[]` | `toBytes()` Serializes the HLL to an array of bytes in correspondence with the format of the default schema version, `SerializationUtil.DEFAULT_SCHEMA_VERSION`.
    `byte[]` | `toBytes(ISchemaVersion schemaVersion)` Serializes the HLL to an array of bytes in correspondence with the format of the specified schema version.
    `void` | `union(HLL other)` Computes the union of HLLs and stores the result in this instance.

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### MINIMUM_LOG2M_PARAM

          public static final int MINIMUM_LOG2M_PARAM

      See Also:
        Constant Field Values

    - #### MAXIMUM_LOG2M_PARAM

          public static final int MAXIMUM_LOG2M_PARAM

      See Also:
        Constant Field Values

    - #### MINIMUM_REGWIDTH_PARAM

          public static final int MINIMUM_REGWIDTH_PARAM

      See Also:
        Constant Field Values

    - #### MAXIMUM_REGWIDTH_PARAM

          public static final int MAXIMUM_REGWIDTH_PARAM

      See Also:
        Constant Field Values

    - #### MINIMUM_EXPTHRESH_PARAM

          public static final int MINIMUM_EXPTHRESH_PARAM

      See Also:
        Constant Field Values

    - #### MAXIMUM_EXPTHRESH_PARAM

          public static final int MAXIMUM_EXPTHRESH_PARAM

      See Also:
        Constant Field Values

    - #### MAXIMUM_EXPLICIT_THRESHOLD

          public static final int MAXIMUM_EXPLICIT_THRESHOLD

      See Also:
        Constant Field Values

  - ### Constructor Detail

    - #### HLL

          public HLL(int log2m,
                     int regwidth,
                     int expthresh,
                     boolean sparseon,
                     HLLType type)

      NOTE: Arguments here are named and structured identically to those in the PostgreSQL implementation, which can be found here.
      Parameters:
        `log2m` - log-base-2 of the number of registers used in the HyperLogLog algorithm. Must be at least 4 and at most 30.
        `regwidth` - number of bits used per register in the HyperLogLog algorithm. Must be at least 1 and at most 8.
        `expthresh` - tunes when the `HLLType.EXPLICIT` to `HLLType.SPARSE` promotion occurs, based on the set's cardinality. Must be at least -1 and at most 18.
        `sparseon` - Flag indicating if the `HLLType.SPARSE` representation should be used.
        `type` - the type in the promotion hierarchy which this instance should start at. This cannot be `null`.

    - #### HLL

          public HLL(int log2m,
                     int regwidth)

      Construct an empty HLL with the given `log2m` and `regwidth`. This is equivalent to calling `HLL(log2m, regwidth, -1, true, HLLType.EMPTY)`.
      Parameters:
        `log2m` - log-base-2 of the number of registers used in the HyperLogLog algorithm. Must be at least 4 and at most 30.
        `regwidth` - number of bits used per register in the HyperLogLog algorithm. Must be at least 1 and at most 8.
      See Also:
        `HLL(int, int, int, boolean, HLLType)`

  - ### Method Detail

    - #### getType

          public HLLType getType()

      Returns:
        the type in the promotion hierarchy of this instance. This will never be `null`.

    - #### addRaw

          public void addRaw(long rawValue)

      Adds `rawValue` directly to the HLL.
      Parameters:
        `rawValue` - the value to be added. It is very important that this value already be hashed with a strong (but not necessarily cryptographic) hash function. For instance, the Murmur3 implementation in Google's Guava library is an excellent hash function for this purpose and, for seeds greater than zero, matches the output of the hash provided in the PostgreSQL implementation.

    - #### cardinality

          public long cardinality()

      Computes the cardinality of the HLL.
      Returns:
        the cardinality of HLL. This will never be negative.

    - #### clear

          public void clear()

      Clears the HLL. The HLL will have cardinality zero and will act as if no elements have been added. NOTE: Unlike `addRaw(long)`, `clear` does NOT handle transitions between `HLLType`s - a probabilistic type will remain probabilistic after being cleared.

    - #### union

          public void union(HLL other)

      Computes the union of HLLs and stores the result in this instance.
      Parameters:
        `other` - the other `HLL` instance to union into this one. This cannot be `null`.

    - #### toBytes

          public byte[] toBytes()

      Serializes the HLL to an array of bytes in correspondence with the format of the default schema version, `SerializationUtil.DEFAULT_SCHEMA_VERSION`.
      Returns:
        the array of bytes representing the HLL. This will never be `null` or empty.

    - #### toBytes

          public byte[] toBytes(ISchemaVersion schemaVersion)

      Serializes the HLL to an array of bytes in correspondence with the format of the specified schema version.
      Parameters:
        `schemaVersion` - the schema version dictating the serialization format
      Returns:
        the array of bytes representing the HLL. This will never be `null` or empty.

    - #### fromBytes

          public static HLL fromBytes(byte[] bytes)

      Deserializes the HLL (in `toBytes(ISchemaVersion)` format) serialized into `bytes`.
      Parameters:
        `bytes` - the serialized bytes of new HLL
      Returns:
        the deserialized HLL. This will never be `null`.
      See Also:
        `toBytes(ISchemaVersion)`

    - #### clone

          public HLL clone()
                    throws CloneNotSupportedException

      Create a deep copy of this HLL.
      Overrides:
        `clone` in class `Object`
      Throws:
        `CloneNotSupportedException`
      See Also:
        `Object.clone()`

Copyright © 2000-2016 Apache Software Foundation. All Rights Reserved.