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

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

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

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

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

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, val=v)
        if Heap.first().key > getDistance(v, current)
            break
    return K вершин из Heap c минимальным расстоянием