Приближенные словари: различия между версиями

Бурман и коллеги показали, что детерминированные схемы, в отличие от рандомизированных, позволяют получить компромиссное соотношение времени и памяти.

'''Теорема 6. Предположим, что детерминированная схема хранит подмножества размера n из совокупности размера m, используя s бит памяти, и отвечает на запросы о принадлежности с помощью t битовых зондов с запросами к памяти. Тогда <math>\tbinom{m}{n} \le max_{i \le nt} \tbinom{2s}{i}</math>.'''

У этого компромиссного результата есть интересное следствие. Вспомним, что схема хэширования FKS представляет собой структуру данных для хранения множеств размером не более n из совокупности размера m с использованием O(n log m) бит таким образом, что на запросы о принадлежности можно отвечать с использованием O(log m) битовых зондов. В качестве следствия этого компромиссного результата в работе [2] показано, что схема FKS применяет оптимальное количество битовых зондов с поправкой на постоянный коэффициент для данного объема памяти.

Из Теоремы 6 также следует, что любая детерминированная схема, отвечающая на запросы с использованием t битовых зондов, в наихудшем случае должна занимать не менее <math>ntm^{\Omega(1/t)}</math> бит памяти. Последний результат доказывает существование схем, почти достигающих нижней границы.