Структура индекса для запросов top-k для цепочек битов

Для данного массива цепочек битов (все одинаковой длины) и строки запроса Q можно найти наиболее подходящие строки для Q из top-k, где сходство между строками A и B определяется как число 1 в A и B ( применяется поразрядно).

Я думаю, что для этой проблемы должен быть классический результат.

k мало, в сотнях, а число векторов в сотнях миллионов и длина векторов составляет 512 или 1024

7 голосов | спросил Moonwalker 9 J0000006Europe/Moscow 2016, 22:23:28

2 ответа


0

Одним из способов решения этой проблемы является создание K-ближайшего соседнего графа (K-NNG) (орграф) с функцией подобия Рассела-Рао.

Обратите внимание, что эффективная конструкция K-NNG остается открытой проблемой, и ни одно из известных решений этой проблемы не является общим, эффективным и масштабируемым [цитата из Эффективное построение графа ближайшего соседа для общих мер подобия - Донг, Чарикар, Ли 2011] .

Ваша дистанционная функция часто называется сходством Рассела-Рао (см., например, Обзор двоичного сходства и меры расстояния - Чой, Ча, Tappert 2010 ). Обратите внимание, что сходство с Расселом-Рао не является метрикой (см. Свойства бинарных векторных мер различий - Чжан, Срихари 2003 ):" if "часть" d (x, y) = 0 тогда и только тогда, когда x == y ", ложно.

В быстрый алгоритм поиска k-ближайших соседей с неметрическим различием - Zhang, Srihari 2002 , авторы предлагают быстрый алгоритм иерархического поиска для поиска k-NN с использованием неметрической меры в двоичном векторном пространстве. Они используют параметрическую двоичную векторную функцию расстояния D (β). Когда β = 0, эта функция сводится к функции расстояния Рассела-Рао. Я бы не назвал это «классическим результатом», но это единственная статья, в которой я смог найти эту проблему.

Возможно, вы захотите проверить эти два опроса: О проблемах поиска неметрического сходства в сложных доменах - Skopal, Bustos 2011 и Опрос по поиску ближайших соседей Методы - Реза, Гахремани, Надери 2014 . Может быть, вы найдете то, что я пропустил.

ответил Lior Kogan 30 J0000006Europe/Moscow 2016, 23:17:10
0

Эту проблему можно решить, написав простое задание Map and Reduce. Я не утверждаю, что это лучшее решение, и не утверждаю, что это only решение.

Кроме того, вы раскрыли в комментариях, что k исчисляется сотнями, существуют миллионы цепочек битов и что размер каждой из них составляет 512 или 1024.


Псевдокод Mapper:

  • Учитывая Q ;
  • Для каждой цепочки битов b вычислите сходство = b & Q
  • Emit (сходство, b)

Теперь объединитель может объединить список всех цепочек битов из каждого сопоставителя, имеющих одинаковое сходство.

Псевдокод редуктора:

  • Потреблять (схожесть, listOfBitStringsWithThisSdentifity) ;
  • Выведите их в порядке убывания значения сходства.

На выходе редуктора вы можете извлечь цепочки битов top-k.

Итак, парадигма MapReduce, вероятно, является классическим решением, которое вы ищете.

ответил displayName 1 J000000Friday16 2016, 18:49:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132