Поиск ближайших соседей с помощью иерархического маленького мира
Версия от 22:45, 28 февраля 2019; 93.185.30.235 (обсуждение)
Иерархия навигируемых малых миров (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает список с пропусками.
Содержание
Маленький мир
Маленький мир (англ. 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