spark-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Timothy Hunter (JIRA)" <j...@apache.org>
Subject [jira] [Created] (SPARK-23996) Implement the optimal KLL algorithms for quantiles in streams
Date Mon, 16 Apr 2018 19:23:00 GMT
Timothy Hunter created SPARK-23996:
--------------------------------------

             Summary: Implement the optimal KLL algorithms for quantiles in streams
                 Key: SPARK-23996
                 URL: https://issues.apache.org/jira/browse/SPARK-23996
             Project: Spark
          Issue Type: Improvement
          Components: MLlib, SQL
    Affects Versions: 2.3.0
            Reporter: Timothy Hunter


The current implementation for approximate quantiles - a variant of Grunwald-Khanna, which
I implemented - is not the best in light of recent papers:

 - it is not exactly the one from the paper for performance reasons, but the changes are
not documented beyond comments on the code

 - there are now more optimal algorithms with proven bounds (unlike q-digest, the other contender
at the time)

I propose that we revisit the current implementation and look at the Karnin-Lang-Liberty algorithm
(KLL) for example:
[https://arxiv.org/abs/1603.05346]

[https://edoliberty.github.io//papers/streamingQuantiles.pdf]

This algorithm seems to have favorable characteristics for streaming and a distributed implementation,
and there is a python implementation for reference.

It is a fairly standalone piece, and in that respect available to people who don't know too
much about spark internals.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org


Mime
View raw message