TimeMachine: Timeline Generation for Knowledge-Base Entities

Tim Althoff, Xin Luna Dong, Kevin Murphy, Safa Alai, Van Dang, Wei Zhang

Abstract

As knowledge bases (KBs) like Wikidata and Freebase grow to encompass millions of entities and billions of facts, the challenge of information retrieval shifts from finding data to curating it. We present TimeMachine, a system designed to automatically generate interactive, diverse, and relevant timelines for KB entities. By framing timeline generation as a submodular optimization problem, TimeMachine balances the "interestingness" of events with the necessity for temporal and content variety, significantly outperforming traditional ranking methods in human evaluations.

Introduction

In the era of information abundance, a simple search for a prolific figure like Robert Downey Jr. can yield thousands of timestamped facts. Presenting these as a raw list results in a cluttered and unreadable interface. Effective timeline generation requires sophisticated selection based on three criteria: relevance (prioritizing major milestones), temporal diversity (preventing event clustering to allow for easier navigation), and content diversity (providing a holistic view of a person's life across different domains like career, personal life, and awards).

System Architecture

The TimeMachine pipeline is divided into two primary stages: Candidate Event Generation and Event Selection.

The TimeMachine system architecture, illustrating the transition from offline candidate generation to online event selection.

1. Event Generation and Filtering

The system traverses the KB to identify "events"—paths of length one or two that terminate in a timestamp. This includes simple facts (e.g., birth dates) and compound events (e.g., two actors appearing in the same film). To manage noise, two filters are applied:

  • Frequency Filter: Discards generic paths (e.g., "nationality -> date founded") that are associated with too many entities to be considered personal milestones.
  • Existence Filter: Removes events that fall outside the entity's known lifespan.

2. Submodular Optimization for Selection

The core of TimeMachine is a selection engine that treats timeline generation as a submodular maximization problem. This approach leverages the principle of diminishing returns: once a movie release is selected, the marginal value of adding another movie release decreases, while the value of adding a distinct event type (like a marriage) remains high.

Relevance is calculated using Normalized Pointwise Mutual Information (NPMI) derived from a corpus of 10 billion web documents. To ensure a clean visual layout, the system enforces constraints where no more than n events can overlap in a specific time window. This constraint forms a mathematical structure known as a $p$-system, allowing a greedy algorithm to efficiently find a solution guaranteed to be within 1/3 of the theoretical optimum.

Evaluation and Results

The researchers evaluated TimeMachine using a benchmark of 250 popular entities across various fields, including entertainment, politics, and sports. A user study involving 1,154 participants compared the "Full" TimeMachine model against several ablated versions to measure the impact of specific features.

User preference results (RPref) comparing the full TimeMachine model against various ablated versions (Base, E2D, E2E, TD, CD).

As shown in the results, users consistently preferred the full model in 60% to 91% of pairwise comparisons. Notably, removing Content Diversity (CD)—allowing duplicate event types—was the most detrimental change, with 91.1% of users preferring the diverse version. Similarly, removing Temporal Diversity (TD) led to an 86.7% preference for the spaced-out version, highlighting the importance of visual clarity.

Conclusion and Future Work

TimeMachine demonstrates that diversity in timeline generation is not merely an aesthetic preference but a rigorous mathematical constraint that can be optimized. By combining web-scale co-occurrence data with submodular functions, the system produces high-quality, navigable life stories. Future work will explore moving beyond point-in-time events to include intervals (e.g., a multi-year war) and utilizing abstractive summarization to provide more natural language descriptions of event clusters.

Summary updated

BibTeX
@inproceedings{althoff2015timemachine,
  author = {Tim Althoff and Xin Luna Dong and Kevin Murphy and Safa Alai and Van Dang and Wei Zhang},
  title = {{TimeMachine: Timeline Generation for Knowledge-Base Entities}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2015},
  doi = {10.1145/2783258.2783325},
}
Figure