skip to content

A news feed's scored candidates hold forty near-identical stories on one event - how does the list-editing layer avoid showing ten?

level: middleimportance: must knowfreq 70%

answer

  1. the top ten is one story ten times
  2. cluster first, then select
  3. a tuned similarity threshold, both ways wrong
  4. relevance minus resemblance to what is placed
  5. greedy per slot, on the shortlist only

basics

~20 s

Cluster the near-duplicates first, then select greedily. Content similarity over title and lead text groups the forty filings into one event cluster; the list-editing pass then picks one representative and, using maximal marginal relevance, scores each further slot on relevance minus similarity to what is already placed.

solid answer

~40 s

Two mechanisms, in that order. First **near-duplicate detection**: compare candidates pairwise on their text - shingled title and lead compared by Jaccard similarity, or cosine similarity between content embeddings - and collapse everything above a tuned threshold into one event cluster, keeping the highest-scoring member as its representative. Second **maximal marginal relevance** for the remaining slots: instead of taking the next-highest score, take the candidate maximising `lambda * relevance - (1 - lambda) * maxSimilarity(candidate, alreadyPlaced)`. With `lambda = 1` you reproduce plain top-N; lowering it buys spread at a measured cost in relevance. Both run on the shortlist of a few hundred, not the catalogue, so the pairwise comparisons are affordable.

code

pseudocode · 26 lines
pseudocode
selected = []
pool = shortlist              # a few hundred scored candidates, relevance in [0, 1]
LAMBDA = 0.7                  # 1.0 would reproduce plain top-N by relevance

while length(selected) < SLOT_COUNT and pool is not empty:
    best = none
    bestValue = -infinity

    for each c in pool:
        maxSim = 0
        for each s in selected:
            maxSim = max(maxSim, similarity(c, s))

        if maxSim >= NEAR_DUPLICATE_THRESHOLD:
            continue                       # same story is already on the slate

        value = LAMBDA * relevance(c) - (1 - LAMBDA) * maxSim
        if value > bestValue:
            bestValue = value
            best = c

    if best is none:
        break                              # every survivor duplicates the slate

    append best to selected
    remove best from pool

go deeper

for a junior

Remember that a feed with many outlets covering one event must collapse them before display, and that a plain content hash catches only byte-identical copies.

for a middle

Explain the two steps and their mechanics: similarity-based clustering with a tuned threshold, then greedy selection scoring relevance against resemblance to what is already placed.

for a senior

Show the failure modes you have actually seen - a threshold that buries follow-up stories, stale clusters during a developing event, and a short slate when over-fetching was not budgeted.

for a principal

Treat the diversity knob as a trade with a measurable curve, and decide who owns it and what relevance the business is willing to spend on spread.

## Three different problems wearing one name "Duplicates" in a news feed means three distinct things, and they need different machinery: - **Exact duplicates** - the same article reachable by two URLs, or ingested twice. A content hash catches these before anything is scored. - **Near-duplicates** - the same wire copy republished by twelve outlets with a changed headline. Textually almost identical. - **Same-event coverage** - forty independently written stories about the same event. Textually quite different, but a slate of ten of them is still one story repeated. The ranking stage makes all three worse rather than better: if one story is highly relevant to this reader, every version of it scores highly, so the unedited top ten *is* ten versions of one story. This is why the de-duplication step is a property of the list-editing layer and not a data-quality afterthought. ## Detecting the near-duplicate The standard toolkit, all of it cheap on a shortlist: - **Shingling plus Jaccard similarity**: cut the title and lead paragraph into overlapping word n-grams, and measure the overlap between two candidates' shingle sets. Compact sketches of those sets make the comparison fast enough to do pairwise. - **Cosine similarity over a content embedding**: one vector per article, one dot product per pair. Catches paraphrase that shingling misses. - **Structured event keys**: the same named entities in the same time bucket, or a shared syndication identifier where one exists. Catches same-event coverage that neither text measure reaches, because two independent write-ups share entities but little wording. Each needs a **threshold tuned on labelled pairs**, and the threshold is the whole game. Too tight and a genuine follow-up story - a development on the same event, hours later - gets collapsed into its predecessor and never shown. Too loose and the slate fills with the same story. ## Choosing the representative Once a cluster exists, one member takes the slot. The usual choices, in rough order of how often they are used: 1. The highest relevance score in the cluster - simple, and consistent with the ranker. 2. The original rather than the republication, where provenance is known. 3. The version whose outlet the reader has engaged with before. The rest are not thrown away. A feed typically keeps them behind the representative as a "more coverage" affordance, which is also what makes the collapse defensible to the outlets whose filings did not get the slot. ## Maximal marginal relevance De-duplication removes the obvious repeats; **maximal marginal relevance (MMR)** shapes what is left. At each slot, instead of taking the next-highest scoring candidate, take the one maximising ```pseudocode value(c) = lambda * relevance(c) - (1 - lambda) * max over placed s of similarity(c, s) ``` The first term wants relevance; the second penalises a candidate for resembling anything already on the slate. `lambda = 1` gives plain top-N. Lowering `lambda` widens the slate and costs measured relevance in a way you can plot: it is a tuning knob with a curve behind it, not a boolean. MMR is **greedy** - it fixes each slot before considering the next - so it does not produce the globally optimal diverse set, and it does not try to. Greedy is chosen because it is `O(slots * candidates)` similarity lookups on a shortlist and finishes inside the request budget. ## Where this goes wrong in production - **The slate comes up short.** If every remaining candidate duplicates something already placed, the greedy loop runs out. Over-fetching the shortlist is the defence; a page that renders eight of ten slots is the symptom. - **Similarity computed on titles alone.** Two unrelated stories with formulaic headlines merge; one of them silently never appears. - **Stale cluster assignments.** Clusters computed at ingest go stale as an event develops, so the representative can be an early, now-superseded filing. - **Double penalty.** Running MMR after already collapsing clusters can over-spread the slate, because both mechanisms are pushing the same direction. Tune them together, not separately. - **No logging.** Without a record of which cluster swallowed which candidate, "why was my story not shown" has no answer.

  • What does the near-duplicate threshold cost you when it is set too tight?
    A follow-up story - a real development on the same event, filed hours later - looks textually close to the original and gets collapsed into its cluster, so the reader never sees the update. The failure is silent: the slate looks clean and diverse while the newest information is the thing that was suppressed.
  • Why does the greedy MMR loop run on the shortlist rather than on all retrieved candidates?
    It is quadratic in the wrong direction: each slot compares every remaining candidate against everything already placed. On a few hundred candidates and ten slots that is a few thousand similarity lookups, comfortably inside a request budget; on tens of thousands of retrieved candidates it is not. De-duplication therefore runs after the ranking stage has cut the pool, not before.
  • What happens to the thirty-nine filings that lost the slot?
    They stay attached to their cluster's representative rather than being deleted, which is what lets the surface offer other coverage of the same event behind the placed item. Keeping them also preserves the option to re-pick a representative later in the cycle, when a fuller account of the event supersedes the first filing.

saying these in an interview costs you the question

  • Suggests retraining the ranking model to score duplicates lower
  • Treats a content hash as sufficient for near-duplicates
  • Sets one similarity threshold and never tunes it on labelled pairs
  • Thinks maximal marginal relevance finds the globally optimal set
  • Forgets that removing duplicates can leave the slate short of slots
  • Runs pairwise similarity over the whole retrieved candidate pool