Эффективный поиск двоичных строк с малым расстоянием Хэмминга в большом наборе

Проблема:

Учитывая большой (~ 100 миллионов) список 32-разрядных целых чисел без знака, 32-разрядное число без знака битовое целое входное значение и максимальное Расстояние Хэмминга возвращают все элементы списка, которые находятся в пределах указанного расстояния Хэмминга входного значения.

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

Пример:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

Мои мысли на данный момент:

Для вырожденного случая расстояния Хэмминга, равного 0 , просто используйте отсортированный список и выполните двоичный поиск определенного входного значения.

Если бы расстояние Хэмминга было бы только ev Если быть 1, я мог бы перевернуть каждый бит в исходном вводе и повторить вышеупомянутое 32 раза.

Как я могу эффективно (без сканирования всего списка) обнаруживать элементы списка с расстоянием Хэмминга> 1.