You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "zhuwenzhuang (via GitHub)" <gi...@apache.org> on 2023/05/30 06:33:36 UTC
[GitHub] [datasketches-java] zhuwenzhuang opened a new issue, #446: Sketches for Histogram and NDV
zhuwenzhuang opened a new issue, #446:
URL: https://github.com/apache/datasketches-java/issues/446
Hi, I found [HIVE-26221](https://issues.apache.org/jira/browse/HIVE-26221) uses the KLL float sketch as the histogram implementation. It works for range predicate selectivity. But float sketch cannot calculate NDV in an arbitrary range of rank.
Do we support any Sketches that can calculate any range's NDV?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] AlexanderSaydakov commented on issue #446: Sketches for Histogram and NDV
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1568873348
I don't think so
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on issue #446: Sketches for Histogram and NDV
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1601188435
I think this issue has been addressed. So I'm going to close this issue.
If you have any further questions you can reopen this issue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on issue #446: Sketches for Histogram and NDV
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1581773089
Here is another, but very crude solution. If you just want a very rough idea of what the NDVs are per bin, you could do this:
From the histogram information produced by the KLL sketch, you can compute the fractional density of each bin (fraction of total values including duplicates). Then with a parallel HLL sketch counting NDV of the entire stream you can compute the fractional number of duplicates in the stream. Finally, with the huge assumption that the duplicates are roughly uniformly distributed across the ranks, you can guess-timate the number of NDV in each bin.
(I put this in not just for its humor value, but this is almost exactly what political pollsters do!)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] zhuwenzhuang commented on issue #446: Sketches for Histogram and NDV
Posted by "zhuwenzhuang (via GitHub)" <gi...@apache.org>.
zhuwenzhuang commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1583818480
>
Thanks !
I'm trying
1. (first table scan) percentile_approx for bin's bound_array
2.(second table scan) array_lower_bound_index(bound_array, data_col) for data_col's bin id and data_col pair
3.(from on second step result) compute ndv,min,max,cnt for data_col group by bin id,
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] jmalkin commented on issue #446: Sketches for Histogram and NDV
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1568890200
Sketches are great for answering specific questions, but their size and speed benefits generally come at the cost of less flexibility to answer other questions.
KLL relies only on a comparator between elements. There's no consideration given to duplicates. The short answer is what @AlexanderSaydakov mentioned above.
One possible idea -- with a huge caveat that we can't say much about error bounds -- would be to have a tuple sketch containing the raw values in the tuple summary. You could query the KLL sketch to get the values associated with the rank range boundaries and then filter the the tuple summaries to be within the range. The number of retained values divided by theta would be _an_ estimate of distinct values within the range. But, again, any error bounds produced by the sketch would be misleading since we don't know what they'd be using an approximation of an approximation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho commented on issue #446: Sketches for Histogram and NDV
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #446:
URL: https://github.com/apache/datasketches-java/issues/446#issuecomment-1581761804
If your data is in Hive and you are willing to allow two passes on your data you could use KLL to establish the histogram boundaries you are interested in on the first pass, and then on the second pass feed an array of HLL sketches corresponding to the histogram ranges that would do distinct counts filtered for each range. This is a little clumsy, but would provide reliable accuracy bounds based on the HLL configuration. This avoids the kind of approximation of approximations issue @jmalkin mentioned.
Of course, the resulting histogram boundaries are also approximations, but at least you would have independent control of the accuracy of the boundaries and the accuracy of the NDV of each of the bins separately :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[GitHub] [datasketches-java] leerho closed issue #446: Sketches for Histogram and NDV
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho closed issue #446: Sketches for Histogram and NDV
URL: https://github.com/apache/datasketches-java/issues/446
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org