[
https://issues.apache.org/jira/browse/SPARK-23996?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16444909#comment-16444909
]
Miao Wang edited comment on SPARK-23996 at 4/19/18 10:34 PM:
-------------------------------------------------------------
[~timhunter] There is a Java implementation:
[https://github.com/DataSketches/sketches-core/tree/master/src/main/java/com/yahoo/sketches/kll]
I am reading the code now.
Is
[QuantileSummaries.scala|https://github.com/apache/spark/pull/15002/files#diff-48cfea2315f9ae39c33801873c4dbf84]
your implementation?
Thanks!
Miao
was (Author: wm624):
[~timhunter] There is a Java implementation:
[https://github.com/DataSketches/sketches-core/tree/master/src/main/java/com/yahoo/sketches/kll]
I am reading the code now.
Can you point me your spark implementation?
Thanks!
Miao
> 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
> Priority: Major
>
> 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-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
