Dữ liệu lớn & Xác suất
Count Sketch
ID: #235
Xem trên trang chủ
Thời gian (Time)
O(K)
Không gian (Space)
O(Width * Depth)
Mô tả nguyên lý
Ước tính tần suất mục tiêu trong luồng dữ liệu bằng hàm băm kết hợp dấu ngẫu nhiên (+1 hoặc -1).
Cài đặt mẫu (Implementation)
// Băm phần tử vào ma trận bảng đếm và cộng/trừ theo dấu băm phụ để giảm sai số nhiễu.
Dữ liệu lớn & Xác suất
Count-Min Sketch Heavy Hitters
ID: #188
Xem trên trang chủ
Thời gian (Time)
O(K)
Không gian (Space)
O(Width * Depth)
Mô tả nguyên lý
Thuật toán xác định các phần tử xuất hiện nhiều nhất (Heavy Hitters) trong luồng dữ liệu lớn.
Cài đặt mẫu (Implementation)
// Duy trì bảng đếm băm đa tầng để lọc các phần tử có tần suất vượt ngưỡng.