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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание структуры)
Строка 30: Строка 30:
  
 
==Описание структуры==
 
==Описание структуры==
 
+
[[Файл:HNSW.png|мини|500px|Иерархический маленький мир. [https://arxiv.org/abs/1603.09320 Источник]]]
 
+
'''Иерархический Маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} слоистая структура графов. На нулевом слое представлены все '''N''' вершин из исходной выборки. Вершина, присутствующая на уровне '''L''' так же присутствует на уровне '''L + 1''' с вероятностью '''P'''. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>
  
 
==Операции над структурой==
 
==Операции над структурой==

Версия 00:46, 1 марта 2019

Иерархия навигируемых малых миров (англ. 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)
        result.addAll(tempNearest)
    return k первых вершин из nearest

Очевидный недостаток этого алгоритма — опасность свалиться в локальный минимум.

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

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

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

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

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

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

См. также

Примечания

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

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