HyperLogLog sketchは面白い accepted

Abstract

HyperLogLog (以下HLL)は、与えられたデータセットのdistinct element countを省メモリで高速に推定するアルゴリズムです。

RedisやPrestoなど様々なミドルウェアにHLLを利用するための機能が組み込みで用意されていますし、現在のビッグデータ解析において無くてはならないものとなっています。

HLLではデータセットをsketchとよばれる省メモリな表現に変換したのち、そこに保存された値を集計して推定値を算出しますが、このsketchには興味深い特徴があります。

まず、異なるデータセットに対して作られたそれぞれのsketchをmergeして、unionのdistinct countを推定することができます。

そして、HLL sketchの構築と推定値の算出は独立したステップであるため、推定に影響を与えることなくsketchのバイナリ表現を最適化してサイズを圧縮することが可能です。

逆にまた、HLL sketchを変えずに推定器を改良する手法もいくつも提案されています。

Contents

このセッションではまず、HLLの仕組みおよびRedisにおける利用例を解説します。

そののち、HLLがRedis内部でどのように実装されているか、Redisのバージョンアップとともにどのように改良されてきたかを見ていきます。

そしてHLL sketchに関する近年の面白い研究について紹介できたらと思っています。

Video
Session Information
Confirmed confirmed
Starts On 8/31/19, 10:30 AM
Room Seminar Room 1204
Session Duration 50 min session
Spoken Language Japanese
Interpretation Unavailable
Slide Language Japanese