Stream deduplication with near-duplicate suppression

A news pipeline receives a stream of headlines and must pass each story on once. First drop exact repeats. Then also drop a headline that is nearly the same as one already passed on, judged by a similarity score against a threshold. Talk through what exact and approximate methods cost as the stream grows.

Part 1: exact duplicates

Unless you agree on a different interface with the interviewer, assume:

• dedupe(stream: Iterable[str]) -> Iterator[str] — yields each string the first time it appears, in order.

Part 2: near duplicates

• dedupe_near(stream: Iterable[str], threshold: float) -> Iterator[str] — also skips a string whose similarity to any string already yielded is at least threshold. Similarity is the Jaccard index of the two strings' sets of lowercase words: size of the intersection over size of the union.

Example

stream = [
  "GPU prices fall as new chips ship",
  "Fed holds rates steady",
  "GPU prices fall as new chips ship",          # exact repeat: dropped in both parts
  "gpu prices fall as new chips ship today",    # 7 / 8 = 0.875 with the first
  "Fed holds interest rates steady",            # 4 / 5 = 0.8 with the second
  "New chips ship",                             # 3 / 7 = 0.43 with the first
]
list(dedupe_near(stream, 0.8))
  -> ["GPU prices fall as new chips ship", "Fed holds rates steady", "New chips ship"]

Constraints

• The stream is unbounded; assume millions of strings a day.
• Comparing every new string with everything kept is O(n) per string: fine for Part 2's first version, not for the follow-ups.

Clarifying questions

• Is "exact" byte-equal, or after normalizing case, whitespace and punctuation?
• Which similarity: word sets, character shingles, embeddings? Is the threshold inclusive?
• Do strings expire (only dedupe against the last 24 hours)?
• Is a false drop (losing a real story) worse than letting a duplicate through?

What a strong answer covers

• Part 1: a set of strings, or of fixed-size hashes to bound memory, and the collision risk that brings.
• Part 2: tokenizing once per string, Jaccard on sets, comparing only with yielded strings.
• MinHash signatures and locality-sensitive hashing (bands) to find candidates in about O(1) per string instead of comparing with all; the false positive and false negative trade-off as bands and rows change.
• Bloom filters for exact dedupe at large scale, and why they can't be used for similarity.
• Expiring old entries with a time window, and tests on hand-made near-duplicate pairs around the threshold.

Follow-ups

• Scale to a billion strings: what lives in memory and what goes to a store?
• Use embeddings and an approximate nearest-neighbour index instead. When is that better?
• Keep the best version of a story (the longest, or from the most trusted source) instead of the first.
• Run across several workers so that two near-duplicates arriving at different workers are still caught.