Semantic and Vector Search

Every mechanism built so far rests on a single assumption: the word in the query is the same string as the word in the document. In the catalog, this assumption often does not hold. A reader searching “tale” cannot see books whose title carries “story.” This is not a scoring problem: for the inverted index there is no link at all between those two strings, so neither field weight nor function-based scoring can bring those documents in — both only change the score of a term that has already matched.

This lesson builds another access method. Every term and every document is represented by a fixed-length sequence of numbers, called an embedding. The closeness of two documents, or of a query and a document, is a measure computed between these two sequences. No word match is sought; numbers are compared. The term “embedding” appears in two senses in this course: in the document model it described one document being embedded inside another; here it is a text’s numeric-sequence form.

Corpus and Building the Embedding

Code	Assumption	Value	Rationale
QR22	fields entering the embedding	title and summary	the subject and author fields do not enter the vector
QR23	context window	the whole document	two terms appearing in the same record count as co-occurring
QR24	embedding dimension	32; the projection comes from the same seed	vectors come out the same on every run
QR25	synonymous pair	“tale” and “story” in the same context, never together in a document	the measured gain comes from this construction, not from the language

QR25 must be stated explicitly: the corpus is generated so that the two synonyms appear with the same neighboring words. The lesson shows this construction’s measurable result; it does not show that an embedding will find every synonym in a language.

// corpus.mjs — library catalog: seeded corpus, inverted index, and scorer.
export const N = 1200, SEED = 20260801, FIELDS = ["title", "summary", "subject", "author"];
let d = SEED;                                             // 32-bit generator, no overflow
export const random = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const pick = (a) => a[Math.floor(random() * a.length)];
const THEMES = [["story|tale", "literature", "short selection collection narrative fiction rural"],
  ["fable", "children's literature", "child illustrated school youth forest sleep"],
  ["history", "history", "ottoman republic archive document chronicle foundation"],
  ["ocean", "travel", "coast fisherman harbor ship island lighthouse"],
  ["mathematics", "science", "geometry number proof theory solution probability"],
  ["poetry", "poetry", "verse collected divan translation selection meter"]]
  .map(([k, subject, a]) => ({ k: k.split("|"), subject, core: a.split(" ") }));
const COMMON = "book volume edition publication review notes introduction glossary".split(" ");
const FIRST_NAMES = "James Emma Simon Nora Kevin Ocean Grace Owen Meredith Blake".split(" ");
const SURNAMES = "Stone Bishop Miller Hayes Reed Frost".split(" ");

export const documents = Array.from({ length: N }, (_, id) => {
  const t = pick(THEMES), draw = t.k[t.k.length > 1 && random() < 0.5 ? 1 : 0], sm = [draw, draw];
  const title = [...new Set([draw, pick(t.core), pick(t.core)])];
  t.core.forEach((s, j) => { if (random() < 1 / (1 + j * 0.42)) sm.push(s); });
  COMMON.forEach((s, j) => { if (random() < 0.55 / (1 + j * 0.28)) sm.push(s); });
  if (random() < 0.5) sm.push(pick(pick(THEMES).core));   // word leaking from another theme
  for (let k = sm.length - 1; k > 0; k -= 1) { const j = Math.floor(random() * (k + 1));
    [sm[k], sm[j]] = [sm[j], sm[k]]; }
  // the subject tag is a publisher decision: a quarter of documents do not match the text's theme
  return { id, title: title.join(" "), summary: sm.join(" "),
    subject: (random() < 0.25 ? pick(THEMES) : t).subject,
    author: `${pick(FIRST_NAMES)} ${pick(SURNAMES)}`, year: 1975 + Math.floor(random() ** 0.6 * 50),
    loans: Math.floor(random() ** 3 * 400) };
});

export const tokenize = (s) => s.toLocaleLowerCase("en-US").match(/[\p{L}\p{N}]+/gu) ?? [];
export function buildIndex(bs) {                          // per-field inverted index
  const idx = {};
  for (const a of FIELDS) {
    const postings = new Map(), lengths = new Float64Array(bs.length);
    for (const b of bs) {
      const ts = tokenize(b[a]), count = new Map();
      lengths[b.id] = ts.length;
      for (const t of ts) count.set(t, (count.get(t) ?? 0) + 1);
      for (const [t, tf] of count) {
        if (!postings.has(t)) postings.set(t, []);
        postings.get(t).push({ id: b.id, tf });
      }
    }
    idx[a] = { postings, lengths, avgLength: lengths.reduce((x, y) => x + y, 0) / bs.length };
  }
  return idx;
}
export function search(idx, query) {      // result list scored with equal field weight
  const terms = tokenize(query), k1 = 1.2, b = 0.75, p = new Map();
  for (const a of FIELDS) for (const t of terms) {
    const g = idx[a].postings.get(t);
    if (!g) continue;
    const idf = Math.log(1 + (N - g.length + 0.5) / (g.length + 0.5));
    for (const e of g) {
      const norm = 1 - b + (b * idx[a].lengths[e.id]) / idx[a].avgLength;
      p.set(e.id, (p.get(e.id) ?? 0) + (idf * e.tf * (k1 + 1)) / (e.tf + k1 * norm));
    }
  }
  return [...p].sort((x, y) => y[1] - x[1] || x[0] - y[0]);
}

Producing a Vector from Context

An embedding is built as follows. For every term, a count is kept of all the terms that appear in the same record; that count is the term’s context. The context vector has the length of the 50-word vocabulary and is reduced to 32 dimensions with a seeded projection. A document’s embedding is the weighted average of its terms’ embeddings. The query goes through the same process, and similarity is the dot product of two unit vectors.

// embedding.mjs — embedding built from term counts, vector access, and hybrid search.
import { documents, buildIndex, search, tokenize, random, N, SEED, FIELDS } from "./corpus.mjs";
const D = 32, idx = buildIndex(documents), fmt = (x) => Math.round(x).toLocaleString("en-US");
const text = (b) => [...new Set([...tokenize(b.title), ...tokenize(b.summary)])];

const df = new Map();                                     // vocabulary: term -> document frequency
for (const b of documents) for (const t of text(b)) df.set(t, (df.get(t) ?? 0) + 1);
const VOCAB = [...df.keys()], pos = new Map(VOCAB.map((t, i) => [t, i]));
const CO = VOCAB.map(() => new Float64Array(VOCAB.length));   // co-occurrence count
for (const b of documents) { const ts = text(b);
  for (const a of ts) for (const c of ts) if (a !== c) CO[pos.get(a)][pos.get(c)] += 1; }

const idf = VOCAB.map((t) => Math.log(N / df.get(t)));
const R = VOCAB.map(() => Float64Array.from({ length: D }, () => (random() < 0.5 ? -1 : 1)));
const normalize = (v) => { let s = 0; for (const x of v) s += x * x; s = Math.sqrt(s) || 1;
  for (let i = 0; i < v.length; i += 1) v[i] /= s; return v; };
const termVec = CO.map((row) => {                         // context counts -> D-dimensional embedding
  const p = new Float64Array(D);
  for (let i = 0; i < row.length; i += 1) if (row[i]) { const w = row[i] * idf[i];
    for (let j = 0; j < D; j += 1) p[j] += w * R[i][j]; }
  return normalize(p);
});
const embeddings = new Float32Array(N * D);                // document embedding: weighted average of its terms
for (const b of documents) { const p = new Float64Array(D);
  for (const t of text(b)) { const v = termVec[pos.get(t)], w = idf[pos.get(t)];
    for (let j = 0; j < D; j += 1) p[j] += w * v[j]; }
  embeddings.set(normalize(p), b.id * D); }
const queryVec = (q) => { const p = new Float64Array(D);
  for (const t of tokenize(q)) if (pos.has(t)) { const v = termVec[pos.get(t)];
    for (let j = 0; j < D; j += 1) p[j] += idf[pos.get(t)] * v[j]; }
  return normalize(p); };
const vectorSearch = (q) => { const s = queryVec(q), r = [];
  for (let i = 0; i < N; i += 1) { let d = 0;
    for (let j = 0; j < D; j += 1) d += s[j] * embeddings[i * D + j];
    r.push([i, d]); }
  return r.sort((a, b) => b[1] - a[1] || a[0] - b[0]); };
const hybrid = (termList, vectorList) => {                 // rank-based fusion, k = 60
  const p = new Map(), add = (l) => l.slice(0, 100).forEach(([id], i) =>
    p.set(id, (p.get(id) ?? 0) + 1 / (60 + i + 1)));
  add(termList); add(vectorList);
  return [...p].sort((a, b) => b[1] - a[1] || a[0] - b[0]);
};

let entries = 0;
for (const a of FIELDS) for (const g of idx[a].postings.values()) entries += g.length;
console.log(`corpus ${N} documents, seed ${SEED}; vocabulary ${VOCAB.length} terms, embedding dimension ${D}`);
console.log(`vector index ${fmt(embeddings.byteLength)} bytes; inverted index ${fmt(entries)} posting ` +
  `entries x 8 bytes = ${fmt(entries * 8)} bytes`);
console.log(`vector scan per query ${fmt(N * D)} multiply-adds; the set column counts the matching ` +
  `document on the term path, and the document with similarity 0.5 or above on the vector path\n`);
const dot = (a, b) => { let s = 0; for (let i = 0; i < a.length; i += 1) s += a[i] * b[i]; return s; };
for (const t of ["tale", "fable"]) {
  const k = VOCAB.map((u, i) => [u, dot(termVec[pos.get(t)], termVec[i])])
    .sort((a, b) => b[1] - a[1]).slice(1, 5);
  console.log(`nearest terms to the "${t}" embedding: ` +
    k.map(([u, d]) => `${u} ${d.toFixed(3)}`).join(", "));
}
console.log(`document 0 embedding's first four components: ` +
  [...embeddings.slice(0, 4)].map((x) => x.toFixed(3)).join(", ") + "\n");
console.log("query".padEnd(13) + "path".padEnd(8) + "set".padStart(7) +
  "top10 term-bearing".padStart(21) + "top10 synonym".padStart(15) +
  "overlap with term top10".padStart(26) + "  top result");
for (const [q, syn] of [["tale", "story"], ["short story", "tale"]]) {
  const termRes = search(idx, q), vecRes = vectorSearch(q), hybRes = hybrid(termRes, vecRes);
  const qTerms = new Set(tokenize(q)), termTop = new Set(termRes.slice(0, 10).map(([id]) => id));
  const threshold = vecRes.filter(([, d]) => d >= 0.5).length;
  for (const [label, list, size] of [["term", termRes, termRes.length], ["vector", vecRes, threshold],
    ["hybrid", hybRes, hybRes.length]]) {
    const top = list.slice(0, 10).map(([id]) => documents[id]);
    const termBearing = top.filter((b) => text(b).some((x) => qTerms.has(x))).length;
    const synonym = top.filter((b) => text(b).includes(syn)).length;
    console.log(q.padEnd(13) + label.padEnd(8) + fmt(size).padStart(7) +
      `${termBearing}`.padStart(21) + `${synonym}`.padStart(15) +
      `${top.filter((b) => termTop.has(b.id)).length}`.padStart(26) + `  ${top[0].title}`);
  }
}

corpus 1200 documents, seed 20260801; vocabulary 50 terms, embedding dimension 32
vector index 153,600 bytes; inverted index 16,216 posting entries x 8 bytes = 129,728 bytes
vector scan per query 38,400 multiply-adds; the set column counts the matching document on the term path, and the document with similarity 0.5 or above on the vector path

nearest terms to the "tale" embedding: story 0.997, fiction 0.893, narrative 0.882, rural 0.853
nearest terms to the "fable" embedding: child 0.882, sleep 0.867, school 0.833, forest 0.813
document 0 embedding's first four components: -0.186, -0.173, -0.118, 0.220

query        path        set   top10 term-bearing  top10 synonym   overlap with term top10  top result
tale         term        108                   10              0                        10  tale rural
tale         vector      580                    5              5                         2  tale narrative short
tale         hybrid      153                   10              0                         5  tale narrative short
short story  term        245                   10              0                        10  story short
short story  vector      608                   10              5                         1  tale narrative short
short story  hybrid      156                   10              0                         4  story narrative short

The first lines make concrete what an embedding is: document 0’s embedding consists of thirty-two decimal numbers, and the first four sit on the screen. The similarity between “tale” and “story” is 0.997 — these two terms never appear together in any document in the corpus; their closeness comes only from appearing with the same neighbors (fiction, narrative, rural). The inverted index holds no measurable relationship at all between these two strings.

What Is Gained, What Is Lost, and Combining the Two

The “tale” query’s three rows are this lesson’s summary. The term path matches 108 documents, and all ten of the top ten genuinely carry “tale”: precision is exact, but not a single document carrying “story” appears — those documents are outside the set, and no weight can bring them in.

The vector path fills five of the top ten with documents carrying “story.” This is the gain, and it is a gain the term path cannot structurally provide. The same row also shows the loss: only five of the top ten carry “tale,” and the number of documents shared with the term path’s top ten has dropped to two. If the librarian is searching for that exact word, five of the rows are of no use.

The set column shows a second difference. In the term path, “matching document” is well defined: 108. There is no such thing in the vector path; every document has a similarity, and the set is chosen only by a threshold. At a threshold of 0.5, 580 documents remain; a threshold of 0.6 would give a different number. In vector search, the boundary of the set does not come from the data — it comes from the chosen threshold.

The “short story” rows show how deep the difference can run: the two paths’ top tens share one common document. Both lists are defensible — one holds the word, the other holds the context — and they are nearly disjoint.

The hybrid rows merge the two lists by rank: each document’s score comes from the inverse of its ranks in the two lists. The result recovers exact matching in the top ten — all ten carry “tale” — and overlap with the term list rises from two to five. But the synonym column drops to zero: the fusion pushes the documents the vector path gained outside the top ten. Hybrid search favors the two lists’ intersection; the gain does not sit in the top ten but deeper in the list. The set narrows too: 153 documents, because only the first hundred documents from each list enter the fusion.

On the cost side there are two numbers. The vector index holds 153,600 bytes, the inverted index 129,728; the vector index grows linearly with document count (a fixed 128 bytes per document), while the inverted index depends on document length and term diversity. The real difference is at query time: the term path reads only the posting lists of the query terms — 108 entries for “tale” — while the vector path touches every document and performs 38,400 multiply-adds. Because there is no such thing as a non-matching document in vector search, there is nothing to eliminate either; shortening the scan requires a separate structure, and this lesson does not build that structure.

Summary

• An embedding is a fixed-length sequence of numbers, and similarity is a measure between two sequences: “tale” and “story” come out at a similarity of 0.997 without ever appearing together in a document, because they appear with the same neighbors.
• In the “tale” query, the term path gives 108 documents and ten exact matches in the top ten; the vector path fills five of the top ten with documents carrying “story,” and the query term is found in only five.
• Vector search has no matching set; the set is chosen by a threshold: 580 documents at a threshold of 0.5.
• Hybrid search recovers exact matching in the top ten (ten of ten) and raises overlap with the term list from two to five, but drops the synonym-bearing documents out of the top ten.
• The vector index is a fixed 128 bytes per document (153,600 total) and wants 38,400 multiply-adds per query by walking the whole corpus; the term path reads only 108 posting entries for “tale.”

Next Step

This topic built the query’s whole surface: query language, matching, filtering, scoring, weight, aggregation, presentation, and finally an access method that compares context instead of the word itself. Under every number measured there is an unstated condition: all of these queries ran in a single process, on a single index. The inverted index fit in one computer’s memory, the scorer read every posting list locally, the aggregation gathered all its buckets in one place, pagination merged shards in the same process, and the vector scan touched every document in sequence. Once the catalog grows to a million records and the index is spread across multiple machines, none of these queries can run the same way: inverse document frequency becomes a number no single machine knows on its own, where a bucket aggregation merges is an open question, and whether the same query gives the same order on two machines is not guaranteed. The next topic takes up distributing the index across machines and what happens to the same query there.