nx_phash_index.nx source

1// nx_phash_index.nx -- SUBLINEAR Hamming-metric index (BK-tree) over 64-bit perceptual 2// fingerprints. The reverse-image engine (nx_phash / nx_image_search) ranks by a LINEAR O(N) 3// Hamming scan; that is correct but does not scale to a TinEye-class corpus (10^8..10^10 images). 4// This adds a metric tree that, for the small-radius near-duplicate regime, prunes the candidate 5// set to a SUBLINEAR fraction of N via the triangle inequality -- while returning the EXACT same 6// match set as the linear scan (no recall loss). Integer + deterministic end to end (reuses 7// nx_simhash_hamming = popcount64 of XOR; ZERO new metric math). 8// 9// genealogy_id: burkhard_keller_1973_bk_tree (metric tree) over krawetz_2011 dHash fingerprints 10// 11// WHY a BK-tree: Hamming is a true metric (identity, symmetry, triangle inequality), so for any 12// node on the path |d(q,node) - d(node,child)| <= d(q,child). A radius-r query can therefore skip 13// every child whose edge-distance to its parent lies outside [d-r, d+r]. For clustered corpora 14// (real image collections: near-duplicates + visually-similar groups) this prunes the vast 15// majority of nodes. HONEST: on uniform-random codes at large radius it degrades toward linear -- 16// that regime is the Multi-Index-Hashing rung (Norouzi 2012), the next step up. 17// 18// Layout (caller-owned flat arrays, room for `cap` nodes): fp[i], pay[i], and 65 child slots per 19// node at ch[i*65 + d] (d = Hamming edge distance 0..64 inclusive), each = child node index, or 20// -1 = empty. The caller owns/sizes the arrays so the index composes with any storage tier. 21// license_tier: ORIGINAL 22import "nx_simhash.nx" 23 24const PI_SLOTS: i64 = 65 // Hamming edge distances 0..64 inclusive 25 26// set every child slot to -1 (empty). call once before the first insert. 27func pi_init_children(ch: *i64, cap: i64) -> i64 { 28 var i: i64 = 0 29 let total: i64 = cap * PI_SLOTS 30 while i < total { ch[i] = 0 - 1; i = i + 1 } 31 return 0 32} 33 34// insert fingerprint f (payload p) into the BK-tree currently holding n nodes; returns n+1. 35// fp/pay/ch must have room for >= n+1 nodes and ch must be pre-initialised to -1. Terminates: 36// each step either places f in an empty slot or descends to an existing child (finite acyclic tree). 37func pi_insert(fp: *i64, pay: *i64, ch: *i64, n: i64, f: i64, p: i64) -> i64 { 38 if n == 0 { fp[0] = f; pay[0] = p; return 1 } 39 var cur: i64 = 0 40 var placed: i64 = 0 41 while placed == 0 { 42 let d: i64 = nx_simhash_hamming(f, fp[cur]) 43 let slot: i64 = cur * PI_SLOTS + d 44 let c: i64 = ch[slot] 45 if c < 0 { 46 fp[n] = f; pay[n] = p; ch[slot] = n; placed = 1 47 } else { 48 cur = c 49 } 50 } 51 return n + 1 52} 53 54// radius-r search: append the payload of every node within Hamming r of q to out[0..out_cap), 55// return the match count. out_visited[0] is set to the number of fingerprint comparisons made 56// (the candidate set size) -- the measured-exceed counter vs the linear baseline's N. 57func pi_query(fp: *i64, pay: *i64, ch: *i64, n: i64, q: i64, r: i64, out: *i64, out_cap: i64, out_visited: *i64) -> i64 { 58 out_visited[0] = 0 59 if n <= 0 { return 0 } 60 let stack: *i64 = sys_mmap(8 * (n + 8)) as *i64 61 var sp: i64 = 0 62 var nout: i64 = 0 63 var visited: i64 = 0 64 stack[0] = 0; sp = 1 65 while sp > 0 { 66 sp = sp - 1 67 let cur: i64 = stack[sp] 68 let d: i64 = nx_simhash_hamming(q, fp[cur]) 69 visited = visited + 1 70 if d <= r { if nout < out_cap { out[nout] = pay[cur]; nout = nout + 1 } } 71 var lo: i64 = d - r 72 if lo < 0 { lo = 0 } 73 var hi: i64 = d + r 74 if hi > 64 { hi = 64 } 75 var dd: i64 = lo 76 while dd <= hi { 77 let c: i64 = ch[cur * PI_SLOTS + dd] 78 if c >= 0 { stack[sp] = c; sp = sp + 1 } 79 dd = dd + 1 80 } 81 } 82 out_visited[0] = visited 83 return nout 84}