Express lanes — layers and ef_search

1def search(query, k):
2    ep = entry_point      # a promoted top-layer node
3    # express lanes: greedy-hop down the sparse upper layers,
4    # keeping just the single best node at each level
5    for level in range(top_layer, 0, -1):
6        ep = search_layer(query, ep, ef=1, level)
7    # bottom layer: dense local refinement with the full beam
8    candidates = search_layer(query, ep, ef=ef_search, level=0)
9    return candidates.nearest(k)

1def search_layer(query, ep, ef, level):
2    visited = {ep}
3    candidates = pq([ep])      # frontier to explore
4    found = pq([ep])           # best ef so far
5    while candidates:
6        c = candidates.pop_nearest(query)
7        if dist(c, query) > found.farthest_dist():
8            break              # nothing closer left to find
9        for n in neighbors(c, level):
10            if n not in visited:
11                visited.add(n)
12                candidates.push(n); found.push(n)
13                found.trim_to(ef)   # keep only ef closest
14    return found

1def insert(node):
2    # most nodes stay at level 0; a rare few are promoted high,
3    # which is what builds the sparse upper express lanes
4    level = floor(-ln(rand()) * mL)
5    ep = entry_point
6    for lvl in range(top_layer, level, -1):
7        ep = search_layer(node, ep, ef=1, lvl)
8    for lvl in range(min(level, top_layer), -1, -1):
9        nbrs = search_layer(node, ep, ef=ef_construction, lvl)
10        node.link(select_M(nbrs), lvl)   # M edges per level
11    if level > top_layer: entry_point = node