Giao diện
Scale & Approximation Algorithms
Khi hệ thống xử lý hàng triệu request mỗi giây và dataset vượt ngưỡng tỷ bản ghi, các cấu trúc dữ liệu truyền thống như HashSet, TreeMap bắt đầu sụp đổ — không phải vì chúng sai, mà vì chúng tốn quá nhiều bộ nhớ hoặc thời gian ở quy mô lớn.
Module này giới thiệu hai tư duy cốt lõi giúp kỹ sư giải quyết bài toán scale: cấu trúc dữ liệu xác suất (đánh đổi một phần accuracy để tiết kiệm hàng nghìn lần bộ nhớ) và chỉ mục không gian (phân vùng dữ liệu 2D để truy vấn logarithmic thay vì tuyến tính).
Lộ trình học
Nên bắt đầu từ Bloom Filter để nắm tư duy probabilistic, sau đó chuyển sang HyperLogLog cho bài toán đếm cardinality, và cuối cùng là Quadtree cho bài toán không gian 2D.
Bloom Filter (set membership) ↓ HyperLogLog (cardinality estimation) ↓ Quadtree (spatial indexing)
Nội dung
Cấu trúc dữ liệu xác suất (Probabilistic Data Structures)
| Bài học | Mô tả | Độ khó |
|---|---|---|
| Bloom Filter | Kiểm tra set membership với false positive rate có thể điều chỉnh — Cassandra, Chrome Safe Browsing | Intermediate |
| HyperLogLog | Ước lượng cardinality với O(1) memory — Redis PFCOUNT, analytics pipeline | Intermediate |
Chỉ mục không gian (Spatial Indexing)
| Bài học | Mô tả | Độ khó |
|---|---|---|
| Quadtree | Phân vùng đệ quy không gian 2D cho nearest-neighbor và range query — Uber, game engines | Intermediate |
So sánh tổng quan
| Thuật toán | Bộ nhớ | Độ chính xác | Bài toán chính |
|---|---|---|---|
| Bloom Filter | O(m) bits | ~99% (tunable) | Set membership, cache gating |
| HyperLogLog | O(1) ~12 KB | ~97.7% | Đếm unique elements |
| Quadtree | O(N) | 100% exact | Nearest neighbor, range query |
🧠 Quiz
Câu 1: Các cấu trúc dữ liệu probabilistic (Bloom Filter, HyperLogLog) đánh đổi gì để tiết kiệm bộ nhớ?
- [ ] A) Tốc độ truy vấn
- [x] B) Độ chính xác — chấp nhận sai số nhỏ (approximate) để dùng ít bộ nhớ hơn nhiều lần
- [ ] C) Khả năng insert
- [ ] D) Thread safety
💡 Giải thích: Đây là trade-off cốt lõi: exact counting 1 tỷ unique users cần ~8GB RAM (hash set). HyperLogLog cần ~12KB với sai số ~2%. Bloom Filter dùng vài MB thay vì hash table vài GB. Trong Big Data, approximate thường "đủ tốt".
Câu 2: Quadtree thường dùng trong loại ứng dụng nào?
- [ ] A) Xử lý chuỗi văn bản
- [ ] B) Sắp xếp số nguyên
- [x] C) Spatial data: game collision detection, bản đồ (GIS), image processing
- [ ] D) Quản lý transaction database
💡 Giải thích: Quadtree chia không gian 2D thành 4 quadrant đệ quy → truy vấn "tìm tất cả điểm trong vùng" chỉ cần duyệt các quadrant giao với vùng tìm kiếm. Ứng dụng: game engine (Unity, Unreal), Google Maps tiles, image compression (quad decomposition).