120
правок
Изменения
→Вставка элемента
===Вставка элемента===
Случайным образом выбираем максимальный слой, на котором представлена '''q'''.
Жадно ищем '''M''' ближайших вершин к '''q''' на каждом уровне, на котором она представлена; добавляем связи '''q''' с ними; удаляем лишние связи у новообразовавшихся соседей.
'''insert'''(hnsw, q, m, mMax, ef, mL)''':'''
<font color="green">// Ввод: граф hnsw, запрос на добавление q, желаемое количество связей m, максимальное количество связей вершины </font>
<font color="green">// на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. </font>
<font color="green">// Вывод: hnsw с вставленным элементом q. </font>
result = new TreeSet() <font color="green">// Вершины упорядочены по возрастанию расстояния до q. </font>
ep = случайная вершина из верхнего слоя hnsw
maxLevel = индекс самого высокого слоя в hnsw
qLevel = -ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font>
'''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
<font color="green">// Убираем лишние связи, если требуется. </font>
vNeighbours = смежные с v на уровне level
'''if''' vNeighbours.Count() > mMax
оставить у v только связи с ближайшими mMax смежными вершинами на уровне level
ep = result
'''if''' qLevel > maxLevel
Добавить недостающие слои в hnsw, в каждый из них положить q
== См. также ==
