TL;DR
This paper introduces the first truly streaming system for Cross-Document Coreference Resolution (CDC), enabling it to process massive, unbounded streams of text like social media feeds. By employing novel "informed sampling" techniques that prioritize mentions based on recency, distant references, and entity diversity, they achieve performance within 5% of a non-streaming system while using only 30% of the memory.
What Problem Does This Paper Address?
Coreference resolution (CDC) is the task of identifying mentions (like pronouns or names) that refer to the same real-world entity across multiple documents. Traditional CDC systems often require processing all mentions at once, which is computationally infeasible for massive, continuous data streams such as Twitter feeds or news wire services. These streaming scenarios demand systems that can process each incoming mention in constant time and with a fixed amount of memory. The challenge lies in maintaining enough relevant information from the past to accurately resolve current mentions without being overwhelmed by the sheer volume of data. Simply storing recent mentions can bias the system towards "bursty" entities, while storing everything is impossible.
Methods
The authors propose a streaming CDC system that relies on sampling to manage memory constraints. Instead of storing all mentions, they maintain a fixed-size "sample" of past mentions. The core innovation lies in their informed sampling techniques, which go beyond simple random sampling or fixed-size windows. These techniques consider:
- Recency: Prioritizing more recent mentions, as entities mentioned today are likely to be mentioned tomorrow.
- Distant Reference: Including older mentions to resolve references with long temporal gaps.
- Entity Diversity: Ensuring the sample represents a wide range of entities, not just the most frequently mentioned ones.
They introduce several new sampling strategies, including:
- Cache*: A system that keeps mentions recently used for resolution in a FIFO cache.
- Diversity*: Prioritizes storing mentions from a wider variety of entities.
- Diversity-Cache (D-C)*: A combination of Diversity and Cache, aiming to balance both goals.
These informed techniques leverage the fact that the nearest neighbor in the sample is already computed during the coreference resolution process, making their overhead minimal.
Datasets
The authors collected a dataset of 52 million English tweets from a 1% sample over 77 days. They performed named entity recognition and then annotated a subset of "person" named entity mentions. Specifically, they focused on mentions of "Roger" and "Jessica" (chosen based on frequency) and then all mentions for other entities that contained these names or were related to them. This forms a new annotated Twitter corpus for CDC.
Key Insights and Ideas
- Informed sampling is crucial: Simple strategies like fixed windows or uniform random sampling are insufficient. The system's performance significantly improves when sampling decisions are guided by an understanding of temporal recency, distant references, and entity diversity.
- Streaming discourse matters: The idea that current mentions are influenced by previous ones is key. Sampling techniques that exploit this "streaming discourse" lead to better results.
- Memory efficiency is achievable: The proposed system demonstrates that high performance in streaming CDC doesn't require massive memory. A well-designed sampling strategy can achieve near-optimal results with significantly reduced memory footprints.
- Diversity and Recency are complementary: Combining techniques that promote entity diversity with those that prioritize recency (like the Diversity-Cache method) yields the best performance.
Key Results
The proposed Diversity-Cache (D-C) sampling technique achieved a CEAFe score of 63.9% with a sample size of 78,450 mentions (1.0 days of data). This is within 5% of the performance of an "Exact" system (which stores all mentions, ~66.6% CEAFe) while using only about 30% of the memory. The paper highlights that informed sampling techniques (Cache, Diversity, D-C) significantly outperform uninformed ones (Window, Uniform-R, Biased-R). As sample size increases, the performance gap between different techniques narrows, but informed methods consistently lead.
Limitations and Future Work
The authors acknowledge that their system is a pairwise streaming CDC system using single-link clustering. Future work could explore improving the similarity metric used for coreference, applying these sampling techniques to other streaming problems, or incorporating mention compression alongside sampling.
Summary updated