Dữ liệu lớn & Streaming

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 3)

Dữ liệu lớn & Streaming

Flajolet-Martin Algorithm

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

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)

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.