[ https://issues.apache.org/jira/browse/SPARK-21184?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16060741#comment-16060741 ]
Sean Owen commented on SPARK-21184: ----------------------------------- [~timhunter] [~clockfly] do you have opinions on this? Probably best to first make sure the implementation works. Then if there's a variation that's better, move to that if possible. I don't think we'd reimplement completely. > QuantileSummaries implementation is wrong and QuantileSummariesSuite fails > with larger n > ---------------------------------------------------------------------------------------- > > Key: SPARK-21184 > URL: https://issues.apache.org/jira/browse/SPARK-21184 > Project: Spark > Issue Type: Bug > Components: SQL > Affects Versions: 2.1.1 > Reporter: Andrew Ray > > 1. QuantileSummaries implementation does not match the paper it is supposed > to be based on. > 1a. The compress method > (https://github.com/apache/spark/blob/master/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/util/QuantileSummaries.scala#L240) > merges neighboring buckets, but thats not what the paper says to do. The > paper > (http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf) > describes an implicit tree structure and the compress method deletes selected > subtrees. > 1b. The paper does not discuss merging these summary data structures at all. > The following comment is in the merge method of QuantileSummaries: > {quote} // The GK algorithm is a bit unclear about it, but it seems > there is no need to adjust the > // statistics during the merging: the invariants are still respected > after the merge.{quote} > Unless I'm missing something that needs substantiation, it's not clear that > that the invariants hold. > 2. QuantileSummariesSuite fails with n = 10000 (and other non trivial values) > https://github.com/apache/spark/blob/master/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/util/QuantileSummariesSuite.scala#L27 > One possible solution if these issues can't be resolved would be to move to > an algorithm that explicitly supports merging and is well tested like > https://github.com/tdunning/t-digest -- This message was sent by Atlassian JIRA (v6.4.14#64029) --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org