Clustering Duplicate Content with a Greedy Algorithm

One of Buzzvil’s services crawls content from partner publishers and serves it to users.

The collected content inevitably includes overlapping stories. News publishers, in particular, often cover the same topics of the moment, producing similar articles. We therefore need to identify duplicates and choose one representative item to show users.

This involves two steps:

1. Determine which items duplicate one another.
2. Choose a representative from each group of duplicates.

Identifying duplicates and building a graph

Before choosing representative content, we must determine which items overlap.

Duplicate detection itself is not the focus of this post, but our approach can be summarized as follows:

1. Convert each item’s image and text into embedding vectors using appropriate algorithms.
2. Calculate cosine similarity between image embeddings and between text embeddings for all pairs of items.
3. Treat a pair as duplicates if either similarity score exceeds its corresponding threshold.
4. Apply this process across all content pairs.

Once we can decide whether two items are duplicates, their relationships can be represented as an unweighted graph. Each item is a node, and an edge connects two items considered duplicates.

Figure 1. An example graph of duplicate relationships

Clustering duplicates

Once the graph is complete, how should we choose representative content?

This is a form of graph clustering: group nearby nodes and select a representative for each group.

One simple approach would be to place every connected component—all nodes reachable from one another—into a cluster and choose one representative. But that can place an item in the same cluster as a representative it does not actually duplicate.

A familiar Korean children’s song illustrates the problem:

A monkey’s bottom is red.

Red things: apples.

Apples are tasty.

Tasty things: bananas.

Bananas are long.

Long things: trains.

Trains are fast.

Fast things: airplanes.

Airplanes fly high.

High things: Mount Baekdu.

You might accept a connection between a monkey and an apple, and between an apple and a banana. Some people might even accept a similarity between a monkey and a banana. But claiming a monkey is similar to Mount Baekdu is harder to justify.

If every node connected by a path belongs to one cluster, the monkey and Mount Baekdu end up together. A user who has seen the monkey might then never see Mount Baekdu because the system considers it a duplicate.

Hard requirements and softer preferences

To select non-duplicate content efficiently, the clustering algorithm must satisfy two requirements:

1. Every node must either be selected as a representative or be adjacent to a representative.
2. Representatives must not be adjacent to one another.

If we follow these rules, every item can either be shown itself or is a duplicate of something selected to be shown.

We could add one of two policies:

• Create the smallest possible number of clusters—the minimum-representatives principle.
• Create the largest possible number of clusters—the maximum-representatives principle.

Consider only the monkey-to-banana portion of the song:

monkey--apple--banana

To minimize representatives, choose the apple. Both monkey and banana belong to its cluster, yielding one cluster.

(monkey--apple--banana)

To maximize representatives, choose monkey and banana. They are not duplicates of each other, so we get two clusters. Apple can join either cluster. Here it joins monkey:

(monkey--apple)--(banana)

The minimum-representatives policy selects items that duplicate more other items, representing as much content as possible with fewer representatives. The maximum-representatives policy selects items that each represent fewer others, allowing more distinct representatives to reach users.

Finding an algorithm that guarantees either extreme appears difficult. Unless every graph is a simple chain like the song, this becomes a complex combinatorial problem.

Unlike the first two requirements, however, these optimization policies don’t have to be exact. As long as the two hard requirements hold, each item can either be shown or represented by a duplicate that is shown.

We can therefore relax the optional policies into preferences:

• Try to create fewer clusters.
• Try to create more clusters.

Either preference is easy to implement with a greedy algorithm.

The greedy algorithm

For the fewer representatives preference:

1. Select the node with the most edges, designate it as a representative, and create a cluster.
2. Add all its neighboring nodes to that cluster.
3. Remove every node in the cluster and its incident edges from the graph.
4. Repeat until no nodes remain.

For the more representatives preference, change only the first step:

1. Select the node with the fewest edges, designate it as a representative, and create a cluster.

The following figures apply the two variants to Figure 1. Blue nodes are the selected representatives.

Figure 2. Greedy clustering favoring fewer representatives

Figure 3. Greedy clustering favoring more representatives

Batch processing and replacing representatives

New content continually arrives, and every item has a lifespan. Even before it expires, older content appears less frequently because Buzzvil favors fresher material.

We run the clustering process every 30 minutes over content from the previous six hours. That means a representative selected now may lose its place to another item half an hour later.

If we want to prevent that, we can preserve existing representatives and remove their neighboring nodes before running the greedy algorithm on the remaining nodes. Those neighbors are absorbed into the existing representatives’ clusters.

The following graph shows Figure 2 after 30 minutes: new content has arrived and old content has disappeared.

Figure 4. Figure 2 after 30 minutes
Newly arrived content is green.
Dashed nodes have passed the six-hour window and left the graph.

Figure 5. Allowing representatives to be replaced

If replacement is allowed, we get Figure 5: an existing representative can lose its role to another node.

Figure 6. Keeping existing representatives

Without replacement, an item remains a representative once selected, as shown in Figure 6.

If we want to avoid the disruption of representatives changing, we should disallow replacement. If we want the most suitable content to represent a cluster at each moment, we need to allow it.

Possible improvements

Batch clustering has a drawback: new content must wait for the next batch before being classified.

Buzzvil’s current approach

Although duplicate processing runs every 30 minutes, new content does not have to wait 30 minutes to reach users.

Instead of entirely blocking non-representative duplicates, we penalize them so they appear less often. Fresh content also receives an exposure bonus, so a new item does not necessarily appear less frequently than an older representative.

New items therefore receive some exposure before classification, and can gain more if selected as representatives.

Streaming with a metric tree

One way to move from batch to streaming processing is to use a metric tree.

Store the embedding vectors used for duplicate detection in the tree. It can then quickly find items overlapping with newly arrived content and help add new nodes to the duplicate graph.

• If representative replacement is allowed:

  1. Retrieve all content connected by a path to the newly added content.
  2. Apply the greedy algorithm.

• If replacement is not allowed:

  1. Retrieve existing representatives adjacent to the new content.
  2. Absorb new items adjacent to those representatives into their clusters.
  3. Apply the greedy algorithm to the remaining new content.

Without replacement, we need only inspect neighbors of new content. Allowing replacement requires retrieving the entire connected component, which takes longer.

A streaming implementation could also buffer incoming content in a message queue and run clustering whenever the buffer reaches a certain size or a set interval has passed.

Looking back

When I first encountered the duplicate-content problem, I interpreted it as a graph problem and used that to decide our approach. Initially, I defined only the hard requirements and tried to build an algorithm around them. As the approach became complex and time-consuming, distinguishing hard requirements from softer preferences led me to the greedy solution.

We implemented it as a batch process, and running every 30 minutes has delivered satisfactory performance. Still, incoming content is naturally a data stream, so clustering could also be streamed. Pursuing that would require evaluating the supporting metric tree’s performance and deciding how the content queue should behave.