[
https://issues.apache.org/jira/browse/SPARK-55939?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Bo Xiong updated SPARK-55939:
-----------------------------
Description:
h3. Motivation
Spark SQL already provides built-in support for several Apache DataSketches
algorithms:
* HyperLogLog (HLL) sketches for approximate count distinct
* Theta sketches for count distinct with set operations (contributed by my
coworker)
* Tuple sketches for count distinct with aggregated summaries (contributed by
my coworker)
* KLL sketches for approximate quantiles
This request adds built-in support for the *DataSketches ItemsSketch* (Frequent
Items), which tracks the approximate frequency of items in a data stream. It
provides the following features:
* Frequency estimates for any item (not just the top-K)
* Configurable error guarantees ({{{}NO_FALSE_POSITIVES{}}} vs
{{{}NO_FALSE_NEGATIVES{}}})
* Mergeable binary representations for multi-level rollup aggregation
h3. Use Cases
* {*}Frequency estimation in streaming{*}: Maintain running frequency sketches
that can be merged across micro-batches.
* {*}Multi-dimensional rollup{*}: Build sketches at child-level dimensions and
merge up to parent dimensions.
was:
h3. Motivation
Spark SQL already provides built-in support for several Apache DataSketches
algorithms:
* HyperLogLog (HLL) sketches for approximate count distinct
* Theta sketches for count distinct with set operations
* Tuple sketches for count distinct with aggregated summaries
* KLL sketches for approximate quantiles
* Top-K sketches for approximate top-K items
This PR adds built-in support for the *DataSketches ItemsSketch* (Frequent
Items), which tracks the approximate frequency of items in a data stream.
Unlike {{approx_top_k}} which only returns the top-K items, ItemsSketch
provides:
* Frequency estimates for any item (not just the top-K)
* Configurable error guarantees ({{{}NO_FALSE_POSITIVES{}}} vs
{{{}NO_FALSE_NEGATIVES{}}})
* Mergeable binary representations for multi-level rollup aggregation
* Support for a wide range of data types (boolean, numeric, string, decimal,
date, timestamp)
h3. Use Cases
* {*}Finding top sellers across time horizons{*}: Build daily per-category
sketches, then merge across days to find weekly/monthly top sellers without
re-scanning raw data.
* {*}Frequency estimation in streaming{*}: Maintain running frequency sketches
that can be merged across micro-batches.
* {*}Multi-dimensional rollup{*}: Build sketches at child-level dimensions and
merge up to parent dimensions.
> Add built-in DataSketches ItemsSketch (Frequent Items) functions to Spark SQL
> -----------------------------------------------------------------------------
>
> Key: SPARK-55939
> URL: https://issues.apache.org/jira/browse/SPARK-55939
> Project: Spark
> Issue Type: New Feature
> Components: SQL
> Affects Versions: 4.2.0
> Reporter: Bo Xiong
> Assignee: Bo Xiong
> Priority: Major
> Labels: sketch,most-frequent,top-k
> Fix For: 4.2.0
>
> Original Estimate: 4h
> Remaining Estimate: 4h
>
> h3. Motivation
> Spark SQL already provides built-in support for several Apache DataSketches
> algorithms:
> * HyperLogLog (HLL) sketches for approximate count distinct
> * Theta sketches for count distinct with set operations (contributed by my
> coworker)
> * Tuple sketches for count distinct with aggregated summaries (contributed
> by my coworker)
> * KLL sketches for approximate quantiles
> This request adds built-in support for the *DataSketches ItemsSketch*
> (Frequent Items), which tracks the approximate frequency of items in a data
> stream. It provides the following features:
> * Frequency estimates for any item (not just the top-K)
> * Configurable error guarantees ({{{}NO_FALSE_POSITIVES{}}} vs
> {{{}NO_FALSE_NEGATIVES{}}})
> * Mergeable binary representations for multi-level rollup aggregation
> h3. Use Cases
> * {*}Frequency estimation in streaming{*}: Maintain running frequency
> sketches that can be merged across micro-batches.
> * {*}Multi-dimensional rollup{*}: Build sketches at child-level dimensions
> and merge up to parent dimensions.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
