Хеширование с учетом локальных особенностей - что происходит, когда ведро пустое?

Question

Предположим, я построил базу данных LSH согласно некоторому набору хэшей, и сейчас я начинаю запрашивать базу данных, чтобы найти приблизительных ближайших соседей.

Есть ли какие-либо рекомендации относительно того, что происходит, когда вы вычисляете хеш для точки запроса, и соответствующий сегмент пуст? Точно так же, скажем, я хочу найти 5 приблизительных ближайших соседей, а в корзине есть только 4 других точки данных?

Answer 1

Я считаю, что слишком мало очков для поиска означает, что у вас слишком много корзин для ваших тренировочных данных. И это, конечно, зависит от приложения. Взгляните на набор инструментов LSH от реализации Грега Шахнаровича и его файл README. В этой реализации меньшее количество хеш-функций (меньшее k) означает более полные сегменты, а это, в свою очередь, означает более медленный LSH.