KHyperLogLog Functions¶

Presto implements the KHyperLogLog algorithm and data structure. KHyperLogLog data structure can be created through khyperloglog_agg().

Data Structures¶

KHyperLogLog is a data sketch that compactly represents the association of two columns. It is implemented in Presto as a two-level data structure composed of a MinHash structure whose entries map to HyperLogLog.

Serialization¶

KHyperLogLog sketches can be cast to and from varbinary. This allows them to be stored for later use.

Functions¶

khyperloglog_agg(x, y) -> KHyperLogLog()¶

Returns the KHyperLogLog sketch that represents the relationship between columns x and y. The MinHash structure summarizes x and the HyperLogLog sketches represent y values linked to x values.

cardinality(khll) -> bigint()

This calculates the cardinality of the MinHash sketch, i.e. x’s cardinality.

intersection_cardinality(khll1, khll2) ->  bigint()¶

Returns the set intersection cardinality of the data represented by the MinHash structures of khll1 and khll2.

jaccard_index(khll1, khll2) ->  double()¶

Returns the Jaccard index of the data represented by the MinHash structures of khll1 and khll2.

uniqueness_distribution(khll) ->  map<bigint,double>()¶

For a certain value x', uniqueness is understood as how many y' values are associated with it in the source dataset. This is obtained with the cardinality of the HyperLogLog that is mapped from the MinHash bucket that corresponds to x'. This function returns a histogram that represents the uniqueness distribution, the X-axis being the uniqueness and the Y-axis being the relative frequency of x values.

uniqueness_distribution(khll, histogramSize) ->  map<bigint,double>()¶

Returns the uniqueness histogram with the given amount of buckets. If omitted, the value defaults to 256. All uniqueness values greater than histogramSize are accumulated in the last bucket.

reidentification_potential(khll, threshold) ->  double()¶

The reidentification potential is the ratio of x values that have a uniqueness under the given threshold.

merge(khll) -> KHyperLogLog()

Returns the KHyperLogLog of the aggregate union of the individual KHyperLogLog structures.

merge_khll(array(khll)) -> KHyperLogLog()¶

Returns the KHyperLogLog of the union of an array of KHyperLogLog structures.