SimHash: A Whole Document in 64 Bits

The central idea​

A document can contain many words, tokens, or other features. Comparing two complete documents directly may require comparing a large amount of information. SimHash takes a different approach: it compresses the document into one compact fingerprint, described here as a 64-bit value.

The important property is not that the fingerprint preserves every detail. It does not. The purpose is to preserve a useful relationship: documents that are similar should tend to produce fingerprints that differ in only a few bit positions. Documents that are less similar should tend to differ in more positions.

The supplied example focuses on a document with three features. Each feature contributes a hash and a weight. SimHash combines those weighted hashes through a per-bit vote. The resulting votes are folded into a single fingerprint. Once two documents have fingerprints, their similarity can be represented by Hamming distance: the number of bit positions in which the fingerprints differ.

The complete idea can be summarized in six steps:

1. Represent a document using its features.
2. Hash each feature into a fixed-width bit pattern.
3. Give each feature a weight.
4. Let the weighted features vote independently at every bit position.
5. Set each output bit according to the direction of its vote.
6. Compare two fingerprints by counting differing bits.

For a 64-bit SimHash, the final result is one value with $64$ binary positions. The document may contain many features, but its summary has a fixed size.

Why use a fingerprint?​

A fingerprint is useful when the question is about approximate similarity rather than exact equality. Exact equality asks whether two documents are identical. SimHash addresses a different question: do the documents appear similar enough that their compact fingerprints are close?

This distinction matters. If two documents have different wording, additional features, or small changes in feature weights, their complete representations may not be identical. Nevertheless, their weighted evidence can still point in similar directions at many bit positions. SimHash captures that broad agreement in a compact form.

The fingerprint is therefore a summary, not a replacement for the document. It does not retain the original feature list in a readable form. Instead, it preserves a pattern of decisions made independently for each bit. Each decision records whether the positive or negative side of the weighted evidence won at that position.

A 64-bit fingerprint is compact in relation to the amount of input it summarizes. The phrase “whole document in 64 bits” describes this compression: the input can be much larger, while the comparison object remains fixed-width.

That compactness makes comparison simple. Rather than comparing every feature in one document with every feature in another, a comparison can operate on the two fingerprints and their bit differences. The result is a single integer: the Hamming distance.

Features, hashes, and weights​

Suppose a document has three features, which we will call $f_1$, $f_2$, and $f_3$. Each feature is assigned a weight. Let the weights be $w_1$, $w_2$, and $w_3$.

The weights represent how strongly the corresponding features should influence the combined result. The description of SimHash emphasizes a weighted vote, so the weight is not merely decorative. A feature with a larger weight has more influence on every bit position of its hash than a feature with a smaller weight.

Each feature is also mapped to a fixed-width hash. For a 64-bit fingerprint, let the hash of feature $f_i$ be a 64-bit pattern. We can write the hashes of the three features as $h_1$, $h_2$, and $h_3$.

The $j$-th bit of a feature hash is written as $h_{i,j}$. It is either $0$ or $1$. The subscript $i$ identifies the feature, and the subscript $j$ identifies the bit position.

The combination is performed one bit at a time. For bit position $j$, the algorithm examines the $j$-th bit from all three feature hashes and combines their weighted contributions. The document therefore does not receive one undifferentiated vote. It receives one vote calculation for each bit position.

For a 64-bit result, there are $64$ vote positions:

The feature weights are applied consistently across these positions. A feature with weight $w_i$ contributes either positively or negatively at position $j$, depending on whether its hash bit is $1$ or $0$.

Turning a bit into a vote​

A convenient way to express the vote is to interpret a hash bit as a direction. A bit of $1$ contributes in the positive direction, while a bit of $0$ contributes in the negative direction.

For feature $f_i$ at bit position $j$, define its signed contribution as follows:

The total vote at bit position $j$ is then the sum of the signed contributions:

Equivalently, the sum can be written directly in terms of the hash bits:

The expression $2h_{i,j}-1$ converts a binary bit into a sign. If the bit is $1$, the expression becomes $+1$. If the bit is $0$, it becomes $-1$. Multiplying by $w_i$ gives the weighted positive or negative contribution.

After calculating $V_j$, the output fingerprint bit is selected from the sign of the total. A positive total selects $1$, while a negative total selects $0$:

The description gives the core concept as a weighted vote. In an illustrative calculation, it is useful to avoid a tie by choosing weights whose total does not produce zero. If a tie is possible, a concrete implementation must define how that case is handled; the supplied description does not specify a particular tie rule.

The final fingerprint is the sequence of output bits:

This is the folding step. Many feature hashes and their weights are folded into one 64-bit result by reducing the information independently at each bit position.

A small three-feature example​

The real target is a 64-bit fingerprint, but writing all $64$ positions by hand would make the voting process difficult to see. We can use an illustrative 8-bit version to show the same mechanism. The arithmetic and logic are the same; the full version simply repeats the process for $64$ positions instead of $8$.

Consider three features with these weights:

• $f_1$ has weight $3$.
• $f_2$ has weight $2$.
• $f_3$ has weight $1$.

Use these illustrative 8-bit hashes:

f1: 10110010
f2: 10011100
f3: 01110010

The first feature has the greatest influence, the second has a medium influence, and the third has the smallest influence. At each position, translate a $1$ into a positive vote and a $0$ into a negative vote.

For the first bit, the three feature bits are $1$, $1$, and $0$. Their weighted contributions are $+3$, $+2$, and $-1$.

The total is positive, so the first output bit is $1$.

For the second bit, the feature bits are $0$, $0$, and $1$. The contributions are $-3$, $-2$, and $+1$.

The total is negative, so the second output bit is $0$.

For the third bit, the feature bits are $1$, $0$, and $1$. The contributions are $+3$, $-2$, and $+1$.

The output bit is $1$.

Repeating the same calculation for every position gives the complete result. A compact table makes the process visible:

The illustrative fingerprint is therefore:

10110010

This particular output happens to match the first feature in the example, but that is not a general rule. It occurs here because the chosen weights and bit patterns produce that result. The important point is the procedure: the output at each position is determined by the weighted vote, not by copying one feature hash.

For a 64-bit SimHash, replace the eight columns with sixty-four columns. The same three-feature vote is performed at each position, and the sixty-four output decisions form the document fingerprint.

What folding means​

The word “folding” describes the reduction from many feature-level hash bits to one document-level bit at each position. Imagine placing the hash of every feature into a row. For a selected column, all feature hashes contribute a bit. The algorithm converts those bits into signed weighted votes, adds them, and keeps only the winning direction.

The process loses information. After a position is reduced to one output bit, the complete list of individual contributions is no longer present in the fingerprint. This loss is intentional. The result is a compact summary that preserves a useful similarity signal rather than a complete reconstruction of the input.

Folding also explains why weights matter. Without weights, every feature would have the same influence in the vote. With weights, the combined result reflects the relative importance assigned to the features. At any position, a strongly weighted feature can outweigh several weaker opposing contributions, depending on the totals.

For three features, the vote at one position is small and easy to calculate. For a document with many features, the same idea scales conceptually: each feature contributes to each bit position, and the contributions are accumulated before the output bit is selected.

If a document has $m$ features and a fingerprint width of $k$ bits, then there are $k$ vote accumulations, each receiving a contribution from the $m$ features. In symbolic form, the vote for position $j$ is:

For the described 64-bit result, $k=64$. The three-feature example uses $m=3$.

Why similar documents can produce nearby fingerprints​

The similarity behavior comes from shared evidence. Suppose two documents contain many of the same important features. Those shared features contribute the same or similar weighted directions at many bit positions in both documents. As a result, the final vote at those positions is likely to have the same winning direction.

When the winning direction agrees, the corresponding fingerprint bits agree. If this happens across most positions, the two fingerprints differ in only a few places.

The word “similar” does not mean identical. A document may change some features, add features, remove features, or alter feature weights. Such changes can affect some bit votes without necessarily changing every bit. The fingerprints can therefore remain close even though the source documents are not exactly equal.

A useful mental model is a row of $64$ small elections. Each document holds one election per bit position. The feature hashes provide the ballots, and the feature weights determine ballot strength. Two similar documents tend to hold similar elections, so their winning outcomes match in many positions.

This model also explains why a small difference in the input does not automatically imply a large difference in the fingerprint. If the changed feature has little influence at a particular position, or if the other features still produce the same winner, that output bit remains unchanged. A changed feature can affect some positions more than others.

The reverse is also important: a difference in one feature does not guarantee that exactly one fingerprint bit changes. That feature contributes to all bit positions of its hash. Its influence may change several vote outcomes, one outcome, or none, depending on the surrounding weighted totals. The fingerprint records final winners, not a direct list of changed features.

Hamming distance as the comparison​

Once two documents have fingerprints, the comparison can be reduced to bit positions. The Hamming distance between two equal-width bit strings is the number of positions where they differ.

Let fingerprints $A$ and $B$ each contain $k$ bits. Their Hamming distance is:

The bracketed term contributes $1$ when the two bits differ and $0$ when they agree. For a 64-bit SimHash, the distance is an integer from $0$ through $64$.

A distance of $0$ means every bit is equal. A distance of $1$ means exactly one bit differs. A larger distance means more positions disagree. Under the SimHash idea described here, a smaller Hamming distance indicates greater similarity in the fingerprint space.

Consider these illustrative 8-bit fingerprints:

A: 10110010
B: 10100011

Compare the positions from left to right:

A: 1 0 1 1 0 0 1 0
B: 1 0 1 0 0 0 1 1
   = = = x = = = x

There are two differing positions, so:

For 64-bit fingerprints, the same comparison has sixty-four positions. The result remains a simple count, even though the original documents may have contained many features.

Hamming distance can therefore serve as the similarity signal itself, as stated in the description. A system can compare the distance of two fingerprints rather than first reconstructing or directly comparing their complete feature collections. The distance is not a full explanation of why two documents differ; it is a compact measure of how many fingerprint decisions disagree.

From weighted votes to a practical comparison workflow​

A practical conceptual workflow has two phases: fingerprint creation and fingerprint comparison.

Phase one: create a fingerprint​

First, identify the features that represent the document. In the supplied example, there are three features. Assign each feature a weight. Then compute a fixed-width hash for every feature.

Next, create one running vote total for every output bit. For a 64-bit fingerprint, maintain $64$ totals. For each feature, inspect each bit of its hash. Add the feature weight to the corresponding total when the bit is $1$ and subtract the weight when the bit is $0$.

After all features have contributed, inspect each total. A positive total becomes output bit $1$; a negative total becomes output bit $0$, subject to whatever tie convention a concrete implementation defines. Concatenate the output bits to obtain the fingerprint.

The important implementation shape is not a long output string proportional to the document size. It is a fixed set of per-bit accumulators followed by a fixed-width result.

Phase two: compare fingerprints​

To compare two documents, compute or retrieve their two 64-bit fingerprints. Align their bits and count mismatches. The resulting Hamming distance is the comparison value.

For example, if two fingerprints differ at $5$ positions, then their Hamming distance is $5$. If another pair differs at $18$ positions, the first pair is closer according to this measure.

The comparison phase does not need to repeat the feature-level weighted vote if the fingerprints have already been stored. It operates directly on the compact summaries.

The role of the 64-bit width​

The width determines the number of independent output decisions. A 64-bit fingerprint has $64$ positions, and every position receives a vote from the document features.

Using a fixed width gives predictable storage and comparison size. Regardless of whether one input document has a small or large number of features, its final fingerprint still has $64$ bits in the described design.

The width also sets the range of the Hamming distance. For width $k$, the distance satisfies:

For $k=64$:

A larger width provides more bit positions in which two fingerprints can agree or disagree, while a smaller width gives a shorter summary. The supplied description specifically emphasizes a 64-bit fingerprint, so that is the central example here.

The fixed width should not be confused with the amount of information in the original document. A 64-bit result is a compressed representation. Many different documents can map to the same fingerprint or to fingerprints with the same distance. The purpose is approximate comparison, not perfect identification of every possible document.

A second comparison example​

Suppose one document produces the following illustrative 8-bit fingerprint:

D1: 11001010

A second document produces:

D2: 11001110

Only one position differs:

D1: 1 1 0 0 1 0 1 0
D2: 1 1 0 0 1 1 1 0
   = = = = = x = =

Therefore:

Now compare the first document with a third fingerprint:

D3: 00110101

The visual comparison is:

D1: 1 1 0 0 1 0 1 0
D3: 0 0 1 1 0 1 0 1
   x x x x x x x x

Here:

The first pair has a much smaller Hamming distance than the second pair. In SimHash terms, the first pair is the closer pair in fingerprint space.

This example does not claim that a particular numerical distance is universally similar or dissimilar. A concrete application would need to decide how to interpret distances for its own data. The core rule supplied here is that the count of differing bits is the similarity measure.

Why the method is useful for documents​

A document can be represented by a large collection of features. Comparing those collections directly can involve many feature-level details. SimHash changes the comparison object: instead of carrying all feature details into every comparison, it produces one compact fingerprint first.

This approach is attractive when the desired operation is repeated approximate comparison. Once a fingerprint exists, comparing it with another fingerprint means counting bit differences. The original feature hashes and weights are needed to build the fingerprint, but not to perform the basic Hamming comparison between two already-created fingerprints.

The fixed-size representation also gives a consistent language for similarity. Every document becomes a sequence of the same number of bit positions. The comparison no longer depends on the raw length of one document or on the number of features being displayed in the comparison itself.

The method is especially intuitive when the features have meaningful weights. Stronger features can influence the bit votes more heavily, while weaker features have less influence. The output then reflects not merely whether features are present, but how strongly the selected weighting scheme allows them to affect the result.

The process is also easy to describe as a separation between construction and comparison. Construction turns feature-level evidence into a fingerprint. Comparison turns two fingerprints into a distance. Keeping those roles distinct helps explain why the original feature collection is required during fingerprint creation but is not required for the elementary bit-counting step afterward.

What the fingerprint preserves and what it discards​

SimHash preserves a pattern of aggregate decisions. At each bit position, it records which side of the weighted vote won. This is enough to compare fingerprints using Hamming distance.

It discards the detailed explanation behind each decision. Given only the final fingerprint, one cannot generally read off the complete list of features, their hashes, or their weights. Several different collections of contributions can lead to the same winning bit.

This is a normal consequence of compression. The result is valuable because it is small and comparable, not because it is reversible. A fingerprint should therefore be treated as a similarity-oriented summary.

The distinction can be stated precisely:

• The document is the original feature collection.
• The feature hashes are fixed-width representations of individual features.
• The weighted vote combines their bit-level evidence.
• The fingerprint is the final sequence of winning directions.
• The Hamming distance compares two such sequences.

Each stage serves a different purpose. Confusing the stages can lead to incorrect expectations. In particular, a close fingerprint is evidence of similarity under the chosen process, not a claim that the original documents are identical in every respect.

Important reasoning points​

A feature affects every bit position​

A feature hash is a multi-bit pattern. Its weight contributes at each position, with the sign determined by the bit. Therefore, changing one feature can influence several output positions. The outcome at each position still depends on the other feature votes.

The largest weight is influential, not automatically copied​

A feature with the greatest weight has stronger contributions, but the final bit is determined by the total. The output is the result of the complete weighted vote. It is not defined as a copy of the hash belonging to the largest-weight feature.

Similarity is approximate​

The fingerprint compresses many details into $64$ bits. It is designed to make similar inputs land near one another according to Hamming distance, not to preserve every detail or provide a complete identity proof.

Hamming distance is a count​

The distance does not require a separate semantic interpretation for every bit. It simply counts mismatches. For two 64-bit fingerprints, the answer is between $0$ and $64$.

A distance needs context​

The supplied description explains that Hamming distance can be used as the similarity itself. It does not specify a universal cutoff for deciding whether two documents should be considered similar. A cutoff, if needed, belongs to the application using the fingerprints.

The output is not a reconstruction​

The 64-bit result should not be treated as a compact encoded copy of the document. It is a compact record of vote outcomes. The distinction is important: a document can be much richer than its fingerprint, and different documents can produce the same or similarly placed fingerprints.

A compact mathematical summary​

Let a document contain $m$ features. Feature $i$ has weight $w_i$ and a $k$-bit hash whose bit at position $j$ is $h_{i,j}$. Convert each bit into a signed contribution and sum across features:

Choose the output bit from the sign of the vote:

The fingerprint is:

For the 64-bit design, $k=64$. Given two fingerprints $A$ and $B$, compare them using:

The first formula creates the fingerprint. The second measures the distance between two fingerprints. Together they capture the mechanism described by the title and summary: weighted feature hashes are folded into one 64-bit value, and similarity is represented by the number of differing bits.

Final takeaways​

SimHash is best understood as a bit-by-bit weighted voting process.

A document begins as a set of features. Each feature is hashed into a fixed-width bit pattern and assigned a weight. At every bit position, a $1$ contributes positively and a $0$ contributes negatively. The weighted contributions are added, and the sign of the total determines the document's output bit.

Repeating this for all $64$ positions produces the document fingerprint. The original document may be large, but its comparison summary has one fixed width. Similar documents tend to share many of the same weighted influences, so their vote outcomes tend to agree in many positions. Their fingerprints are consequently only a few bits apart.

To compare two fingerprints, count the positions that differ. That count is the Hamming distance. A distance of $0$ means complete bit agreement; a larger distance means more disagreement. The method therefore turns approximate document similarity into a compact, direct comparison between two fixed-size bit patterns.

The most important conceptual boundary is that SimHash is a summary. It does not preserve every feature or provide a reversible copy of the document. Its value lies in making similarity compact and measurable: many feature-level signals go in, one 64-bit fingerprint comes out, and Hamming distance provides the comparison.

When reading or implementing the method, keep the sequence in view: features become hashes, hashes become weighted per-bit votes, votes become fingerprint bits, and fingerprint bits become a Hamming distance. That sequence explains both the strength and the limitation of SimHash. It makes repeated approximate comparisons concise, while deliberately discarding the detailed feature-level information that produced the result.