Download as PDF, PPTX
Uploaded bySimon Belak
Online statistical analysis using transducers and sketch algorithms
The document discusses online statistical analysis using transducers and sketch algorithms, highlighting their effectiveness in handling large datasets through modularization and performance optimization. It covers various statistical methods and techniques, including histograms and distributions, and emphasizes that approximations can often be sufficient. Key takeaways include the usefulness of transducers for efficiency and the importance of having readily available distributions for data analysis.
Online statistical analysis using transducers and sketch algorithms
- 1. Online statistical analysis usingtransducers and sketch algorithms simon@metabase.com @sbelak
- 2. Metabase ❤ github.com/metabase/metabase • Opensource analytics tool • Building a “data scientist in a box” • Hundreds to billions of rows • Some DBs optimised for analytics, some not
- 3. Transducers at aglance • Transducers decomplect recursion mechanism, transformation, building the output, and access mechanism • 3 user-facing “protocols”: xf, transdcucer, and CollReduce
- 4.
- 5. Composing transducers 1. compxfs 2. xf and transducer 3. github.com/henrygarner/redux post-complete fuse
- 6.
- 7. Many batch algorithmscan be turned into online ones Parallelize independent computations Find a recursive relation
- 8. github.com/MastodonC/kixi.stats • Count • (Arithmetic)mean • Geometric mean • Harmonic mean • Median • Variance • Interquartile range • Standard deviation • Standard error • Skewness • Kurtosis • Covariance • Covariance matrix • Correlation • Correlation matrix • Simple linear regression • Standard error of the mean • Standard error of the estimate • Standard error of the prediction • …
- 9.
- 10. Using transducers is worthit for the composition alone
- 11. Annoyances • Can onlytransduce one coll at a time • Always have to pass in an xf • Having functions that return a transducer or not is error prone
- 12.
- 13. Idea: summarise your datawith some data structure and query that
- 14.
- 15. Histogram construction 1. Picka number of buckets K 2. For each incoming value: 1. If a bucket for it exists, increment it 2. else, add a new bucket with count = 1 3. If there are > K buckets, find the two most adjacent buckets and merge them
- 16.
- 17. Estimating values • Assumethe bin mean in also its median • Do weighted interpolations • Often we can be precise up to the two bounding buckets
- 18. Nice property II: decouples data collection from computation
- 19.
- 20. Aside: transducers area good way to wrap Java/ imperative construction
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28. Takeouts • Transducers arenot only performant but also a good modularization protocol • You don’t realise how often you want a distribution until you have it readily available • Often approximations are good enough • You can get surprisingly far on a single machine
- 29.