Skip to content

Similarity fingerprints

The Similar Books page compares books by a fingerprint of each source's normalized text. This page records how that fingerprint is built and compared. The code is in internal/sketch; where the fingerprints are stored is in Data format versioning.

The sketch

A fingerprint is a bottom-k MinHash sketch: the k smallest 64-bit hashes of the document's distinct character n-grams ("shingles"). Keeping the k smallest values of one hash function is more accurate and cheaper than the textbook construction with k independent hash functions (Cohen and Kaplan, 2007).

Parameter Value Why
Shingle width n 5 runes Wider shingles separate related from unrelated documents more sharply but weaken the signal; 5 is the measured balance point for book-length prose.
Retained hashes k 128 Bounds the stored size only; building cost is the shingle scan. The Jaccard error is roughly ±0.05.
Exact limit 5000 runes Below this length every shingle is kept instead of a sample: sampling noise would swamp the signal, and exact comparison costs nothing.

Shingles are counted in runes, so the width means the same for CJK text as for alphabetic text; each window is hashed over its bytes.

A sketch also stores the exact number of distinct shingles. Estimating it from the retained hashes instead (KMV cardinality estimation) costs up to 16% error at k = 128, and the exact count is what makes containment algebra rather than estimation. Building streams the text once and keeps only the k smallest hashes, plus a transient set of seen hashes for the exact count.

The stored form is a version byte, the shingle width, the distinct count, the number of retained hashes, and the hashes, all little-endian, base64-encoded in app/fingerprint-cache.json.

Comparing two sketches

Jaccard similarity is the size of the shingle intersection over the size of the union. It is exact when both sketches hold every shingle they counted. Otherwise it is read off the merged sketches below the smaller of their two largest retained hashes, where both still list their document's shingles exhaustively. Sketches built with different widths, and empty sketches, compare as 0.

Containment says how much of one document lies inside the other. With the Jaccard similarity J and the exact distinct counts na and nb, the intersection follows from J = inter / (na + nb - inter), so containment adds no error beyond the error already in J.

Upper bound. Two documents with na and nb distinct shingles cannot have a Jaccard similarity above min(na, nb) / max(na, nb). That is a hard bound on the true value, so one integer comparison rules out a pair whose lengths differ too much, which matters in a library whose documents vary widely in length.