Quantileについて調査してみた(途中)

はじめに

uint64で高速にLog2を計算する方法を知った · hnakamur’s blogのあと、本題のQuantileについて調査したのでメモです。実はまだ途中なのですが、この後一旦他のことをするので現状をメモしておくということで。

試したレポジトリは https://github.com/hnakamur/quantile_experiment です。

Quantileを推測するアルゴリズムはいろいろある

まず推測する方式の前に、愚直に算出する方式を考えると、全ての入力値を取っておいてランクに対応する値を調べるということになります。ただ、それだと入力値が多くなってくると保管する領域も多くなってしまいます。

そこで入力値を適宜間引きながら、なるべく高精度で近似値を出すようなアルゴリズムがいろいろ考案されているというわけです。

Greenwald-Khanna方式のコードをGoに移植して試してみた

kazuhoさんのツイートで紹介されているコードはSpace-Efficient Online Computation of Quantile Summariesという論文のアルゴリズムを実装しているとのことでした。

検索してGreenwald-Khanna quantile estimator | Andrey Akinshinという解説記事とC#実装を見つけました(記事からリンクされているレポジトリ内には他にもたくさんのアルゴリズムの実装がありました)。

これをGoに移植して、愚直に算出する方式を比較するようなproperty-based テストをflyingmutant/rapidで書いてみました。指定したパーセントに対する値をestimatorで算出して、その値のランクを愚直方式で算出して、ランクのずれが指定の範囲内に収まっているかという確認の仕方をしています。この確認方法で良いのか、指定の範囲の計算方法がこれで正しいのかは私はまだよくわかっていません。

仮にこのテストが正しいとして、何回か失敗するケースがありました。この変更を入れると失敗しなくなったのですが、これが正しいかも不明です。

KLLというアルゴリズムを知った

Quantile - Wikipediaで以下の文で他のアルゴリズムを知りました。

The most popular methods are t-digest[16] and KLL.[17]

16は[1902.04023] Computing Extremely Accurate Quantiles Using t-Digests、17は[1603.05346] Optimal Quantile Approximation in Streamsという論文にリンクされていました。KLLは17の論文の3名の著者の頭文字になっています。

The KLL algorithm uses a more sophisticated

とあるのでt-digestよりはKLLのほうが良さそうな雰囲気です。

Apache Dataskethes というライブラリとREQというアリゴリズムを知った

さらに検索してSketching Quantiles and Ranks Tutorialというページを見つけました。natural rankとnormalized rankという概念や、サーチの際に境界を含める(inclusive)か含めない(exclusive)という選択があることなどを知れて良かったです。

Introduction to the 3 Quantiles Sketchesを見ると2018年3月にKLLの実装がリリースされていますが、その後2021年2月にREQという別の実装がリリースされています。

ということはREQのほうが良いのかなと思って、Javaの実装をGoに移植してみました。値の追加とパーセンタイルを求める部分がとりあえず動いたっぽいという段階で、こちらも愚直方式の結果と付き合わせるテストを書いています。

本当にこれで合ってるかとか性能評価とかはこれからしたいなというところですが、冒頭に書いたように別のことを先にやりたいので一旦ペンディングします。