Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями
Marsermd (обсуждение | вклад) м (Marsermd переименовал страницу Поиск ближайших соседей с помощью графов-представителей в [[Поиск ближайших соседей с помощью иерархии мал…) |
Marsermd (обсуждение | вклад) м (Marsermd переименовал страницу Поиск ближайших соседей с помощью иерархии малых миров в [[Поиск ближайших соседей с помощью иерархии мален…) |
(нет различий)
|
Версия 00:11, 1 марта 2019
Иерархия навигируемых малых миров (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает список с пропусками.
Содержание
Маленький мир
![](/wiki/images/thumb/2/27/SmallWorld_Greedy.png/500px-SmallWorld_Greedy.png)
Жадный поиск ближайшего соседа. Чёрные ребра — короткие связи с ближайшими соседями, красные рёбра — длинные связи, обеспечивающие малое мат. ожидание длины пути. Оригинал
Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально
. Но при этом средняя степень вершины мала.Для маленького мира на точках в Евклидовом пространстве, приближенный поиск K ближайших соседей будет выглядеть так:
KNN(request, m, k): nearest = new TreeSet() // вершины упорядочены по возрастанию расстояния до request candidates = new TreeSet() visited = new HashSet() for i = 1 to m candidates.add(случайная вершина графа) tempNearest = new TreeMap() while true current = candidates.popMin() if current дальше чем k-й элемент nearest break for v : смежные с current вершины if !visited.contains(v) candidates.add(v) visited.add(v) tempNearest.add(v) result.addAll(tempNearest) return k первых вершин из nearest
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум.