Online Near-Duplicate Detection of News Articles (2020)

Abstract: Near-duplicate documents are particularly common in news media corpora. Editors often update wirefeed articles to address space constraints in print editions or to add local context; journalists often lightly modify previous articles with new information or minor corrections. Near-duplicate documents have potentially significant costs, including bloating corpora with redundant information (biasing techniques built upon such corpora) and requiring additional human and computational analytic resources for marginal benefit. Filtering near-duplicates out of a collection is thus important, and is particularly challenging in applications that require them to be filtered out in real-time with high precision. Previous near-duplicate detection methods typically work offline to identify all near-duplicate pairs in a set of documents. We propose an online system which flags a near-duplicate document by finding its most likely original. This system adapts the shingling algorithm proposed by Broder (1997), and we test it on a challenging dataset of web-based news articles. Our online system presents state-of-the-art F1-scores, and can be tuned to trade precision for recall and vice-versa. Given its performance and online nature, our method can be used in many real-world applications. We present one such application, filtering near-duplicates to improve productivity of human analysts in a situational awareness tool.

## p the number of static, randomly-generated numbers in permutations, which we use to generate a sketch (of size p) of a document (section 2.2.1). 20 t collision a threshold number of collisions among the values of the sketches of two documents. two documents having more than this many collisions are considered near-duplicate candidates (section 2.2.2). ## f the portion (starting at the beginning) of two potential near-duplicate documents to compare directly (section 2.2.2). 0.4, 0.5, 0.65, 0.8, 1.0 r overlap the threshold minimum ratio of overlap between the n-grams of two potential near-duplicate documents; if the ratio is above this value, the documents are considered to be potential near-duplicates of one-another (section 2.2.2). 0.2, 0.3, 0.4, 0.5 to produce more overlap by chance and larger n-grams tend to be more likely to be unique even when pulled from similar documents (e.g. the larger an n that is considered, the more n-grams are affected by a trivial single-word change in a document); 3-grams and 4-grams tend to be an ideal compromise for most language modelling tasks. we chose a value of k such that, for roughly 90% of our news articles, we are able to sample the entire article, but are intentionally trimming the small number of very long articles down to a more manageable size to increase processing speed. our choice of p permutations was somewhat arbitrary, but the goal was to find the smallest number such that inspecting p n-grams for any random article would give us the gist of what the article was about. we chose t collision by repeatedly ingesting a set of documents and evaluating false positive rates -observing that e.g. two documents sharing only one out of twenty randomly-selected n-grams would happen by chance but be a poor predictor of similarity. we grid-searched values of f by observing that, at one extreme, some news articles (particularly short ones) are composed entirely of "new" news content, while, at the other extreme, some news articles start with a short paragraph of novel news content but end with roughly 60% background or context boilerplate text. we did not have a reasonable linguistically-motivated intuition for how to choose a value for r overlap , so we chose equally-distributed values from 20% to 50% overlap, reasoning that any less than 20% was probably too dissimilar to consider. finally, a note that as our system uses a heuristic-based model for near-duplicate detection (as opposed to a supervised machine learning model), setting these parameters does not induce bias or over-fitting; accordingly, we would expect these to generalize well for other data sets.