120
правок
Изменения
Нет описания правки
'''Иерархический маленький мир''' (англ. ''Hierarchical Navigable Small World''<ref>[https://arxiv.org/abs/1603.09320 Yu. A. Malkov, D. A. Yashunin {{---}} Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs]</ref>) {{---}} структура данных, позволяющая эффективно искать K k почти что ближайших соседей. <br/>
Ключевая идея {{---}} вероятностная эвристика для создания соединений на большие расстояния. <br/>
По своей концепции напоминает [[список с пропусками]]. <br/>
'''Маленький мир'''<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D1%80_%D1%82%D0%B5%D1%81%D0%B5%D0%BD_(%D0%B3%D1%80%D0%B0%D1%84) Статья о маленьком мире на википедии]</ref> (англ. ''Small World''<ref>[https://en.wikipedia.org/wiki/Small-world_network Статья о маленьком мире на английской википедии]</ref>) {{---}} граф, в котором мат. ожидание кратчайшего пути между двумя случайно выбранными вершинами растёт пропорционально <tex>\log{N}</tex>. Но при этом средняя степень вершины мала.
Для маленького мира на точках в Евклидовом пространстве жадный поиск K k ближайших соседей будет выглядеть так:
'''knn'''(V, E, request, m, k)''':'''
W = <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины. </font>
