Говоря простым языком, знания DS не требуются.
Начало
Если мы когда-либо работаем над каким-либо проектом по науке о данных или хотим добавить в вашу систему более интеллектуальный поиск (например, векторный поиск). возможно, вы уже использовали этот алгоритм — HNSW.
Этот пост не для того, чтобы просматривать документы (я не могу этого сделать) с деталями, а просто для того, чтобы просто выделить основную идею этого алгоритма, чтобы поделиться ею и обсудить.
Как обычно, начнем с простой аналогии.
Новый Южный Уэльс (судоходный маленький мир)
Итак, сегодня, допустим, вы хотите догнать своего друга на выходных, вы остаетесь в городе 1, а ваш друг в городе 2, городе 1 и городе 2 вместе становится «Неотвратимым маленьким миром», в этом мире 2 правила:
- вы можете пользоваться только общественным транспортом
- Есть только автобусы
Для достижения кратчайшего времени в пути автобусная система построена таким образом:
- каждый раз добавлять новую станцию (случайным образом) на карту
- При добавлении новой станции подключайтесь к ближайшей станции на карте (жадно)
Давайте построим это.
Итак, как видите: есть 2 города. теперь, если вы строитель, чтобы соединить эти 7 автобусных остановок вместе, чтобы обеспечить минимальное время в пути (начиная с любой станции), как это сделать?
Помните идею построения минимального остовного дерева шаг за шагом?
Таким образом, алгоритм NSW чем-то похож на алгоритм prim. разница в том, что вместо использования кучи для отслеживания минимального расстояния до начальной точки мы находим (k) ближайших точек на карте и соединяем их.
Итак, допустим, у вас есть только 1 друг, которого нужно встретить в городе 2, поэтому нужно найти только 1 «дом друга», поэтому k = 1. Значит ли это, что если вы хотите сегодня встретиться с 3 друзьями в городе 2, произойдет тот же процесс, что и ниже, но k = 3 (каждый раз соединяйте 3 ближайшие автобусные остановки)? да.
давай продолжим.
Шаг 1, случайным образом выберите автобусную остановку под номером 2.