nx_vec_nsw.nx source

1// nx_vec_nsw.nx -- R-VEC-3 of the onsite-search S-class ladder: SOVEREIGN approximate-nearest-neighbor INDEX via 2// a Navigable Small World proximity graph (LIBRARY). "Illustration of the multi-layered search process of a 3// Hierarchical Navigable Small World graph" (cited srch_hnsw.raw) -- this builds the SINGLE-LAYER NSW core (the 4// base HNSW stacks into layers); an ANN search "is allowed to return points whose distance is at most c*d" 5// (cited srch_ann.raw) for huge speedups over brute force. Reuses R-VEC-0 vr_cos_milli for distance (higher 6// cosine = nearer). HONEST SCOPE: single-layer NSW + ef-beam greedy search; hierarchical layers = the named 7// HNSW extension. Sub-linear because search only walks the graph neighborhood, not all N vectors. 8// 9// exports: vr_nsw_build, vr_nsw_search. license_tier: ORIGINAL 10import "nx_syscalls.nx" 11import "nx_vec_kernel.nx" 12const K_MAGIC_2000000: i64 = 2000000 13 14// add directed edge a->b (dedup, capacity MMAX) 15func nsw_addedge(adj: *i64, deg: *i64, MMAX: i64, a: i64, b: i64) -> i64 { 16 if deg[a] >= MMAX { return 0 } 17 var e: i64 = 0 18 while e < deg[a] { if adj[a*MMAX+e] == b { return 0 } e = e + 1 } 19 adj[a*MMAX+deg[a]] = b; deg[a] = deg[a] + 1; return 1 20} 21 22// build the NSW graph: insert nodes in order; each links (bidirectionally) to its M nearest already-inserted. 23func vr_nsw_build(V: *i64, N: i64, D: i64, M: i64, MMAX: i64, adj: *i64, deg: *i64) -> i64 { 24 var i: i64 = 0; while i < N { deg[i] = 0; i = i + 1 } 25 let cosb: *i64 = sys_mmap(8*(N+2)) as *i64 26 let used: *i64 = sys_mmap(8*(N+2)) as *i64 27 i = 1 28 while i < N { 29 let vi: *i64 = ((V as i64) + i*D*8) as *i64 30 var j: i64 = 0 31 while j < i { let vj: *i64 = ((V as i64) + j*D*8) as *i64; cosb[j] = vr_cos_milli(vi, vj, D); used[j] = 0; j = j + 1 } 32 var lim: i64 = M; if i < M { lim = i } 33 var sel: i64 = 0 34 while sel < lim { 35 var bestj: i64 = 0-1; var bc: i64 = 0-K_MAGIC_2000000 36 var t: i64 = 0 37 while t < i { if used[t] == 0 { if cosb[t] > bc { bc = cosb[t]; bestj = t } } t = t + 1 } 38 if bestj < 0 { sel = lim } else { 39 used[bestj] = 1 40 nsw_addedge(adj, deg, MMAX, i, bestj) 41 nsw_addedge(adj, deg, MMAX, bestj, i) 42 sel = sel + 1 43 } 44 } 45 i = i + 1 46 } 47 return 0 48} 49 50// ef-beam greedy search from `entry`; returns the node id of the best (nearest) found. Buffers caller-provided. 51func vr_nsw_search(V: *i64, N: i64, D: i64, query: *i64, entry: i64, ef: i64, MMAX: i64, adj: *i64, deg: *i64, 52 visited: *i64, res_id: *i64, res_cos: *i64, res_exp: *i64) -> i64 { 53 var i: i64 = 0; while i < N { visited[i] = 0; i = i + 1 } 54 visited[entry] = 1 55 let ve: *i64 = ((V as i64) + entry*D*8) as *i64 56 res_id[0] = entry; res_cos[0] = vr_cos_milli(query, ve, D); res_exp[0] = 0 57 var rn: i64 = 1 58 var guard: i64 = 0 59 while guard < N + 8 { 60 guard = guard + 1 61 var best: i64 = 0-1; var bc: i64 = 0-K_MAGIC_2000000 62 var t: i64 = 0 63 while t < rn { if res_exp[t] == 0 { if res_cos[t] > bc { bc = res_cos[t]; best = t } } t = t + 1 } 64 if best < 0 { guard = N + 8 } else { 65 res_exp[best] = 1 66 let c: i64 = res_id[best] 67 var e: i64 = 0 68 while e < deg[c] { 69 let nb: i64 = adj[c*MMAX+e] 70 if visited[nb] == 0 { 71 visited[nb] = 1 72 let vn: *i64 = ((V as i64) + nb*D*8) as *i64 73 let d: i64 = vr_cos_milli(query, vn, D) 74 if rn < ef { res_id[rn] = nb; res_cos[rn] = d; res_exp[rn] = 0; rn = rn + 1 } 75 else { 76 var mi: i64 = 0; var mc: i64 = res_cos[0]; var u: i64 = 1 77 while u < rn { if res_cos[u] < mc { mc = res_cos[u]; mi = u } u = u + 1 } 78 if d > mc { res_id[mi] = nb; res_cos[mi] = d; res_exp[mi] = 0 } 79 } 80 } 81 e = e + 1 82 } 83 } 84 } 85 var bi: i64 = 0; var bcos: i64 = res_cos[0]; var w: i64 = 1 86 while w < rn { if res_cos[w] > bcos { bcos = res_cos[w]; bi = w } w = w + 1 } 87 return res_id[bi] 88}