Поиск ближайших соседей с помощью иерархического маленького мира — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Маленький мир)
Строка 2: Строка 2:
  
 
==Маленький мир==
 
==Маленький мир==
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>.
+
'''Маленький мир''' (англ. ''Small World'') {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
  
 
Для маленького мира на точках в Евклидовом пространстве, приближенный поиск K ближайших соседей будет выглядеть так:
 
Для маленького мира на точках в Евклидовом пространстве, приближенный поиск K ближайших соседей будет выглядеть так:

Версия 23:56, 28 февраля 2019

Иерархия навигируемых малых миров (англ. Hierarchical Navigable Small World) — структура данных, позволяющая эффективно находить K почти что ближайших соседей. По своей концепции напоминает список с пропусками.

Маленький мир

Маленький мир (англ. Small World) — граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально [math]\log{N}[/math]. Но при этом средняя степень вершины мала.

Для маленького мира на точках в Евклидовом пространстве, приближенный поиск 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

Описание структуры

Операции над структурой

Поиск элемента

Вставка элемента