Говоря простым языком, знания DS не требуются.

Начало

Если мы когда-либо работаем над каким-либо проектом по науке о данных или хотим добавить в вашу систему более интеллектуальный поиск (например, векторный поиск). возможно, вы уже использовали этот алгоритм — HNSW.

Этот пост не для того, чтобы просматривать документы (я не могу этого сделать) с деталями, а просто для того, чтобы просто выделить основную идею этого алгоритма, чтобы поделиться ею и обсудить.

Как обычно, начнем с простой аналогии.

Новый Южный Уэльс (судоходный маленький мир)

Итак, сегодня, допустим, вы хотите догнать своего друга на выходных, вы остаетесь в городе 1, а ваш друг в городе 2, городе 1 и городе 2 вместе становится «Неотвратимым маленьким миром», в этом мире 2 правила:

  • вы можете пользоваться только общественным транспортом
  • Есть только автобусы

Для достижения кратчайшего времени в пути автобусная система построена таким образом:

  • каждый раз добавлять новую станцию ​​(случайным образом) на карту
  • При добавлении новой станции подключайтесь к ближайшей станции на карте (жадно)

Давайте построим это.

Итак, как видите: есть 2 города. теперь, если вы строитель, чтобы соединить эти 7 автобусных остановок вместе, чтобы обеспечить минимальное время в пути (начиная с любой станции), как это сделать?

Помните идею построения минимального остовного дерева шаг за шагом?

Таким образом, алгоритм NSW чем-то похож на алгоритм prim. разница в том, что вместо использования кучи для отслеживания минимального расстояния до начальной точки мы находим (k) ближайших точек на карте и соединяем их.

Итак, допустим, у вас есть только 1 друг, которого нужно встретить в городе 2, поэтому нужно найти только 1 «дом друга», поэтому k = 1. Значит ли это, что если вы хотите сегодня встретиться с 3 друзьями в городе 2, произойдет тот же процесс, что и ниже, но k = 3 (каждый раз соединяйте 3 ближайшие автобусные остановки)? да.

давай продолжим.

Шаг 1, случайным образом выберите автобусную остановку под номером 2.