An Improved System for Sentence-level Novelty Detection in Textual Streams

Xinyu Fu, Eugene Ch’ng, Uwe Aickelin, Lanyun Zhang

Introduction

In the era of "Big Data," news cycles move at breakneck speeds across platforms like Twitter and Google News. Identifying the "First Story" (FSD) of an emerging event—such as the onset of an epidemic or a sudden natural hazard—is critical for early warning systems. However, traditional novelty detection systems face two primary hurdles: the vocabulary problem, where static models fail to account for emerging terms, and the scalability problem, where brute-force comparisons are computationally prohibitive for massive streams.

Methodology

The proposed system addresses these challenges by combining Incremental TF-IDF weighting with Locality Sensitive Hashing (LSH).

  • Incremental TF-IDF: Unlike standard models using fixed training sets, this system updates word importance (term frequency and document frequency) as new documents arrive, allowing the vector space model to evolve dynamically with the stream.
  • Locality Sensitive Hashing (LSH): To ensure efficiency, LSH "hashes" similar documents into the same "buckets," limiting novelty checks to local neighborhoods rather than the entire database.
  • Multi-Table Hashing: The researchers introduced a control variable ($L$) to construct multiple hash tables, using a union operator to ensure that "near neighbors" in high-dimensional space are not missed due to hashing collisions.

Experimental Setup

The study utilized a Google News dataset from the "Technology" category (July–August 2012), consisting of 500 training snippets and 1,000 test pieces. Google News was selected for its reliable machine-annotated clusters, which provide a more objective "ground truth" than human-annotated benchmarks like TDT5 or TREC.

Results and Analysis

The system was evaluated using Detection Error Trade-off (DET) curves, which plot miss probability against the false alarm rate. The incremental approach demonstrated a significant performance gain over the static baseline.

Detection Error Trade-off (DET) curves showing the performance of Incremental TF-IDF versus Static TF-IDF and random performance.

As shown in the performance metrics, the miss probability was reduced from 27.1% to 11.6%, representing a roughly 16% improvement in detection accuracy.

Table comparing the miss probabilities of Static and Incremental TF-IDF models.

The false alarm rate also saw a slight reduction from 8.01% to 7.20%. While the incremental model introduces some computational overhead due to constant weight updates, the substantial gain in accuracy justifies the minor loss in operational speed.

Conclusion

This research highlights that dynamic context is essential for effective novelty detection in live streams. By allowing the model to adapt to new vocabulary on the fly, the system achieves much higher sensitivity to first stories. Future work will focus on optimizing the computational cost of incremental updates and validating the system on larger, multi-topic real-time datasets to further address the challenges of Big Data.

Summary updated

Abstract

Novelty detection in news events has long been a difficult problem. A number of models performed well on specific data streams but certain issues are far from being solved, particularly in large data streams from the WWW where unpredictability of new terms requires adaptation in the vector space model. We present a novel event detection system based on the Incremental Term Frequency-Inverse Document Frequency (TF-IDF) weighting incorporated with Locality Sensitive Hashing (LSH). Our system could efficiently and effectively adapt to the changes within the data streams of any new terms with continual updates to the vector space model. Regarding miss probability, our proposed novelty detection framework outperforms a recognised baseline system by approximately 16% when evaluating a benchmark dataset from Google News.
BibTeX
@misc{fu2016improved,
  author = {Xinyu Fu and Eugene Ch’ng and Uwe Aickelin and Lanyun Zhang},
  title = {{An Improved System for Sentence-level Novelty Detection in Textual Streams}},
  year = {2016},
  eprint = {1605.00122},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.00122},
}
Figure