Centroid

但是這樣要知道 500 個數字的順序才能計算，這在數字非常多的時候是不容易的。取而代之的是，試著將用很少的數字來代替 500個數字，怎麼做呢？

將鄰近的數字們用兩個數字代表： 平均值跟個數 原始的論文中是用總和，但是兩者意義相同，實作上為了效率都會選用平均值。

這樣的一組平均值跟個數被稱為 Centroid ，我們可以用好幾個 centroid 來代替整個 PDF, T-Digest 就是在做這件事。

當然可以自由決定要用幾個 centroid 來代表

計算百分位數時就是只需要從這些 centroids 中找出對應位置的項目來做內插法。

Clustering

將很多數字用一個或多個 centroids 代表的動作稱為 clustering. 我們知道當一個 centroid 代表的數字越多，流失的資訊也就越多，也就越不精確，因此怎麼 clustering 就是影響成效的一個重點。

T-Digest 的作法是控制各個 centroid 的大小，在需要精確的部份用更多 centroids 來表達。為此論文提出了一個公式⊕ 來定義這個行為：

k(q, δ) = δ\left(\frac{sin^{-1}(2q - 1)}{π} + \frac{1}{2}\right)

其中 q 是 quantile, δ 是壓縮率參數，而 k(q, δ) 表示 q 應該要用第幾個 centroid 表達。可以從圖中看到在靠近 q = 0 跟 q = 1 的時候，k 的變動很大，也就是說我們用比較多的 centroids 來表示。 為什麼這樣設計呢？

這是因為大部分計算百分位數時，真正關心的通常是 1、0.1、99、99.9、99.99…等很極端的百分位數，相較之下中間部份不那麼在意其精確程度了。

Merge and the rest …

除了透過 clustering 建構 T-Digest 之外，論文中也給了合併兩個 T-Digest 的方法。這帶來了一個很大的好處：當資料點太多時，我們可以分組計算 T-Digest 然後在合併起來，這讓平行分散計算變得可能很重要的一點是 T-Digest 的 merge 需要滿足結合律才能安全的用在平行分散的系統上。但很可惜的是， T-Digest 是近似演算法，所以沒有真正的滿足結合律。雖然如此，仍然可以在一定的誤差之下滿足這些條件，也使得實務上還是可行。，也就是 Divide and Conquer.

論文中剩下的部份除了討論成效之外，還給出了幾個實用的演算法：

• Trimmed Mean, 一個 quantile range 之間的平均值
• Cumulative Density Function(CDF)
• Inverse CDF