This article is a Private article. Only a writer and users who know the URL can access it.
Please change open range to public in publish setting if you want to share this article with other users.

Data Structures for Big Data (HelloInterview) のメモ

Last updated at 2026-06-14Posted at 2026-05-02

この記事で学んだことをメモる。

いずれも、Redisでサポートされている。

Bloom Filter

= Low memory Set with add(val) and may_contain(val). No remove(val).

🟢 いつ使うべきか

例えば

web crawler で、訪問済みのページの管理
Redis cache で、アクセス前に Bloom Filter を見ることで、cache miss するリクエストの多くをしなくて済む。 (他のクライアントがcacheを更新している場合や、TTLによるアイテム削除がある場合は使えない)

🟢 内部構造

todo: まとめる

Count-Min Sketch

= Low memory Counter with increment(key) and decrement(key) and upper_bound_count(key)

ただし、Redis では、decrement(key)はサポートされていない。

🟢 いつ使うべきか

例えば、Heaver Hitter (頻出アイテム算出) に使用できる。todo: 以下整理する

ref. YouTube TopK - DD: Can we make use of approximations to improve performance?

🟢 内部構造

todo: まとめる

HyperLogLog

= Low memory Counter with increment(val) and approx_cardinality(val). No decrement(val).

📝 approx_cardinality(val) = approx_num_unique(val)

🟢 いつ使うべきか

例えば、

Analytics workloads
Database systems　(Analytics DB で、カラムの中のunique countの近似値を返すクエリ)
Security applications
Cache analysis (Cacheで、incoming queriesから、実際に幾つのキーが作られたのかを計算する)

todo:それぞれ理解する

🟢 内部構造

todo: まとめる

肝となるのは、「trailing zeroが長く続くhash値が発生した -> たくさんのユニークアイテムが存在している可能性が高い」という論理。

bucket ごとに、trailing zero max length を更新する. (記事ではleadingだったが)

複数のbucketに区切るのは精度を上げるため。偶然zeroが長く連続するハッシュ値が偶然した場合の影響を減らす。
read時には、すべてのbucketのレジスタのharmonic meansをとって、count推定をする。

Approximate Quantiles

= Low memory List with add(val) and remove(val)and approx_quantile(val)

todo

Ref.

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up