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

Иерархический маленький мир (англ. 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, layer):
    // Ввод: запрос q, входные точки ep, искомое количество ближайших соседей ef, номер слоя layer
    // Вывод: ef ближайших соседей q в слое layer
    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

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

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