Изменения

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

На таком графе приближенный поиск K ближайших соседей будет выглядеть так: KNN(request, m, k)''':''' Heap nearest = new TreeSet() <texfont color="green"> \varnothing // вершины упорядочены по возрастанию расстояния до request </texfont> current 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 вершины distance = getDistance '''if''' !visited.contains(v, request) <font color="green">// getMetric candidates.add(a, bv) {{---}} расстояние между вершинами a и b в метрическом пространстве </font> Heap visited.pushadd(key=distance, val=v) '''if''' Heap tempNearest.firstadd(v) result.key > getDistanceaddAll(v, currenttempNearest) break '''return''' K k первых вершин из Heap c минимальным расстояниемnearest