Жадно ищем '''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 W = new TreeSet() <tex>\emptyset</tex> <font color="green">// Вершины упорядочены по возрастанию расстояния до ближайшие к q. вершины </font> ep mL = случайная вершина из верхнего слоя |hnsw| - 1 maxLevel ep = индекс самого высокого слоя в <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] qLevel qL = -ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font> '''for''' level = maxLevel mL to qLevel qL + 1 result W = searchLayer(q, ep, ef=1, level) ep = resultW '''for''' level = min(maxLevelmL, qLevelqL) to 0 result W = searchLayer(q, ep, ef, level) neighbors neighbours = searchLayer.getFirst(M) Добавить связи между neighbours и ближайших к q на уровне levelвершин из W '''for''' v n <tex>\in</tex> neighbours: neighbors hnsw[level] = hnsw[level] <tex>\bigcup</tex> (n, q) hnsw[level] = hnsw[level] <tex>\bigcup</tex> (q, n)
<font color="green">// Убираем лишние связи, если требуется. </font>
vNeighbours nNeighbours = смежные с {v| (v на уровне , n) '''in''' hnsw[level]} '''if''' vNeighboursnNeighbours.Count() > mMax оставить у <font color="green">// Самая дальняя от n вершина, смежняя с ней. </font> v = {q1 | (q2, n) <tex>\in</tex> nNeighbours & <tex>\forall</tex>q2 <tex>\in</tex> hnsw[level], |q - q1| >= |q - q2|} hnsw[level] = hnsw[level] <tex>\setminus</tex> (n, v только связи с ближайшими mMax смежными вершинами на уровне ) hnsw[level] = hnsw[level] <tex>\setminus</tex> (v, n) ep = resultW '''if''' qLevel qL > maxLevelmL Добавить недостающие слои в '''for''' level = mL to qL hnsw.append({q, в каждый из них положить q{}})
== См. также ==
