Распределенный LSH (хеширование с учетом местоположения)

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

Наивным подходом было бы разбросать все объекты по разным серверам и отправить один запрос на каждый сервер. Сервер с лучшим ответом правильно имеет правильный объект.

Я уверен, что должно быть какое-то лучшее решение, когда запрос не нужно отправлять на все узлы сервера, а похожие объекты сгруппированы вместе на одном сервере.

Что было бы хорошим подходом для распределенных таблиц LSH? Может быть, есть еще какие-то проекты?

Спасибо за любую подсказку.


database hash distributed
person Marlon    schedule 23.10.2010    source источник
comment
Я бы посмотрел на Кассандру с пользовательским разделением.   -  person Savino Sguera    schedule 11.08.2011
comment
Это может иметь значение: Распределенный поиск по сходству в больших измерениях с использованием хэширования с учетом местоположения Хагани, Микеле и Арберер.   -  person Kipton Barros    schedule 02.10.2012
comment
Ссылка @KiptonBarros исчезла, но этот документ можно найти здесь: openproceedings.org/2009/ conf/edbt/HaghaniMA09.pdf   -  person duhaime    schedule 16.08.2017

Ответы (1)


arrow_upward
2
arrow_downward

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

Все становится сложнее, если вы не знаете точных ключей (как я подозреваю, в вашей ситуации) - LSH генерирует общий порядок для ваших записей - где похожие записи, вероятно (но не гарантировано), будут иметь один и тот же хэш. Я думаю об этом, например, как о сопоставлении гиперплоскостей с длиной их вектора нормали от начала координат... следовательно, например, при поиске подобной (но не идентичной) гиперплоскости той, которая находится между 4 и 5 единицах от начала координат, хорошее место для начала поиска среди других гиперплоскостей между 4 и 5 единицами от начала координат. Следовательно, если это «расстояние от источника» является вашей хеш-функцией, чувствительной к местности, вы можете shard ваши данные используют его, и при этом вы можете уменьшить нагрузку (при этом увеличив задержку в худшем случае) путем поиска только сегмента с соответствующим LCH «расстояние от источника». С этим конкретным LCH, где сходство линейно коррелирует с хэшем, можно было бы получить окончательный результат, обращаясь только к подмножеству распределенных серверов. Это относится не ко всем функциям LSH.

ИМХО, все зависит от вашей функции LSH - и этот выбор зависит от специфики вашего приложения.

person aSteve    schedule 25.09.2011