%md

ScaDaMaLe Course [site](https://lamastex.github.io/scalable-data-science/sds/3/x/) and [book](https://lamastex.github.io/ScaDaMaLe/index.html)

%md

# Sketching with T-digest for quantiles

## A Toy Anomaly Detector

Fisher noticed the fundamental computational difference between mean, covariance, etc. and median, quantiles, in early 1900s.

The former ones are today called recursively computable statistics. When you take the memory footprint needed to keep these statistics updated then we get into the world of probabilistic datastructures...

The basic idea of sketching is formally conveyed in Chapter 6 of [Foundations of data Science](https://www.cs.cornell.edu/jeh/book.pdf).

Let's get a more informal view form the following sources.

%md

Here we focus on a specific sketch called **T-Digest** for approximating extreme quantiles:

**Pointers:**

- READ White Paper: [https://arxiv.org/pdf/1902.04023.pdf](https://arxiv.org/pdf/1902.04023.pdf)

- WATCH Spark/AI/Data Summit Talks: 

  - [https://databricks.com/session/sketching-data-with-t-digest-in-apache-spark](https://databricks.com/session/sketching-data-with-t-digest-in-apache-spark)

  - [https://databricks.com/session/one-pass-data-science-in-apache-spark-with-generative-t-digests](https://databricks.com/session/one-pass-data-science-in-apache-spark-with-generative-t-digests)

- GLANCE Blogs: 

  - [https://medium.com/@muppal/probabilistic-data-structures-in-the-big-data-world-code-b9387cff0c55](https://medium.com/@muppal/probabilistic-data-structures-in-the-big-data-world-code-b9387cff0c55)

  - [https://medium.com/@mani./t-digest-an-interesting-datastructure-to-estimate-quantiles-accurately-b99a50eaf4f7](https://medium.com/@mani./t-digest-an-interesting-datastructure-to-estimate-quantiles-accurately-b99a50eaf4f7)  

**NOTE:**

* Once you could see Ted Dunning's explanation of t-digest here: 

  - https://www.youtube.com/watch?v=B0dMc0t7K1g 

  - But, unfortunately, since 2020 this video has become a private property with this warning: *Private video Sign in if you've been granted access to this video*

%md

# Demonstration of t-digest to detect anomalous scores

%md

Let us import the following scala implementation of t-digest:

* for Spark 3.0.1 use maven coordinates: `org.isarnproject:isarn-sketches-spark_2.12:0.5.0-sp3.0`

See the library: [https://github.com/isarn/isarn-sketches-spark](https://github.com/isarn/isarn-sketches-spark)

%md

Here is a quick overview of the simple mixture of two Normal or Gaussian random variables we will be simulating from.

%md

Let's t-digest this `data` using a user-defined function `udf` evaluated below.