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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Граф-представители)
(→‎Граф-представители)
Строка 2: Строка 2:
  
 
==Граф-представители==
 
==Граф-представители==
−
'''Граф-представитель''' (англ. ''Navigable Small World'') {{---}} граф на множестве точек в пространстве, удовлетворяющий правилу <tex>O(\log{n})</tex> рукопожатий. Т.е. средняя длина пути в графе <tex>O(\log{n})</tex>.
+
'''Граф-представитель''' (англ. ''Navigable Small World'') {{---}} граф на множестве точек в Евклидовом пространстве, удовлетворяющий правилу <tex>O(\log{n})</tex> рукопожатий. Т.е. средняя длина кратчайшего пути между вершинами в графе равна <tex>O(\log{n})</tex>.
  
−
На таком графе поиск K ближайших соседей будет выглядеть так:
+
На таком графе приближенный поиск K ближайших соседей будет выглядеть так:
−
  KNN(request)''':'''
+
  KNN(request, m, k)''':'''
−
     Heap = <tex> \varnothing </tex>
+
     nearest = new TreeSet()  <font color="green">// вершины упорядочены по возрастанию расстояния до request </font>
−
     current = случайная вершина графа
+
     candidates = new TreeSet()
−
    '''while''' ''true''
+
    visited = new HashSet()
−
        '''for''' v : смежные с current вершины
+
    '''for''' i = 1 '''to''' m
−
            distance = getDistance(v, request)           <font color="green">// getMetric(a, b) {{---}} расстояние между вершинами a и b в метрическом пространстве </font>
+
        candidates.add(случайная вершина графа)
−
            Heap.push(key=distance, val=v)
+
        tempNearest = new TreeMap()
−
        '''if''' Heap.first().key > getDistance(v, current)
+
        '''while''' ''true''
−
            break
+
            current = candidates.popMin()     
−
     '''return''' K вершин из Heap c минимальным расстоянием
+
            '''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
  
 
==Описание структуры==
 
==Описание структуры==

Версия 01:49, 28 февраля 2019

Иерархия графов-представителей (англ. 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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Поиск_ближайших_соседей_с_помощью_иерархического_маленького_мира&oldid=69993»