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

:

учитывая большой (~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 просто используйте отсортированный список и выполните двоичный поиск для конкретного входного значения.

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

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