Dữ liệu lớn & Streaming
Flajolet-Martin Algorithm
ID: #230
Xem trên trang chủ
Thời gian (Time)
O(N * Hash)
Không gian (Space)
O(Bitmask)
Mô tả nguyên lý
Thuật toán ước lượng số lượng phần tử phân biệt trong luồng dữ liệu dựa trên số lượng bit 0 tận cùng của mã băm.
Cài đặt mẫu (Implementation)
// Đếm vị trí bit 0 liên tiếp lớn nhất trong giá trị băm để suy ra số lượng phần tử duy nhất xấp xỉ.
Dữ liệu lớn & Streaming
Misra-Gries Heavy Hitters
ID: #232
Xem trên trang chủ
Thời gian (Time)
O(N)
Không gian (Space)
O(K counters)
Mô tả nguyên lý
Thuật toán tìm các phần tử xuất hiện chiếm tỷ trọng lớn hơn 1/k trong luồng dữ liệu thời gian thực.
Cài đặt mẫu (Implementation)
// Duy trì bộ đếm k-1 phần tử ứng viên, giảm trừ đồng loạt khi xuất hiện phần tử lạ khác.
Dữ liệu lớn & Streaming
Top-K Stream Processing (Space-Saving)
ID: #234
Xem trên trang chủ
Thời gian (Time)
O(N)
Không gian (Space)
O(Capacity)
Mô tả nguyên lý
Theo dõi K phần tử có tần suất xuất hiện cao nhất trong luồng dữ liệu khổng lồ với bộ nhớ giới hạn.
Cài đặt mẫu (Implementation)
// Thay thế phần tử tần suất thấp nhất bằng phần tử mới khi bộ đếm bị đầy.