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

Иерархический маленький мир (англ. 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)
        nearest.addAll(tempNearest)
    return k первых вершин из nearest

Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа m, вероятность такого застревания экспоненциально падает.

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

Иерархический Маленький мир (англ. Hierarchical Navigable Small World) — слоистая структура графов. На нулевом слое представлены все N вершин из исходной выборки. Вершина, присутствующая на уровне L так же присутствует на уровне L + 1 с вероятностью P. Т.е. кол-во слоёв растет как [math]O(\log N)[/math]. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за [math]O(\log N)[/math].

Иерархический маленький мир. Источник

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

Поиск ближайших соседей в слое

Жадно идём по уровню в сторону запроса.

searchLayer(q, ep, ef, lc):
    // Ввод: запрос q, входная точка ep, искомое количество ближайших соседей ef, номер слоя layer
    // Вывод: ef ближайших соседей q
    candidates = new TreeSet(ep) // Вершины упорядочены по возрастанию расстояния до q. 
    result = new TreeSet(ep)
    visited = new HashSet(ep)
    while candidates.isNotEmpty()
        current = candidates.getMin()
        furthest = result.getMax()
        if distance(current, q) > distance(furthest, q)
            break // Мы в локальном минимуме. 
        for v : смежные с current вершины в уровне layer
            if !visited.contains(r)
                visited.add(v)
                furthest = result.getMax()
                if distance(v, q) < distance(furthest, q) or result.count() < ef
                    candidates.add(v)
                    result.add(v)
                    if result.count() > ef
                        result.removeLast()
    return result

Поиск ближайших соседей во всей структуре

Жадно ищем ближайшего соседа на каждом уровне, кроме 0. Когда находим, спускаемся через него на уровень ниже. На нулевом уровне жадно ищем K ближайших соседей.

knn(hnsw, q, K, ef):
    // Ввод: граф hnsw, запрос q, искомое количество ближайших соседей  K, количество кандидатов при поиске ef
    // Вывод: K ближайших соседей q
    result = new TreeSet() // Вершины упорядочены по возрастанию расстояния до request. 
    ep = случайная вершина из верхнего слоя hnsw
    maxLevel = индекс самого высокого слоя в hnsw
    for level = maxLevel to 1
        result = searchLayer(q, ep, ef=1, level) // На каждом уровне, кроме нижнего мы ищем всего одну ближайшую вершину. 
        ep = result.getMin()
    result = searchLayer(q, ep, ef, lc=0)
    return первые K элементов из result

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

Жадный поиск вершины. Оригинал

Случайным образом выбираем максимальный слой, на котором представлена q. Жадно ищем M ближайших вершин к q на каждом уровне, на котором она представлена; добавляем связи q с ними; удаляем лишние связи у новообразовавшихся соседей.

insert(hnsw, q, m, mMax, ef, mL):
    // Ввод: граф hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины 
    //       на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. 
    // Вывод: hnsw с вставленным элементом q. 
    result = new TreeSet() // Вершины упорядочены по возрастанию расстояния до q. 
    ep = случайная вершина из верхнего слоя hnsw
    maxLevel = индекс самого высокого слоя в hnsw
    qLevel = -ln(rand(eps, 1.0)) * mL // Верхний слой для вершины q. 
    for level = maxLevel to qLevel + 1
        result = searchLayer(q, ep, ef=1, level)
        ep = result
    for level = min(maxLevel, qLevel) to 0
        result = searchLayer(q, ep, ef, level)
        neighbors = searchLayer.getFirst(M)
        Добавить связи между neighbours и q на уровне level
        for v : neighbors
            // Убираем лишние связи, если требуется. 
            vNeighbours = смежные с v на уровне level
            if vNeighbours.Count() > mMax
                оставить у v только связи с ближайшими mMax смежными вершинами на уровне level
        ep = result
    if qLevel > maxLevel
        Добавить недостающие слои в hnsw, в каждый из них положить q

Источники информации

Статья на википедии о маленьких мирах