Updated July 2026: TraceMind retired its k-d-tree index in v1.3.0; this article now describes the current architecture.
Three tabs deep into a rabbit hole about vector search databases, I was convinced the answer to fast search was a clever data structure. K-d trees, HNSW graphs, inverted file indexes: the literature is full of ways to avoid comparing your query against every stored vector. TraceMind even shipped with one of them for a while.
Then I looked at the actual problem size, did the arithmetic, and deleted it. The short version is this: when TraceMind returns search results in milliseconds across tens of thousands of indexed pages, the reason is not a tree. It is cosine similarity, computed the boring way, over data laid out so the arithmetic is nearly free. Understanding why that works also explains why building fast semantic search inside a browser is easier than the vector-database discourse suggests, at least at personal scale.
The problem: find the closest vectors
TraceMind uses the all-MiniLM-L6-v2 model, which produces a 384-dimensional vector for every page you visit (since v1.7.0 you can also pick a multilingual model in Settings). That's 384 numbers per page. When you search, your query becomes a 384-dimensional vector too, and the task is to find the stored vectors closest to it in that space.
"Closest" needs a definition, and for text embeddings the definition that works is cosine similarity. If you want the full story of where these vectors come from, how vector embeddings work in your browser covers the embedding side.
Cosine similarity, actually explained
Cosine similarity measures the angle between two vectors, not the distance between their endpoints. The formula:
cos(θ) = (A · B) / (||A|| * ||B||)
The numerator is the dot product: multiply the two vectors component by component and sum the results. The denominator normalizes by each vector's length, so only direction matters.
Why direction? Because in embedding space, direction is meaning. A long, rambling article and a short note about the same topic produce vectors pointing the same way; the length of the text nudges magnitude, not orientation. Two vectors pointing the same direction score close to 1. Unrelated ones drift toward 0.
There's a beautiful simplification hiding here. If you normalize every vector to length 1 when you store it, the denominator becomes 1 and cosine similarity collapses to a plain dot product: 384 multiplications and 383 additions. No square roots, no divisions, nothing clever. That is the entire mathematical core of semantic search.
The back-of-envelope math
So how expensive is the "dumb" approach, comparing the query against everything? Let's do the arithmetic.
Say you've indexed 50,000 pages, a heavy year of browsing. Each comparison is a 384-dimensional dot product, roughly 384 multiply-add operations. The full scan:
50,000 vectors x 384 multiply-adds ≈ 19.2 million operations
Nineteen million operations sounds like a lot. It isn't. Modern CPUs execute billions of simple arithmetic operations per second, and this particular workload, sequential reads over a contiguous array with a tight inner loop, is the friendliest thing you can hand to a processor. There's no pointer chasing, no branching, no cache misses to speak of. A scan like this finishes in single-digit to low double-digit milliseconds, which is faster than a single animation frame.
That is the whole trick. O(n) is only scary when n is large. For a personal browser history, n tops out in the tens of thousands, and the constant factor is tiny.
Quantization: making the arithmetic even cheaper
The other half of the story is how the vectors are stored. The model emits 384 floating-point numbers, four bytes each, about 1.5 KB per page. TraceMind quantizes each component down to a single byte before caching, so the whole vector fits in 384 bytes, roughly a quarter of the float footprint.
The vectors are then packed end to end into one contiguous int8 cache. Two things fall out of this:
- Less memory to touch. The scan's speed is bounded by how fast bytes stream out of memory. A quarter of the data means a quarter of the memory traffic.
- Integer dot products. Multiplying small integers is about the cheapest operation a CPU offers, and JavaScript engines optimize tight loops over typed arrays very well.
Quantization does round the numbers, and rounding loses a little precision. For ranking search results it does not matter in practice: the vectors that pointed the same direction before quantization still point the same direction after. You're sorting by similarity, not doing orbital mechanics.
We used to have a k-d tree
Here's the honest part of this story. Earlier versions of TraceMind ran Voy, a Rust k-d tree library compiled to WebAssembly, precisely because we assumed a linear scan wouldn't hold up. A k-d tree recursively splits the dataset along alternating dimensions so a query can prune whole branches without checking them. In 2 or 3 dimensions it is a beautiful structure.
At 384 dimensions, it stops being beautiful. This is the well-known curse of dimensionality: as dimensions grow, the pruning that gives k-d trees their speed stops firing, because almost every branch might still contain a closer neighbor. The tree does a lot of bookkeeping to approximate the scan it was built to avoid.
The browser added a second problem. Chrome extensions on Manifest V3 run under a strict Content Security Policy, and the dynamic code generation that WASM vector libraries lean on needs exactly the permissions that policy withholds. The index path ended up dormant, fragile, and nursed around the security model. In v1.3.0 we removed it and kept the plain scan, which had quietly been doing the real work anyway.
The uncomfortable lesson: the sophisticated structure was solving a problem we didn't have, at a scale we'll never reach, in an environment that resisted it. The dumb loop was exact, CSP-safe, and already fast.
What is Reciprocal Rank Fusion and why use two systems?
I want to spend a moment on RRF because it's genuinely clever and often overlooked.
Pure semantic search is excellent at understanding meaning but can miss exact-match queries. If you search for a specific error code like "ERR_CONNECTION_TIMED_OUT," a semantic model might decide it's conceptually similar to other network errors and return vaguely related results, when what you want is the exact page that mentioned that string.
Pure keyword search (like FlexSearch or BM25) is excellent at exact matches but fails completely on conceptual queries. Search for "slow network response" and it won't find a page that said "high latency connection."
TraceMind runs both, FlexSearch first and then the cosine scan, and RRF combines them. The formula takes each result's rank position in each list and computes a combined score. A document ranked 1st in the semantic list and 5th in the keyword list scores higher than a document ranked 1st in only one list. The result is a merged ranking that captures both precision (keywords) and recall (semantics).
You can see a practical discussion of this approach in semantic search versus keyword search for knowledge workers, which covers the trade-offs from a less technical angle.
Bloom filters: the fast no-result check
One more piece of math worth explaining properly, because its job is narrower than people assume.
A Bloom filter is a probabilistic data structure that answers "could this possibly be in the set?" extremely fast, using very little memory. It doesn't store the actual items, just a compact bit array where bits are set by running items through multiple hash functions.
When you query a Bloom filter:
- If any of the corresponding bits are not set, the item is definitely not in the set.
- If all bits are set, the item is probably in the set (there's a small false positive rate).
TraceMind uses its Bloom filter for exactly one thing: a fast no-result pre-check. Words from your pages are added to the filter during indexing, and when a query arrives, the filter can declare "nothing you've saved could match this" before any heavier search work runs. It is sized for 100,000 elements at a 1% false positive rate with 7 hash functions, around 117 KB of memory for an instant early exit. It is a doorman, not an index; when the filter says "maybe," the real search pipeline does all the actual finding.
The trade-offs are real
I want to be honest about the limitations.
A linear scan has a ceiling. The cost grows with every page you index, and somewhere in the hundreds of thousands to millions of vectors, O(n) per query stops being funny. That is the regime where HNSW graphs and their cousins genuinely earn their complexity, and it's why vector databases exist. A browser history isn't that regime, but it's worth knowing where the cliff is.
Quantization is lossy. The rounding is invisible for ranking, but it is real, and a system that needed exact similarity values would need to keep the floats.
And there's one trade-off we got to delete: approximation. An ANN index returns vectors that are very probably the closest, with a small chance of missing one. Brute force compares against everything, so the results are exact by construction. Retiring the index made search simpler and more correct at the same time, which is not a trade you get offered often.
Why this matters for browser search specifically
Most browser history tools, including Chrome's built-in Ctrl+H, use simple string matching. They're fast because the problem is easy: find pages where the URL or title contains your query string. No ML, no vectors, no dot products.
The reason TraceMind's approach is worth the engineering complexity is that string matching doesn't understand what you were looking for. If you search for "that article about improving JavaScript bundle size," Chrome needs the page title or URL to literally contain those words. TraceMind understands that a page about "webpack code splitting and tree shaking" is exactly what you're looking for.
That understanding, implemented efficiently enough to run in a browser extension, is the whole product. And the thing that makes it fast enough to be usable turned out not to be a tree at all. It's a dot product in a loop, over bytes packed tightly enough that the loop flies.
If you want to see what this looks like in practice, you can try TraceMind on any Chromium-based browser, including Chrome, Brave, and Edge.