[GitHub] [incubator-druid] leerho commented on issue #7444: Are there documentation on the limitation of intersection using theta sketch?

[GitBox <gi...@apache.org>]

leerho commented on issue #7444: Are there documentation on the limitation of intersection using theta sketch?
URL: https://github.com/apache/incubator-druid/issues/7444#issuecomment-482247719
 
 
   Refer to documentation [here](https://datasketches.github.io/docs/Theta/ThetaSketchSetOps.html) and [here](https://datasketches.github.io/docs/Theta/ThetaAccuracyPlots.html).
   
   When you print the results via toString() you should be able to see the 95% confidence upper and lower bounds from the sketch itself.  What the sketch is telling you is that given the configuration of your sketches and the cardinalities of your input streams, the "true" answer should be within those bounds with 95% confidence.  And theoretically this is the best you can do given the above.
   
   Theta sketches retain only a small sample of the input streams that that they see.  When you perform an intersection it reduces that small sample to an even smaller set, possibly zero!  And as you might guess, extracting useful information about your input streams with zero samples is rather difficult:
   
   ![We_do_sketches](https://user-images.githubusercontent.com/12941506/55978742-66e08600-5c45-11e9-9721-e746dafc7e87.png)
   
   Successive intersections will quickly reduce your number of samples available to estimate from and thus will dramatically increase the error.  Also attempting to intersect one sketch from a large cardinality set with another sketch from a very small cardinality set will also increase your error (see the 2nd link above).  
   
   **So what can you do?**
   
   - Organize your intersections (and AnotB ops) to be performed as the very last step.  For example,
   instead of `AU(B^C)` use `(AUB)^(AUC)`. This keeps the internal sample set as large as possible until the very end.
   - If you know which streams have large cardinality, use large sketches for these sketches. Internally we use sketches of 2^20 for our large cardinality streams (there is generally only a few of them) and then 2^14 for everything else.
   - Always query the resulting sketch from a set expression to obtain the upper and lower bounds.   This will tell you right away what your error confidence interval is.
   
   
   

----------------------------------------------------------------
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.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org