Result Grouping and Near-Duplicate Collapsing

A query about a breaking news event returns, from a large index, twenty results that are the same wire story reprinted on different outlets, distinguished only by a headline and an advertising frame. The reader wants one instance plus an indication that more exist, not twenty lines that are textually identical. The mechanism that compresses those twenty into one is near-duplicate detection applied at result time, and it has to run on every query without a noticeable delay.

The fingerprints are computed at index time

Comparing every pair of results for textual similarity at query time is quadratic in the result set and far too slow. The standard solution computes a fixed-size fingerprint of each document once, at index time, and reduces the query-time problem to comparing fingerprints. The dominant fingerprint for this purpose is the SimHash family, a locality-sensitive hash with the property that the Hamming distance between two fingerprints approximates the similarity between the two documents. A 64-bit fingerprint occupies eight bytes, so an index of a billion documents stores eight gigabytes of fingerprints, which is cheap relative to the documents themselves.

SimHash is computed by hashing each token to a wide value and summing the signed contributions of each bit, so a token that appears in two documents pushes their fingerprints toward each other in exactly the bits where that token hashed to a one. Documents that share most of their tokens land close together in Hamming distance, while unrelated documents do not, even when their fingerprints happen to be near numerically. This is the crucial difference from a cryptographic hash: a plain hash of two near-identical documents differs in about half the bits, while a locality-sensitive hash differs in only a few.

The computation can be written as a running sum. Each token is hashed to a 64-bit value, and for each bit position the fingerprint accumulates plus one where the bit is set and minus one where it is clear; the final fingerprint’s sign at each bit is the majority vote of the tokens:

def simhash(tokens):
    v = [0] * 64
    for t in tokens:
        h = hash_to_64(t)
        for i in range(64):
            v[i] += 1 if (h >> i) & 1 else -1
    return sum((1 << i) for i in range(64) if v[i] > 0)

The result is a 64-bit integer whose distance from another document’s integer reflects the overlap of their token multisets. A document that is a near-duplicate of another, differing only in a boilerplate footer and a headline, shares almost all of its tokens and so lands within a Hamming distance of three or four, the radius the block-matching step is tuned to catch.

Matching fingerprints in Hamming space

The remaining problem is that finding all pairs within a small Hamming distance of a given fingerprint is itself hard over a billion entries. The answer is to split the fingerprint into blocks and require an exact match on at least one block. If two documents are within a Hamming distance of three, then with the 64-bit value split into four 16-bit blocks, at least one block must match exactly, by a pigeonhole argument. The index stores each fingerprint in several tables keyed by block, and a query-time lookup probes the tables for exact block matches, then verifies the full Hamming distance on the short list of candidates.

Manku, Jain, and Das Sarma described this scheme for web crawling and worked out the concrete trade-off between block count, table count, and the false-positive rate. The parameterization is a space-time trade in both directions: more blocks admit a tighter Hamming radius but require more tables and more memory, while fewer blocks reduce memory but admit pairs that are less similar. The interface only cares about the outcome, which is a set of result documents that are near-duplicates of one another.

The pigeonhole argument deserves its exact form, because the whole lookup depends on it. If two fingerprints differ in at most three bits, and the 64-bit value is split into four blocks of sixteen bits, then the three differing bits occupy at most three of the four blocks, leaving at least one block identical between the two fingerprints. A lookup therefore needs only to find fingerprints sharing one block exactly, which an inverted table on block values answers in constant time. The catch is that each fingerprint must be stored in one table per block, four times, so the memory cost is the number of blocks times the fingerprint count, and the query must probe the same number of tables. Four blocks is the smallest split that guarantees a match for distance three, and raising the radius to seven would require eight blocks, doubling the memory and the probe cost for a looser similarity threshold.

Collapsing the list at presentation time

Once the near-duplicate groups are known, the interface applies a presentation rule: one representative per group, with the remaining members either hidden or folded behind an expander. The choice of representative matters. It is conventionally the highest-ranked member under the query’s own scoring, which keeps the collapsed list’s ranking consistent with the flat list it replaces. The grouped members are then shown either as a count or as an indented cluster, so the reader learns that variants exist without having to scan them.

The failure modes are asymmetric. A false negative, two near-identical documents that the fingerprint fails to link, shows the reader duplicates, which is the condition the mechanism was meant to fix. A false positive, two genuinely different documents linked by a coincidental fingerprint match, hides a result the reader might have wanted. The block-matching design biases toward false positives, so implementations verify candidates against the full fingerprint and often against a second, independent hash before declaring a group, spending a small amount of extra work to keep the collapse conservative.

The grouping decision is not binary even after a match is confirmed. Two documents can be near-duplicates of each other but differ enough, in a headline or a date, that a reader cares which one they open, and the interface must decide whether to hide the weaker entirely or to show it behind an expander with the distinction made visible. The choice interacts with the personalization layer downstream, because a hidden variant is one the reader never sees, and hiding it removes it from the click stream that feeds personalization, so an over-eager collapse quietly reduces the signal available to later ranking.

Grouping is the interface’s answer to redundancy in the index. The detection is a locality- sensitive fingerprint computed once and stored compactly; the matching is a pigeonhole decomposition that turns an expensive nearest-neighbour search into a handful of exact block lookups; and the presentation is a one-per-group rule with a chosen representative. Each layer trades something, memory against precision in the fingerprint, precision against recall in the block matching, and compactness against discoverability in the collapse.

The same fingerprinting that groups results also feeds the deduplication the index performs at crawl time, so the mechanism is not only a presentation concern but a shared primitive between crawling and display. A document that is a near-duplicate of one already indexed can be detected by the identical SimHash machinery before it is stored, and the grouping done at query time is then the second application of the same fingerprints, the first having thinned the index itself. This dual use is why the fingerprint is worth computing once and storing compactly: it pays for itself at two stages of the pipeline rather than one.