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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Граф-представители)
Строка 5: Строка 5:
  
 
На таком графе поиск K ближайших соседей будет выглядеть так:
 
На таком графе поиск K ближайших соседей будет выглядеть так:
 
+
'''bool''' KNN(request)''':'''
'''bool''' KNN(request)''':'''
 
 
     Heap = <tex> \varnothing </tex>
 
     Heap = <tex> \varnothing </tex>
 
     current = случайная вершина графа
 
     current = случайная вершина графа
Строка 16: Строка 15:
 
             break
 
             break
 
     '''return''' K вершин из Heap c минимальным расстоянием
 
     '''return''' K вершин из Heap c минимальным расстоянием
 
  
 
==Описание структуры==
 
==Описание структуры==

Версия 00:32, 28 февраля 2019

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

Граф-представители

Граф-представитель (англ. Navigable Small World) — граф на множестве точек в пространстве, удовлетворяющий правилу [math]O(\log{n})[/math] рукопожатий. Т.е. средняя длина пути в графе [math]O(\log{n})[/math].

На таком графе поиск K ближайших соседей будет выглядеть так:

bool KNN(request):
    Heap = [math] \varnothing [/math]
    current = случайная вершина графа
    while true
        for v : смежные с current вершины
            distance = getDistance(v, request)           // getMetric(a, b) — расстояние между вершинами a и b в метрическом пространстве 
            Heap.push(key=distance, v=v)
        if Heap.first().key > getDistance(v, current)
            break
    return K вершин из Heap c минимальным расстоянием

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

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

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

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