Пространственно-эффективные вероятностные структуры данных для извлечения номера

Question

У нас есть алгоритм, который получает гипотетически длинный поток ключей. Затем он генерирует значение от 0 до 1 для каждого ключа, когда мы его обрабатываем, для последующего поиска. Набор ввода достаточно велик, и мы не можем позволить себе хранить одно значение для каждого ключа. Правило генерирования значений не зависит от ключей.

Теперь предположит, что мы можем терпеть ошибки в заднем поиске, но мы хотим еще минимизировать разницы в извлекаться и исходных значений (т.е. асимптотический в течение многих случайных извлечений).

Например, если исходное значение для данной клавиши было 0,008, то получение 0,06 намного лучше, чем извлечение 0,6.

Какие структуры данных или алгоритмы мы можем использовать для решения этой проблемы?

Цветные фильтры - это самая близкая структура данных, о которой я могу думать. Можно было квантовать выходной диапазон, использовать фильтр цветения для каждого ведра и как-то объединить их выход во время поиска, чтобы оценить наиболее вероятное значение. Прежде чем перейти к этому пути и изобрести колесо, существуют ли какие-либо известные структуры данных, алгоритмы, теоретические или практические подходы к решению этой проблемы?

Я в идеале ищу решение, которое позволяет параметризовать обмен между пробелами и ошибками.

Answer 1

Возможно, вариант фильтра Bloom, называемый Compact Approximator: как фильтр цветения, но обобщенный, поэтому записи являются значениями из решетки. Эта решетка здесь только плавает между 0 и 1 (она имеет больше структуры, чем просто быть решеткой, но она удовлетворяет требованиям) или, тем не менее, вы храните эти числа.

Обновление заменяет соответствующие записи максимумом между ним и значением, которое запоминается, а запрос вычисляет минимум всех соответствующих записей (примеры ниже). Результаты могут только переоценить истинное значение. Путем изменения порядка упорядочения (замена min и max и инициализация на 1 вместо 0) вы можете получить недооценку, вместе предоставляя интервал, который содержит истинное значение.

---

Так, например, используя первые аппроксимировать (переоценок), поставив в ряд выглядит следующим образом:

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

и получить завышенную выглядит следующим образом:

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