How does similarity search work — cosine, dot product and Euclidean?

// Three ways to score "how close" a document vector is to a query vector.
// 2-dimensional so you can check every number by hand.
const q = [1, 1];
const docs = { A: [0.9, 0.8], B: [6, 1], C: [0.3, 0.3] }; // A on topic, B long and off-angle, C same angle but short
const sq = (x) => x * x;
const dot = (a, b) => a[0] * b[0] + a[1] * b[1];
const norm = (a) => Math.sqrt(dot(a, a));
const cosine = (a, b) => dot(a, b) / (norm(a) * norm(b));
const euclid = (a, b) => Math.sqrt(sq(a[0] - b[0]) + sq(a[1] - b[1]));
const unit = (a) => a.map((x) => x / norm(a));
const f = (x) => x.toFixed(3);

function table(title, query, set) {
  console.log(title);
  console.log("  doc  cosine  dot     euclid");
  const names = Object.keys(set);
  for (const n of names) console.log(`  ${n}    ${f(cosine(query, set[n]))}   ${f(dot(query, set[n])).padEnd(6)}  ${f(euclid(query, set[n]))}`);
  const by = (score, desc) => [...names].sort((x, y) => (desc ? score(set[y]) - score(set[x]) : score(set[x]) - score(set[y]))).join(" > ");
  console.log(`  ranking by cosine: ${by((v) => cosine(query, v), true)}`);
  console.log(`  ranking by dot:    ${by((v) => dot(query, v), true)}`);
  console.log(`  ranking by euclid: ${by((v) => euclid(query, v), false)}`);
}

table("raw vectors (lengths differ)", q, docs);
const unitDocs = Object.fromEntries(Object.entries(docs).map(([k, v]) => [k, unit(v)]));
table("after scaling every vector to length 1", unit(q), unitDocs);

console.log("identity check on unit vectors: euclid^2 = 2 - 2 * cosine");
for (const [k, v] of Object.entries(unitDocs)) {
  const e2 = sq(euclid(unit(q), v)), rhs = 2 - 2 * cosine(unit(q), v);
  console.log(`  ${k}: ${f(e2)} vs ${f(rhs)}`);
}

// Exact (flat) search vs an IVF index (k-means buckets, probe the closest few).
// Seeded generator so every run and every language prints the same numbers.
let seed = 42;
const rand = () => { seed = (seed * 1664525 + 1013904223) % 4294967296; return seed / 4294967296; };
const gauss = () => { let s = 0; for (let i = 0; i < 12; i++) s += rand(); return s - 6; }; // approx normal, no log/cos
const D = 16, N = 3000, CLUSTERS = 30, LISTS = 30, K = 10, QUERIES = 40;

const centers = [];
for (let c = 0; c < CLUSTERS; c++) { const v = []; for (let d = 0; d < D; d++) v.push(gauss() * 2); centers.push(v); }
const pts = [];
for (let i = 0; i < N; i++) { const c = centers[i % CLUSTERS]; const v = []; for (let d = 0; d < D; d++) v.push(c[d] + gauss() * 2.5); pts.push(v); }
const dist2 = (a, b) => { let s = 0; for (let d = 0; d < D; d++) { const t = a[d] - b[d]; s += t * t; } return s; };
const order = (arr) => arr.sort((x, y) => x[0] - y[0] || x[1] - y[1]); // by distance, then id

// build the IVF index: 5 rounds of k-means, start from evenly spaced points
let cents = []; for (let j = 0; j < LISTS; j++) cents.push(pts[j * 97].slice());
let assign = new Array(N).fill(0);
for (let round = 0; round < 5; round++) {
  for (let i = 0; i < N; i++) { let best = 0; for (let j = 1; j < LISTS; j++) if (dist2(pts[i], cents[j]) < dist2(pts[i], cents[best])) best = j; assign[i] = best; }
  const sum = cents.map(() => new Array(D).fill(0)), cnt = new Array(LISTS).fill(0);
  for (let i = 0; i < N; i++) { cnt[assign[i]]++; for (let d = 0; d < D; d++) sum[assign[i]][d] += pts[i][d]; }
  cents = cents.map((c, j) => (cnt[j] ? sum[j].map((s) => s / cnt[j]) : c));
}
const lists = cents.map(() => []);
for (let i = 0; i < N; i++) lists[assign[i]].push(i);

const queries = [];
for (let qi = 0; qi < QUERIES; qi++) { const c = centers[(qi * 7) % CLUSTERS]; const v = []; for (let d = 0; d < D; d++) v.push(c[d] + gauss() * 3); queries.push(v); }

function exact(q) { return order(pts.map((p, i) => [dist2(q, p), i])).slice(0, K).map((x) => x[1]); }
function ivf(q, nprobe) {
  const near = order(cents.map((c, j) => [dist2(q, c), j])).slice(0, nprobe);
  const cand = []; for (const [, j] of near) for (const i of lists[j]) cand.push([dist2(q, pts[i]), i]);
  return { ids: order(cand).slice(0, K).map((x) => x[1]), work: LISTS + cand.length };
}

console.log(`${N} vectors, ${D} dims, ${LISTS} IVF lists, top-${K}, ${QUERIES} queries`);
console.log("method      distance computations per query   recall@10");
console.log(`flat        ${String(N).padEnd(34)}100.00%`);
for (const nprobe of [1, 2, 4, 8, 16, 30]) {
  let hit = 0, work = 0;
  for (const q of queries) {
    const truth = new Set(exact(q)); const r = ivf(q, nprobe);
    work += r.work; hit += r.ids.filter((i) => truth.has(i)).length;
  }
  const label = `ivf n=${nprobe}`.padEnd(12);
  console.log(`${label}${String(Math.floor(work / QUERIES + 0.5)).padEnd(34)}${((100 * hit) / (QUERIES * K)).toFixed(2)}%`);
}