Фильтр для запросов диапазона на наборе

Question

У нас есть набор ключей S.

Для запросов на членство (есть k в S?) Фильтры Блума часто помогают нам быстро определить, что ключа нет в наборе.

Как мы можем отфильтровать запросы диапазона (есть ли ключ из диапазона [k1, k2] в S?)?

Answer 1

Вы можете решить эту проблему за время O (log n), используя либо деревья сегментов, либо деревья Фенвика.

С сегментными деревьями вы можете задать вопрос: есть ли битовый набор в диапазоне [a..b]? На этот вопрос можно ответить во время O (log n). Кроме того, вы можете установить (или сбросить) один бит за время O (log n).

Аналогично с деревьями Фенвика.

Предположение: ключи k1, k2 и т.д ... являются целыми числами - мы должны сделать это предположение, чтобы мы могли понять диапазон [k1..k2].

Answer 2

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

Например, у вас есть хеш-функция f (x) и хеш-функцияг (х).Вы определяете f (x) так, что f (x) = hash_function (x div 16) + x mod 16.

При поиске вы можете искать 2 байта (16 бит), окружающих f (x)результат за 1 бит.Если вы найдете его, проверьте соответствующее значение для попадания.

Это означает, что вы можете искать совпадения по 16 значениям одновременно с быстрым двухбайтовым извлечением.

Обратите внимание, что игра схэш-функции таким образом могут повлиять на ваши результаты другими способами.

Answer 3

У вас есть контроль длины диапазонов, которые вы хотите проверить?Если диапазон мал (k2 - k1 <небольшое число), то вы можете просто использовать фильтр Блума и проверять каждое k в диапазоне. </p>