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

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

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

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