Cấu trúc dữ liệu xác suất không gian hiệu quả để khôi phục số

Question

Hãy xem xét chúng tôi có một thuật toán nhận được luồng khóa dài về mặt giả thuyết. Sau đó nó tạo ra một giá trị từ 0 đến 1 cho mỗi khóa, khi chúng ta xử lý nó, để thu hồi sau. Bộ đầu vào đủ lớn để chúng tôi không thể chứa một giá trị cho mỗi khóa. Quy tắc tạo giá trị độc lập trên các khóa.

Bây giờ, giả sử rằng chúng ta có thể tha thứ cho lỗi trong việc tra cứu sau, nhưng chúng tôi muốn vẫn giảm thiểu sự khác biệt trong lấy và gốc giá trị (ví dụ: tiệm qua nhiều khả năng tìm lại ngẫu nhiên).

Ví dụ: nếu giá trị ban đầu của một khóa nhất định là 0,008, thì truy xuất 0,06 tốt hơn nhiều so với truy xuất 0,6.

Chúng tôi có thể sử dụng cấu trúc dữ liệu hoặc thuật toán nào để giải quyết vấn đề này?

Bộ lọc Bloom là cấu trúc dữ liệu gần nhất mà tôi có thể nghĩ đến. Người ta có thể định lượng phạm vi đầu ra, sử dụng bộ lọc nở hoa cho mỗi nhóm, và bằng cách nào đó kết hợp đầu ra của chúng tại thời điểm truy xuất để ước tính giá trị có khả năng nhất. Trước khi tôi tiến hành với con đường này và phát minh lại bánh xe, có bất kỳ cấu trúc dữ liệu, thuật toán, phương pháp lý thuyết hoặc thực tế đã biết nào để giải quyết vấn đề này không?

Tôi lý tưởng tìm kiếm giải pháp có thể tham số sự cân bằng giữa không gian và tỷ lệ lỗi.

Answer 1

Có lẽ một biến thể của bộ lọc Bloom được gọi là Compact Approximator: giống như bộ lọc nở hoa nhưng được khái quát hóa để các mục nhập là các giá trị từ mạng tinh thể. Mạng đó ở đây chỉ nổi giữa 0 và 1 (nó có cấu trúc nhiều hơn là chỉ là một mạng nhưng nó đáp ứng các yêu cầu) hoặc tuy nhiên bạn đang lưu trữ những con số đó.

Bản cập nhật thay thế các mục có liên quan theo giá trị tối đa giữa giá trị đó và giá trị được ghi nhớ, truy vấn tính toán tối thiểu tất cả các mục có liên quan của nó (ví dụ bên dưới). Kết quả chỉ có thể đánh giá quá cao giá trị thực. Bằng cách đảo ngược thứ tự (hoán đổi min và max và khởi tạo thành 1 thay vì 0), bạn có thể nhận được một đánh giá thấp, cùng nhau đưa ra một khoảng thời gian có chứa giá trị thực.

---

Vì vậy, ví dụ, bằng cách sử dụng đầu tiên xấp xỉ (overestimations), đặt trong một số trông như thế này:

index1 = hash1(key) 
data[index1] = max(data[index1], value); 
index2 = hash2(key) 
data[index2] = max(data[index2], value); 
... etc 

Và nhận được đánh giá quá cao trông giống như:

result = 1 
index1 = hash1(key) 
result = min(data[index1], result); 
index2 = hash2(key) 
result = min(data[index2], result); 
... etc