News Near-Duplicate Detection: Where 3-gram Jaccard and IDF Failed

I collected news with on-device AI. Four of the top eight items were the same story.

It was an article about Jincheon County’s smart-care project. Four outlets—v.daum.net, nbnnews, inews365, and ccdailynews—reported on the same event.

The headlines differed slightly. As a result, the existing deduplication based on exact comparison after headline normalization did not catch them.

A simple Jaccard implementation and an IDF-weighted implementation could not separate false positives with a threshold. After adding a topic gate that compared the leading tokens of headlines, I grouped the same events.

I split by characters instead of words

My first decision was what to use as the comparison unit.

Splitting by whitespace-delimited words was the natural choice. In Korean, it was risky.

스마트 돌봄
스마트돌봄

These mean the same thing, but splitting them into words produces no overlapping tokens. Korean spacing varies by outlet.

So I used character 3-grams. I split the text into overlapping groups of three characters.

스마트돌봄 → 스마트 / 마트돌 / 트돌봄
스마트 돌봄 → 스마트 / 마트  / 트 돌 / " 돌봄"

They were not completely identical, but 스마트 overlapped. This made the method tolerant of spacing variations.

I calculated Jaccard similarity from the sets of 3-grams in two headlines. It was the intersection divided by the union.

I did not run this calculation on every article. There was one inexpensive step first.

Dedupe made two passes. The first merged headlines that were exactly identical after normalization. Outlets that republished wire-service articles unchanged were caught here. There was little cost because it required only string comparison and a map.

The remaining items went through the second pass. These were cases where an outlet had rewritten the sentence.

진천군, 온디바이스 AI 기반 스마트 돌봄 구축 본격 착수
진천군 온디바이스 AI기반 스마트돌봄 본격화

They did not become the same string even after normalization. 구축 본격 착수 and 본격화 differed. Catching these was the purpose of the approximate-duplicate stage.

Filtering exact matches first reduced the input to the second stage. The two stages also failed in different ways. The first only missed duplicates; it did not incorrectly merge them. Only the second could produce incorrect merges.

I examined the distribution with 100 live items

I retrieved 100 results for 온디바이스 AI using the Korean locale and examined the actual distribution.

	Similarity
Same event	0.29 ~ 0.62
Different event	0.02 ~ 0.19

They were generally separated. It looked as though I could draw the line somewhere between 0.2 and 0.29.

Boilerplate inflated similarity

I found two false positives.

0.64  "어드밴트, 온디바이스 AI 서비스 실증·확산 사업 참여"
      "엠젠솔루션, 온디바이스 AI 서비스 실증·확산 사업 참여"

Different companies had participated in the same project. These were different news stories. The similarity was 0.64, higher than the same-event range of 0.29–0.62.

0.46  "경북도, 온디바이스 AI 실증사업 공모 2년째 선정"
      "증평군 온디바이스 AI 실증사업 공모 선정"

These were different local governments. This was also a false positive.

The cause was structural. Most of each headline consisted of the same boilerplate. 온디바이스 AI 실증사업 공모 선정 was shared, while only the subject name at the front differed.

The subject name accounted for only a small portion of the 3-gram sets. 어드밴트 produced three 3-grams, while the remaining common phrase produced more than twenty.

Similarity measured the ratio across the entire string. When the part that distinguished the meaning was short, its difference was buried.

IDF weighting solved only half the problem

My second attempt was to reduce the weights of common 3-grams.

I counted how many documents in the batch contained each 3-gram and assigned lower weights to common ones. This was the same basic idea as IDF in information retrieval.

가중치 = log(1 + 전체 문서 수 / (1 + 그 3-gram이 나온 문서 수))

실증사업 appeared in several articles in the batch, so its weight decreased. 어드밴트 appeared in only one article, so its weight increased. I calculated the weighted Jaccard by using the sum of these weights instead of counts for the intersection and union.

The results separated somewhat.

Pair	Simple Jaccard	IDF weighted	Decision
Gyeongsangbuk-do / Jeungpyeong County	0.31	0.15	Resolved
Advent / Mgen Solution	0.64	0.54	Still high
Jincheon County (true duplicate)	—	0.51	Lower than the false positive

The third row was decisive.

The true-duplicate Jincheon County pair scored 0.51, while the false-positive Advent pair scored 0.54. The false positive scored higher than the true duplicate.

No matter where I placed the threshold, one of them was wrong. At 0.52, I missed the true duplicate; at 0.50, I merged the false positive.

Weighting alone could not separate them.

At this point, I abandoned the direction of making the similarity calculation more sophisticated. The problem was not the accuracy of the similarity score. It was somewhere else.

I used the structure of the headlines

News headlines had a pattern.

어드밴트, 온디바이스 AI 서비스 실증·확산 사업 참여
경북도, 온디바이스 AI 실증사업 공모 2년째 선정
증평군 온디바이스 AI 실증사업 공모 선정

The subject came first, followed by the content. Sometimes there was a comma, and sometimes there was not.

I turned this structure into a gate. If the leading tokens differed, I did not merge the items regardless of their similarity.

Pair	Leading token	Merge
Advent / Mgen Solution	Different	Block
Gyeongsangbuk-do / Jeungpyeong County	Different	Block
Four Jincheon County items	Same	Allow

All three false positives were blocked, while all true duplicates were retained.

Once the gate handled precision, I could lower the threshold

This was the practical benefit of the design.

Without the gate, the threshold had to handle both precision and recall. Raising it caused misses, while lowering it caused incorrect merges.

Once the gate handled precision, the threshold only needed to account for recall. I could lower it aggressively.

I swept the threshold and checked how many of the 100 items remained.

Threshold	Result count
0.45	84
0.40	83
0.35	81
0.30	77

I manually inspected every merged group generated at 0.30. They were three outlets covering Jincheon County’s smart-care project, five covering Nota’s AMD partnership, three covering Hwaseong City’s fire detection project, and two covering Pohang City’s manufacturing demonstration. All four groups were true duplicates. There were no false positives. I adopted 0.30.

I left the rationale in a comment above the constant. It was thirteen lines.

// core-feed/catalog/collect.go:232-245
// Calibrated on 100 live Google News results for "온디바이스 AI" …
// Sweeping downward collapsed 100 items to 84 / 83 / 81 / 77
// at 0.45 / 0.40 / 0.35 / 0.30.
//
// 0.30 is low only because the subject gate carries the precision.
const nearDuplicateThreshold = 0.30

Someone changing that one number should be able to read why it was 0.30. Without the sweep values and manual inspection results, 0.35 would look safer. The final two lines prevented that judgment. The value was low because the gate handled precision; if the gate were removed, this value would also need to be raised.

I did not validate values at or below 0.25. I did not go lower because of the risk of merging different events involving the same subject.

I paid attention to two more implementation details

I bucketed by subject to avoid N² comparisons

Comparing every pair would be quadratic in the number of documents. With 100 items, that meant 4,950 comparisons, and it would become much larger when processing 16 locales in one batch.

If the leading tokens differed, the items could not be merged anyway. So I created buckets by leading token and compared items only within the same bucket.

// core-feed/catalog/collect.go:326-346
for i := range items {
  for _, r := range buckets[leads[i]] {          // 같은 선두 어절만 본다
    if weightedJaccard(grams[i], grams[r], idf) < nearDuplicateThreshold {
      continue
    }
    ...                                          // 대표를 더 나은 쪽으로 교체
  }
  buckets[leads[i]] = append(buckets[leads[i]], i)
}

The bucket key was leadToken. I removed the outlet name at the end of the headline, split on spaces, commas, ·, and colons, and retained only letters and numbers from the first fragment. This made 어드밴트, and 어드밴트 produce the same key.

The key could also be an empty string. That meant the headline had no usable leading token. In that case, the gate did not operate, and items with empty keys were placed in one bucket and compared only by similarity. The gate blocked items when it could and stayed out of the way when it could not.

The gate also served as a performance optimization. A rule added for precision made the number of comparisons roughly linear.

I prevented chain merges with greedy clustering

If A resembled B and B resembled C, should A and C also be merged?

Similarity was not transitive. A and C could be completely different. If I merged transitively, groups could grow without bound.

So I compared each item only with the representative of each group. If A was the representative, B was compared with A, and C was also compared with A. B and C were not compared with each other.

There was a trade-off. Two groups that were actually the same event remained separate.

"진천군 스마트돌봄" 그룹
"진천군 내년까지 어린이집 16곳" 그룹

They were reports about the same project. They were not merged because the similarity between their representatives was below the threshold.

I judged over-splitting to be preferable to over-merging. An incorrect merge caused the user to lose an article. Splitting left one duplicate visible.

I kept the existing rule for which article to retain

When merging, I had to choose a representative. I applied the same rules used for exact-match deduplication.

Rank	Criterion
1	Original outlet rather than a syndicator (v.daum.net, news.naver.com rather than the original)
2	Direct link rather than an opaque link
3	Newest

The second rule was needed because of Google News. Google News links were redirect addresses that concealed the original domain.

I locked it down with four tests and documented three limitations

I wrote four new tests.

Test	What it protected
Merge rewritten reports of the same event	Recall
Keep different subjects (companies and local governments) separate	Precision
Prefer the original outlet during approximate merging	Representative selection
Do not merge unrelated articles	Threshold

The second test protected the core of this work. If someone changed the threshold later and brought back false positives, this test would catch them.

All 36 tests passed. I checked it again with live data.

	Before	After
온디바이스 AI collection	102 items	95 unique
Jincheon County articles	4 items	1 item
Top 8 items	4 were the same event	All different events

I documented three limitations

The 0.30 threshold was calibrated using 100 items from a single Korean topic. I did not verify whether the same value was appropriate for other languages or topics. English news headlines might not follow a subject, content structure, in which case the gate itself would behave differently.

I calculated IDF within each batch. Document frequency became unstable when the batch was very small. In a three-item batch, a 3-gram appearing in two items became common based on that alone. I did not observe a practical problem because the comparison was relative, but this remained a structural weakness.

I did not retain the intermediate outputs from the first two attempts. I deleted the code when I discarded the standalone simple Jaccard and IDF-weighted implementations. If I tried this again in another language, I would have to build them from scratch.