Поиск ближайших соседей с помощью иерархического маленького мира
Иерархия навигируемых малых миров (англ. 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
Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум.
Описание структуры
Иерархический Маленький мир (англ. Hierarchical Navigable Small World) — слоистая структура графов. На нулевом слое представлены все N вершин из исходной выборки. Вершина, присутствующая на уровне L так же присутствует на уровне L + 1 с вероятностью P. Т.е. кол-во слоёв растет как . Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за
