TimeMachine:\\ Timeline Generation for Knowledge-Base Entities
\alignauthor Tim Althoff*
Xin Luna Dong\textsuperscript{\textdagger
\input{000abstract
000abstract.tex
% !TEX root = timelines-paper.tex

We present a method called 
\systemname\
to generate a timeline of events and relations for entities in a knowledge base. 
For example for an actor, such a timeline should show the most important
professional and personal milestones and relationships such as works, awards, collaborations, and family relationships.
We develop three orthogonal timeline quality criteria that an ideal timeline should satisfy:
% We present a method to generate a timeline of events and relations for entities in a knowledge base. 
% For example for an actor, such a timeline should show the most important
% professional and personal milestones and relationships such as works, awards, collaborations, and family relationships.
% We argue that an ideal timeline 
% should satisfy three orthogonal quality criteria:
(1) it shows events that are {\em relevant} to the entity;
(2) it shows events that are {\em temporally diverse}, 
so they distribute along the time axis, avoiding visual crowding
and allowing for easy user interaction,
such as zooming in and out;
and
(3) it shows events that are {\em content diverse},
so they contain many different types of events ({\em e.g.}, for an actor,
it should show movies and marriages and awards, not just movies).
We present an algorithm to generate such timelines for a given time period and screen size,
based on submodular optimization and web-co-occurrence statistics
with provable performance guarantees.
A series of user studies using Mechanical Turk shows 
that all three quality criteria are crucial to produce quality timelines 
and that our algorithm significantly
outperforms various baseline and state-of-the-art methods.


% We present a method to generate a timeline of events for entities in a knowledge base (KB). 
% We argue that an ideal timeline enabling interactive exploration 
% should satisfy three orthogonal quality criteria:
% (1) it shows events that are relevant to the entity;
% (2) visual crowding is avoided to allow for easy interaction
% and (3) it reveals interesting and diverse relationships to other entities.
% We present an algorithm to generate such timelines for a given time period and screen size,
% based on submodular optimization and web-co-occurrence statistics
% with provable performance guarantees.
% A series of user studies using Mechanical Turk shows that our algorithm significantly
% outperforms various simpler approaches.

% In this paper, we focus on four kinds of entities ---
% musicians, actors, politicians and athletes --- and use the Freebase
% knowledge base, but the proposed techniques are general.


%%% old version of oct 29, 2014
% We present a method to generate a timeline of events for entities in a knowledge base (KB). 
% In this paper, we focus on four kinds of entities ---
% musicians, actors, politicians and athletes --- and use the Freebase
% knowledge base, but the proposed techniques are general.
% We argue that an ideal timeline should satisfy three criteria:
% (1) it shows events that are relevant to the entity;
% (2) it reveals interesting and diverse relationships to other entities;
% and (3) it enables further exploration in an interactive way. 
% We present an algorithm to generate such timelines,
% based on submodular optimization and web-co-occurrence statistics
% with provable performance guarantees.
% A series of user studies using Mechanical Turk shows that our algorithm significantly
% outperforms various simpler approaches.
% \todo{this is not parallel to three quality criteria}

% We automatically generate timelines for entities with rich history in KG (music artists, actors, athletes, etc). 
% Ideally, a timeline should (1) show correct events that are relevant to the timeline entity, (2) reveal interesting and diverse relationships to other entities, and (3) enable further exploration in an interactive way. 
% We present an algorithm using submodular optimization based on web-co-occurrence signals. 
% A series of user studies on Mechanical Turk shows that our algorithm significantly outperforms a set of baseline methods.
% \todo{expand}

010introduction_old.tex
% !TEX root = timelines-paper.tex
\enlargethispage{1\baselineskip} % needed to have contributions on pg 1

% [see paper outline for more details]
% motivation
% goal definition
% give example
% highlight challenges
% overview of paper
% contributions
% explain outline

\begin{figure*}[t]
	\centering
%	\includegraphics[width=\linewidth]{timeline_rdjr_full.png}
	% \includegraphics[width=0.8\linewidth]{timeline_rdjr_full.png}
  \includegraphics[width=0.8\linewidth]{timeline_rdjr_full_smaller.pdf}
%  \vspace{-2mm}
	\caption{An example timeline for Robert Downey Jr. (American actor) generated by our proposed approach.
	 Note that the timeline is interactive and displays
         explanations for each event on mouseover
(see Figure~\ref{fig:timeline_rdjr_zoom}).
Furthermore, it can be dynamically zoomed.
}
	\label{fig:timeline_rdjr_full}
  % \vspace{-0.5em}
\end{figure*}

% When querying an entity (such as a person or a movie) on a search
% engine, we are often overwhelmed by the volume and diversity of
% results. Often what we would like to see (especially when using a
% mobile device) is a brief summary of the most
% important facts related to this entity. In many cases, a convenient
% way to present this information is in the form of a timeline, with the
% key events arranged along the horizontal axis,


The volume and diversity of results when querying 
an entity (\eg, person or organization) on a search engine
can be overwhelming.
We argue that in many cases an overview
of the most important events in an organized and readable format
would serve users better,
ideally with interactive
features to enable further exploration.
A timeline with clickable key events arranged 
along a horizontal time axis would serve this need.

%a visualization dating back to the work of Joseph Priestley (1765) and
%William Playfair (1786) \cite{beniger1978quantitative}. 
%An example is shown in
%Figure~\ref{fig:timeline_rdjr_full}.
%(Note that the timeline is interactive, so that when the user mouses
%over an event, some text pops up to give more details. Also, the
%timeline can be adjusted dynamically.)

% Many people are interested in history and learning about other's lives and achievements.
% Current search engines and tools fail at providing good summaries of other individuals' lives.
% Often the best option the user is left is is to go to sites such as Wikipedia.org or biography.com and read through and digest long articles and make up their own mind about what the key events were.
% A standard approach to summarize history as a series of temporal events is to lay them out on a timeline.
% Timelines are usually visualized as a horizontal axis depicting time and displaying individual events along this axis based on when they occurred.
% Such a summarizing visualization is key to learning about a series of events efficiently.
% There is a clear need for timelines to become a core part of the search experience for temporal queries.

In this paper, we develop an approach called 
\systemname\
to automatically generate such
timelines.
The input is a knowledge base (KB) of time-stamped facts, such as
Freebase~\cite{Bollacker08}, 
Wikidata~\cite{Vrandecic2014},
or YAGO~\cite{suchanek2007yago}
(in this paper we use Freebase).
In addition, the user must specify
an entity of interest (\eg, a person).
% (In this paper, we focus on four kinds of entities:
% musicians, actors, politicians and athletes
% but the techniques are general.)
Finally, the user can optionally
specify a 
temporal interval of interest.
(If omitted, we can use a default interval,
such as from the person's date of birth to his or her date of death, or the
current time, whichever comes first.)

The output is a timeline such as the one shown in
Figure~\ref{fig:timeline_rdjr_full}, 
derived for the American actor Robert Downey Jr.
He is best known for his starring roles in the movies
{\em Iron Man} and {\em Avengers}, both of which are shown.
The timeline further depicts various family relationships (father
Robert Downey Sr., ex-wife Deborah Falconer and wife Susan Downey),
important acting roles for his career (the movie {\em Chaplin} and TV
show {\em Ally McBeal}), as well as 
other notable works and professional relationships. 
% \todo{(The images in the timeline come from Freebase.)
% They come from KG (some google service) and not from Freebase.
% }

The timeline is interactive in three ways.
First, when the user hovers over an
image,
we show various details, such as 
 ``Robert Downey Jr. starred in The Avengers, released on
 April 11, 2012''.
Second, the user can specify a particular
    time period, and a new timeline for that period will replace the current one.
    For example, Figure~\ref{fig:timeline_rdjr_zoom} shows the timeline
    for Robert Downey Jr. from 2007 until 2014 
    and gives an example event description.
The zoomed-in version focuses attention on more recent events,
such as his award for {\em Tropic Thunder}
and his role in the {\em Sherlock Holmes} movies.
Finally, the user can click on an entity icon, such as {\em Susan Downey},
    and a timeline for this entity will be displayed. 
    %(if enough interesting events exist for that entity). % Feedback from David: This is kind of implied.

An obvious method for generating such timelines is to select events with highest
global relevance scores (for example, according to a query log). 
%subject to not spreading over the display area. 
However, an empirical study shows that the results are far from satisfactory 
(see Section~\ref{sec:evaluation}).
We argue that high quality timelines should satisfy three orthogonal quality criteria:
%(in addition to being composed of actual correct events):
\begin{enumerate}
% 	\item 
% \kevin{I think we should drop this. It is too trivial/ obvious to be
%   worth mentioning. Also, we need to be consistent with the abstract,
%   that claims there are 3 criteria.}
% Correctness: Only display events that are actually true/correct.

	\item Relevance: Display only the most ``interesting'' or
          ``relevant'' events in an entity's    history.

	\item Temporal Diversity: Distribute events evenly along the
          temporal axis, to avoid visual crowding, and to allow easy
          interaction with the depicted events.

	\item Content Diversity: Display a diverse set of event types
(\eg, for an actor, do not only list the movies they have been in).
% Attempt to provide a diverse
%           representation of the subject's life. For example,  only
%           showing only movies an actor has appeared in is discouraged.
%   \todo{Consider swapping the two diversity categories (but then also
%   in evaluation section) to be parallel to the abstract?} 
\end{enumerate}
While the need for relevance is quite obvious, the
need for temporal diversity and content diversity is less clear.  
We present results from a series of user studies 
(in Section~\ref{sec:evaluation})
that clearly demonstrate the need for these two criteria.

\eat{  These types of interactions require an algorithmic solution that 
  quickly generates a timeline based on user input
  that shows relevant and diverse content
  within a limited amount of space.
  Previous work has introduced timeline generation from KBs 
through visualizing entity-level co-occurrence in news corpora~\cite{mazeika2011entity}, 
displaying events associated with an entity in the YAGO KB~\cite{wang2010timely} 
and generating context-aware timelines from Wikipedia~\cite{tuan2011cate},
  but has not yet considered these types of challenges
  (see Section~\ref{subsec:eval_relevance_signals} for an experimental comparison to the state of the art and Section~\ref{sec:relatedwork} for a discussion of related work).
}

Previous work has introduced timeline generation from knowledge bases %KBs
through visualizing entity-level co-occurrence in news corpora~\cite{mazeika2011entity}, 
displaying events associated with an entity in YAGO ~\cite{wang2010timely} 
and generating context-aware timelines from Wikipedia~\cite{tuan2011cate}.
However, none of them have addressed the challenges raised
by the diversity requirements and enabling user interaction. 
We propose a principled solution based on submodular optimization,
for which we both provide theoretical performance guarantees,
and show empirical evidence of significant improvement over baseline
and state-of-the-art methods.

%\safa{you must substantiate this claim.  Why is it challenging?  Also use the word algorithmically .. automatic 
%in computing is redundant since everything is automatic}Automatically
%generating high quality timelines is very challenging.

In particular,
our approach involves the following two main steps, which are sketched in Figure~\ref{fig:system_overview}.
First, given a subject entity of interest,
we generate as many candidate events as possible
by searching for neighboring entities with timestamps in the given knowledge base.
We generate candidate events for all possibly interesting subjects offline.
% (high coverage and high correctness).
Section~\ref{sec:generation} describes this first step in detail.
% (See Section~\ref{sec:generation} for details.)

Second, given a set of candidates and a time period of interest, we
select (online, or at run time)
a diverse subset of the most relevant events subject to temporal diversity or layout constraints.
% (high relevance, high content diversity, and high temporal diversity). 
% We extract the candidate events from the Freebase knowledge graph.
% Even though it is known that Freebase (and similar 
% \safa{not KB but KG .. I think it is important that this method relies on a graph and not just any Knowledge Base}KBs, such as YAGO)
% is quite incomplete (\safa{delete "in the sense that"}in the
% sense that many mandatory relations between entities are missing)
% \cite{Dong14},
% we show that we can nevertheless extract a large number of candidate
% events for a large number of popular entities.
% The details of this process are 
% described in Section~\ref{sec:generation}.
To do this, we maximize a submodular objective using various
relevance signals based on web co-occurrence, 
subject to these layout constraints.
% (which is more complex than the more standard set
%cardinality constraint).
We prove that our greedy algorithm for optimization
yields close-to-optimal solutions.
In addition, 
our algorithm allows for fast dynamic updates of the timeline based on
user interaction (zooming in or out).
%We choose this two-step approach to enable fast timeline generation for user-defined time spans.
% and for different form factors (e.g. desktop vs mobile).
% (See Section~\ref{sec:selection} for details.)
Section~\ref{sec:selection} describes this second step in detail.

% Kevin added this, just because we have already discussed sec 2-3
% so it feels odd to not discuss the remaining sections
Section~\ref{sec:evaluation} evaluates our proposed algorithm and
compares it to various simpler
baselines and current approaches. Section~\ref{sec:relatedwork} summarizes related work,
Section~\ref{sec:future} discusses future work,
and finally Section~\ref{sec:conclusion} concludes.


%The objective function contains various terms that measure the
%relevance of candidate entitites.
%We propose different relevance signals, based on
%entity-entity and entity-date co-occurrence statistics derived from a large web corpus.
% We present a comprehensive evaluation of our system and the relative
% importance of different parts through a series of large-scale user
% studies on Amazon Mechanical Turk.
% This is described in Section~\ref{sec:evaluation}.

In summary, our main contributions are as follows.
\begin{enumerate}
%interactive timeline search
  \item A design of a timeline search engine that efficiently 
        supports various types of user interaction.
  % \item A design of a timeline search system that allows for 
  %       efficient dynamic modification of timelines 
  %       based on user interaction.

	\item An algorithm for generating entity
          timelines based on submodular optimization
          and web-co-occurrence scores.

% 	\item An efficient way to dynamically modify timelines
% based on user interaction.

	\item An extensive user study of the relative importance of
          different signals for determining entity relevance
          and different notions of diversity.
\end{enumerate}
\vspace{-1.0\baselineskip}

% The remainder of the paper is organized as follows: 
% Section~\ref{sec:generation} details the event candidate generation phase and the second phase, event selection, is described in Section~\ref{sec:selection}. 
% Experimental results are presented in Section~\ref{sec:evaluation}.
% We discuss related work in Section in Section~\ref{sec:relatedwork} before we conclude the paper in Section~\ref{sec:conclusion}.


\begin{figure}[t]
	\centering
	\includegraphics[width=1.0\linewidth]{system_architecture_new_black_newfont.pdf}
%  \vspace{-5mm}
	\caption{System architecture.
{\sc TimeMachine} traverses the KB offline to generate candidate events for 
a subject of interest (\eg, {\em Robert Downey Jr}, represented by Freebase ID {\em /m/016z2j}).
At run time, the user specifies a time period (\eg, {\em 1988--2014}) of interest,
and {\sc TimeMachine} selects a subset of events from the candidates to generate the timeline.
}
	\label{fig:system_overview}
  % \vspace{-0.5em}
\end{figure}



010introduction.tex
% !TEX root = timelines-paper.tex
% \enlargethispage{1\baselineskip} % needed to have contributions on pg 1

% [see paper outline for more details]
% motivation
% goal definition
% give example
% highlight challenges
% overview of paper
% contributions
% explain outline

\begin{figure*}[t]
	\centering
%	\includegraphics[width=\linewidth]{timeline_rdjr_full.png}
	% \includegraphics[width=0.8\linewidth]{timeline_rdjr_full.png}
  \includegraphics[width=0.8\linewidth]{timeline_rdjr_full_smaller.pdf}
 \vspace{-4mm}
	\caption{An example timeline for Robert Downey Jr. (American actor) generated by our proposed approach.
	 Note that the timeline is interactive and displays
         explanations for each event on hover
(see Figure~\ref{fig:timeline_rdjr_zoom}).
Furthermore, it can be dynamically zoomed.
}
	\label{fig:timeline_rdjr_full}
  % \vspace{-0.5em}
\end{figure*}

% When querying an entity (such as a person or a movie) on a search
% engine, we are often overwhelmed by the volume and diversity of
% results. Often what we would like to see (especially when using a
% mobile device) is a brief summary of the most
% important facts related to this entity. In many cases, a convenient
% way to present this information is in the form of a timeline, with the
% key events arranged along the horizontal axis,


% People have been overwhelmed with the amount of information available to them for a long time~\cite{shahaf2012metro}.
% This problem only has become worse ever since the web has brought down barriers for creation and distribution of information.
% Relevant information is often buried in an avalanche of data, and locating it is difficult~\cite{shahaf2012metro}.
% Search engines have attempted to help users locate relevant information~\cite{modern-ir}, 
% but the volume and diversity of results can still be overwhelming,
% even for simple single entity queries (\eg, person or organization)~\cite{shahaf2013information}.

% \enlargethispage{1\baselineskip} % important layout hack

As the web and other technological advancements continue to bring down barriers for creation and distribution of information, 
relevant information is often buried in an avalanche of data, and locating it has become increasingly difficult~\cite{shahaf2012metro}.
Search engines have attempted to address this challenge~\cite{modern-ir}, 
but the volume and diversity of results can still be overwhelming,
even for simple entity queries~\cite{shahaf2013information}.
%
In many such cases, for instance when searching for a person or organization, 
an overview
of the most important events in an organized and readable format 
would serve users better,
ideally with interactive
features to enable further exploration.
A {\em timeline} with clickable key events arranged 
along a horizontal time axis would serve this need~\cite{tuan2011cate}.
% In this paper, we consider the problem of automatically generating such timelines 
% for a given entity (\eg, a person) 
% and optionally a temporal interval of interest.


Automatically generating timelines is very challenging.
To be specific, consider creating a timeline for the American actor Robert Downey Jr.
There are hundreds of possible candidate events and it is infeasible to display all of them.
Robert Downey Jr. is best known for his starring roles in the movies {\em Iron Man} and {\em Avengers}, 
but even for a single movie there are dozens of related events to display (production, release dates, opening, and award ceremonies).
In fact, one should not only focus on movies but provide a more holistic overview of his life and career.
This could include showing various family relationships 
(\eg, father Robert Downey Sr., ex-wife Deborah Falconer, or wife Susan Downey), 
important acting roles for his career (the movie {\em Chaplin} and TV
show {\em Ally McBeal}), 
and other notable works and professional relationships.
However, note that events might be related as well --- if one includes a movie award one might not want to display its release date separately but rather show a more diverse event instead.
Lastly, the timeline should be interactive to enable further exploration. 
% for instance to learn more about his wife.
% Figure~\ref{fig:timeline_rdjr_full} shows the timeline that our system generated for Robert Downey Jr. 

Knowledge bases (KB) of timestamped facts such as 
Freebase~\cite{Bollacker08} 
% Wikidata~\cite{Vrandecic2014},
or YAGO~\cite{suchanek2007yago}
have been used as the source of event information 
%~\cite{wang2010timely,mazeika2011entity,tuan2011cate}
(in this paper we use Freebase).
Previous work has introduced timeline generation from KBs
through visualizing entity-level co-occurrence in news corpora~\cite{mazeika2011entity}, 
displaying events associated with an entity in YAGO~\cite{wang2010timely}, 
and generating context-aware timelines from Wikipedia~\cite{tuan2011cate}.
However, these works did not address the problem of selecting a subset of events but instead displayed all events~\cite{mazeika2011entity,wang2010timely},
or have used a static global ranking that does not capture dependencies between events and is therefore unable to encourage diversity~\cite{tuan2011cate}.
% However, some of these works have not considered the problem of selecting a subset of events but instead displayed all events~\cite{mazeika2011entity,wang2010timely}.
% Others have used a static global ranking that does not capture dependencies between events and is therefore unable to encourage diversity~\cite{tuan2011cate}.
Furthermore, this existing work has not considered challenges raised by enabling user interaction
nor provided an empirical evaluation of the quality of the generated timelines.

\xhdr{Present work} In this paper, we develop an approach called 
\systemname\
to generate a timeline for a given entity of interest.
We develop three orthogonal timeline quality criteria:

\begin{enumerate}
  \item Relevance: Display only the most ``interesting'' or
          ``relevant'' events in an entity's    history.

  \item Temporal Diversity: Distribute events evenly along the
          temporal axis, to avoid visual crowding, and to allow easy
          interaction with the depicted events.

  \item Content Diversity: Display a diverse set of event types
(\eg, for an actor, do not only list the movies they have been in).

\end{enumerate}
% While the need for relevance is quite obvious, the
% need for temporal and content diversity is less clear.  
% We present results from a series of user studies 
% that demonstrate the need for these two criteria.
Consequently, we propose a principled solution to timeline generation according to these criteria based on submodular optimization,
for which we both provide theoretical performance guarantees
and show empirical evidence of significant improvement over baseline
and state-of-the-art methods.

In Figure~\ref{fig:timeline_rdjr_full}, we show that our approach successfully
generates a timeline of relevant events that is diverse both in terms of content and time.
This timeline is also interactive in three ways.
First, when the user hovers over an
image,
we show various details, such as 
 ``Robert Downey Jr. starred in {\em The Avengers}, released on
 April 11, 2012''.
Second, the user can specify a particular
    time period, and a new timeline for that period will replace the current one.
    For example, Figure~\ref{fig:timeline_rdjr_zoom} shows the timeline
    for Robert Downey Jr. from 2007 until 2014 
    and gives an example event description.
The zoomed-in version focuses attention on more recent events,
such as his award for {\em Tropic Thunder}
and his role in the {\em Sherlock Holmes} movies.
Finally, the user can click on an entity icon, such as Susan Downey,
    and a timeline for this entity will be displayed. 



Our approach involves the following two main steps, which are sketched in Figure~\ref{fig:system_overview}.
First, given a subject entity of interest,
we generate as many candidate events as possible
by searching for neighboring entities with timestamps in the given knowledge base (Section~\ref{sec:generation}).
We generate candidate events for all possibly interesting subjects offline.
%Section~\ref{sec:generation} describes this first step in detail.
%
Second, given a set of candidates and a time period of interest, we
select (online)
a diverse subset of the most relevant events subject to temporal diversity or layout constraints (Section~\ref{sec:selection}).
To do this, we maximize a submodular objective using various
relevance signals based on web co-occurrence, 
subject to these layout constraints.
We prove that our greedy algorithm for optimization
yields close-to-optimal solutions.
In addition, 
our algorithm allows for fast dynamic updates of the timeline based on
user interaction (zooming in or out).
%Section~\ref{sec:selection} describes this second step in detail.

We evaluate our proposed algorithm through a series of user studies with 1154 raters and compare it to
various simpler baselines and state-of-the-art approaches (Section~\ref{sec:evaluation}).
Our experiments show that users always significantly prefer our proposed method (60-91\% of timeline comparisons).
Further, we demonstrate that enforcing temporal diversity and content diversity significantly improves the results.


In summary, our main contributions are as follows:
\begin{enumerate}
  \item A design of a timeline search engine that efficiently 
        supports various types of user interaction.

  \item An algorithm for generating entity
          timelines based on submodular optimization
          and web-co-occurrence scores.

  \item An extensive user study of the relative importance of
          different signals for determining entity relevance
          and different notions of diversity.
\end{enumerate}
\vspace{-1.0\baselineskip}



\begin{figure}[t]
  \centering
  \includegraphics[width=.9\linewidth]{system_architecture_new_black_newfont.pdf}
 \vspace{-4mm}
  \caption{System architecture.
    {\sc TimeMachine} traverses the KB offline to generate candidate events for 
    a subject of interest (\eg, Robert Downey Jr.).
    At run time, the user specifies a time period of interest 
    and {\sc TimeMachine} selects a subset of events from the candidates to generate the timeline.
    }
  % \caption{System architecture.
  %   {\sc TimeMachine} traverses the KB offline to generate candidate events for 
  %   a subject of interest (\eg, {\em Robert Downey Jr}, represented by Freebase ID {\em /m/016z2j}).
  %   At run time, the user specifies a time period (\eg, {\em 1988--2014}) of interest,
  %   and {\sc TimeMachine} selects a subset of events from the candidates to generate the timeline.
  %   }
  \label{fig:system_overview}
  % \vspace{-0.5em}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% %a visualization dating back to the work of Joseph Priestley (1765) and
% %William Playfair (1786) \cite{beniger1978quantitative}. 
% %An example is shown in
% %Figure~\ref{fig:timeline_rdjr_full}.
% %(Note that the timeline is interactive, so that when the user mouses
% %over an event, some text pops up to give more details. Also, the
% %timeline can be adjusted dynamically.)

% % Many people are interested in history and learning about other's lives and achievements.
% % Current search engines and tools fail at providing good summaries of other individuals' lives.
% % Often the best option the user is left is is to go to sites such as Wikipedia.org or biography.com and read through and digest long articles and make up their own mind about what the key events were.
% % A standard approach to summarize history as a series of temporal events is to lay them out on a timeline.
% % Timelines are usually visualized as a horizontal axis depicting time and displaying individual events along this axis based on when they occurred.
% % Such a summarizing visualization is key to learning about a series of events efficiently.
% % There is a clear need for timelines to become a core part of the search experience for temporal queries.

% In this paper, we develop an approach called 
% \systemname\
% to automatically generate such
% timelines.
% The input is a knowledge base (KB) of time-stamped facts, such as
% Freebase~\cite{Bollacker08}, 
% Wikidata~\cite{Vrandecic2014},
% or YAGO~\cite{suchanek2007yago}
% (in this paper we use Freebase).
% In addition, the user must specify
% an entity of interest (\eg, a person).
% % (In this paper, we focus on four kinds of entities:
% % musicians, actors, politicians and athletes
% % but the techniques are general.)
% Finally, the user can optionally
% specify a 
% temporal interval of interest.
% (If omitted, we can use a default interval,
% such as from the person's date of birth to his or her date of death, or the
% current time, whichever comes first.)

% The output is a timeline such as the one shown in
% Figure~\ref{fig:timeline_rdjr_full}, 
% derived for the American actor Robert Downey Jr.
% He is best known for his starring roles in the movies
% {\em Iron Man} and {\em Avengers}, both of which are shown.
% The timeline further depicts various family relationships (father
% Robert Downey Sr., ex-wife Deborah Falconer and wife Susan Downey),
% important acting roles for his career (the movie {\em Chaplin} and TV
% show {\em Ally McBeal}), as well as 
% other notable works and professional relationships. 
% % \todo{(The images in the timeline come from Freebase.)
% % They come from KG (some google service) and not from Freebase.
% % }

% The timeline is interactive in three ways.
% First, when the user hovers over an
% image,
% we show various details, such as 
%  ``Robert Downey Jr. starred in The Avengers, released on
%  April 11, 2012''.
% Second, the user can specify a particular
%     time period, and a new timeline for that period will replace the current one.
%     For example, Figure~\ref{fig:timeline_rdjr_zoom} shows the timeline
%     for Robert Downey Jr. from 2007 until 2014 
%     and gives an example event description.
% The zoomed-in version focuses attention on more recent events,
% such as his award for {\em Tropic Thunder}
% and his role in the {\em Sherlock Holmes} movies.
% Finally, the user can click on an entity icon, such as {\em Susan Downey},
%     and a timeline for this entity will be displayed. 
%     %(if enough interesting events exist for that entity). % Feedback from David: This is kind of implied.

% An obvious method for generating such timelines is to select events with highest
% global relevance scores (for example, according to a query log). 
% %subject to not spreading over the display area. 
% However, an empirical study shows that the results are far from satisfactory 
% (see Section~\ref{sec:evaluation}).
% We argue that high quality timelines should satisfy three orthogonal quality criteria:
% %(in addition to being composed of actual correct events):
% \begin{enumerate}
% % 	\item 
% % \kevin{I think we should drop this. It is too trivial/ obvious to be
% %   worth mentioning. Also, we need to be consistent with the abstract,
% %   that claims there are 3 criteria.}
% % Correctness: Only display events that are actually true/correct.

% 	\item Relevance: Display only the most ``interesting'' or
%           ``relevant'' events in an entity's    history.

% 	\item Temporal Diversity: Distribute events evenly along the
%           temporal axis, to avoid visual crowding, and to allow easy
%           interaction with the depicted events.

% 	\item Content Diversity: Display a diverse set of event types
% (\eg, for an actor, do not only list the movies they have been in).
% % Attempt to provide a diverse
% %           representation of the subject's life. For example,  only
% %           showing only movies an actor has appeared in is discouraged.
% %   \todo{Consider swapping the two diversity categories (but then also
% %   in evaluation section) to be parallel to the abstract?} 
% \end{enumerate}
% While the need for relevance is quite obvious, the
% need for temporal diversity and content diversity is less clear.  
% We present results from a series of user studies 
% (in Section~\ref{sec:evaluation})
% that clearly demonstrate the need for these two criteria.

% \eat{  These types of interactions require an algorithmic solution that 
%   quickly generates a timeline based on user input
%   that shows relevant and diverse content
%   within a limited amount of space.
%   Previous work has introduced timeline generation from KBs 
% through visualizing entity-level co-occurrence in news corpora~\cite{mazeika2011entity}, 
% displaying events associated with an entity in the YAGO KB~\cite{wang2010timely} 
% and generating context-aware timelines from Wikipedia~\cite{tuan2011cate},
%   but has not yet considered these types of challenges
%   (see Section~\ref{subsec:eval_relevance_signals} for an experimental comparison to the state of the art and Section~\ref{sec:relatedwork} for a discussion of related work).
% }

% Previous work has introduced timeline generation from knowledge bases %KBs
% through visualizing entity-level co-occurrence in news corpora~\cite{mazeika2011entity}, 
% displaying events associated with an entity in YAGO ~\cite{wang2010timely} 
% and generating context-aware timelines from Wikipedia~\cite{tuan2011cate}.
% However, none of them have addressed the challenges raised
% by the diversity requirements and enabling user interaction. 


% We propose a principled solution based on submodular optimization,
% for which we both provide theoretical performance guarantees,
% and show empirical evidence of significant improvement over baseline
% and state-of-the-art methods.

% %\safa{you must substantiate this claim.  Why is it challenging?  Also use the word algorithmically .. automatic 
% %in computing is redundant since everything is automatic}Automatically
% %generating high quality timelines is very challenging.

% In particular,
% our approach involves the following two main steps, which are sketched in Figure~\ref{fig:system_overview}.
% First, given a subject entity of interest,
% we generate as many candidate events as possible
% by searching for neighboring entities with timestamps in the given knowledge base.
% We generate candidate events for all possibly interesting subjects offline.
% % (high coverage and high correctness).
% Section~\ref{sec:generation} describes this first step in detail.
% % (See Section~\ref{sec:generation} for details.)

% Second, given a set of candidates and a time period of interest, we
% select (online, or at run time)
% a diverse subset of the most relevant events subject to temporal diversity or layout constraints.
% % (high relevance, high content diversity, and high temporal diversity). 
% % We extract the candidate events from the Freebase knowledge graph.
% % Even though it is known that Freebase (and similar 
% % \safa{not KB but KG .. I think it is important that this method relies on a graph and not just any Knowledge Base}KBs, such as YAGO)
% % is quite incomplete (\safa{delete "in the sense that"}in the
% % sense that many mandatory relations between entities are missing)
% % \cite{Dong14},
% % we show that we can nevertheless extract a large number of candidate
% % events for a large number of popular entities.
% % The details of this process are 
% % described in Section~\ref{sec:generation}.
% To do this, we maximize a submodular objective using various
% relevance signals based on web co-occurrence, 
% subject to these layout constraints.
% % (which is more complex than the more standard set
% %cardinality constraint).
% We prove that our greedy algorithm for optimization
% yields close-to-optimal solutions.
% In addition, 
% our algorithm allows for fast dynamic updates of the timeline based on
% user interaction (zooming in or out).
% %We choose this two-step approach to enable fast timeline generation for user-defined time spans.
% % and for different form factors (e.g. desktop vs mobile).
% % (See Section~\ref{sec:selection} for details.)
% Section~\ref{sec:selection} describes this second step in detail.

% % Kevin added this, just because we have already discussed sec 2-3
% % so it feels odd to not discuss the remaining sections
% Section~\ref{sec:evaluation} evaluates our proposed algorithm and
% compares it to various simpler
% baselines and current approaches. Section~\ref{sec:relatedwork} summarizes related work,
% Section~\ref{sec:future} discusses future work,
% and finally Section~\ref{sec:conclusion} concludes.


% %The objective function contains various terms that measure the
% %relevance of candidate entitites.
% %We propose different relevance signals, based on
% %entity-entity and entity-date co-occurrence statistics derived from a large web corpus.
% % We present a comprehensive evaluation of our system and the relative
% % importance of different parts through a series of large-scale user
% % studies on Amazon Mechanical Turk.
% % This is described in Section~\ref{sec:evaluation}.

% In summary, our main contributions are as follows.
% \begin{enumerate}
% %interactive timeline search
%   \item A design of a timeline search engine that efficiently 
%         supports various types of user interaction.
%   % \item A design of a timeline search system that allows for 
%   %       efficient dynamic modification of timelines 
%   %       based on user interaction.

% 	\item An algorithm for generating entity
%           timelines based on submodular optimization
%           and web-co-occurrence scores.

% % 	\item An efficient way to dynamically modify timelines
% % based on user interaction.

% 	\item An extensive user study of the relative importance of
%           different signals for determining entity relevance
%           and different notions of diversity.
% \end{enumerate}
% \vspace{-1.0\baselineskip}

% % The remainder of the paper is organized as follows: 
% % Section~\ref{sec:generation} details the event candidate generation phase and the second phase, event selection, is described in Section~\ref{sec:selection}. 
% % Experimental results are presented in Section~\ref{sec:evaluation}.
% % We discuss related work in Section in Section~\ref{sec:relatedwork} before we conclude the paper in Section~\ref{sec:conclusion}.


% \begin{figure}[t]
% 	\centering
% 	\includegraphics[width=1.0\linewidth]{system_architecture_new_black_newfont.pdf}
% %  \vspace{-5mm}
% 	\caption{System architecture.
% {\sc TimeMachine} traverses the KB offline to generate candidate events for 
% a subject of interest (\eg, {\em Robert Downey Jr}, represented by Freebase ID {\em /m/016z2j}).
% At run time, the user specifies a time period (\eg, {\em 1988--2014}) of interest,
% and {\sc TimeMachine} selects a subset of events from the candidates to generate the timeline.
% }
% 	\label{fig:system_overview}
%   % \vspace{-0.5em}
% \end{figure}



015problem.tex
% \begin{figure*}[t]
%   \centering
%   \includegraphics[width=\linewidth]{timeline_rdjr_zoom.png}
%   \caption{An example timeline for Robert Downey Jr,
% where we have zoomed in on the most recent years of his life.
% }
%   \label{fig:timeline_rdjr_zoom}
%   % \vspace{-0.5em}
% \end{figure*}

\smallskip
\noindent
{\bf System design:}
We envision a system called {\sc AboutTime} to support search for the timeline of important events
related to a particular subject. For this paper we assume both the subject and the events on
the timeline come from a {\em knowledge base (KB)}, such as {\em Freebase}~\cite{freebase}.
The KB contains a set of {\tt (subject, predicate, object)} triples
in the RDF format. We leave the problem of history extraction 
from the Web for future research.

When a user specifies a subject such as 
{\em Robert Downey Jr.}, {\sc AboutTime} would show a timeline as in 
Figure~\ref{fig:timeline_rdjr_full} for his life period (\ie, from his birth date 
to his death date or ``now''). 
The timeline consists of a set of {\em events}, each associated with a representing
entity and a timestamp. For each entity the timeline shows a picture icon 
of a fixed width and height; how to select the picture is orthogonal to our problem
and in practice we use the picture specified in {\em Freebase}. 
The picture icons should never overlap; one may stack on top of another if needed.
\eat{For simplicity we use a layout strategy called {\em Order-Layout}, where we 
(1) order the entities by their time stamp, 
(2) put each entity on the timeline according to its timestamp, 
and (3) stack one entity on top of another if putting them on the
same layer would overlap the icons.}
The timeline allows three types of interactions.
\begin{itemize}
  \item {\em Showing details:} When a user hovers the mouse over an entity icon,
    such as {\em The Avengers}, details will be displayed for the event such as 
    {\em ``Robert Downey Jr. starred in The Avenger, released on 2012/04/11''.}
  \item {\em Zooming in and out:} The user can slide the time bar to specify a particular
    time period, and a new timeline for that period will replace the current one.
    For example, Figure~\ref{fig:timeline_rdjr_zoom} shows the timeline
    for {\em Robert Downey Jr.} from 2007 up to now.
  \item {\em Jumping to another entity:} The user can click on an entity icon, such as {\em Susan Downey},
    and a timeline for this entity will be displayed if that entity also has a ``history''.
\end{itemize}

\smallskip
\noindent
{\bf Problem definition:}
The core problem to support timeline search is to generate a timeline for a given subject
and a given time period, fitting in a particular screen area with a given width and height. 
We formally define the problem as follows.

\begin{definition}[Timeline Generation]
Let $\cal K$ be a knowledge base and $\tt s$ be a subject in $\cal K$.
Let $[T_1, T_2]$ be a time period. Let $W$ and $H$ be the width and height
of a screen box, and $w$ and $h$ be the width and height of
a picture icon. The {\em Timeline Generation} problem generates
a timeline with a set $\bf E$ of events such that
\begin{itemize}
  \item each event $e \in \bf E$ represents a historical event for $\tt s$,
    is associated with a representing entity (maybe $\tt s$ itself) in $\cal K$,
    and happens at time $t({\tt s}, e) \in [T_1, T_2]$;
  \item the picture icons of size $h$x$w$ for events in $\bf E$ can fit in the screen of size $H$x$W$.
\end{itemize}
\end{definition}

Note that this definition skips three pieces of details.
The first is about which event represents a historical event for $\tt s$.
In general it should happen at a particular time in a person's life 
and Section~\ref{subsec:event_generation} gives our criteria.
The second is about how the picture icons can fit in a screen. This depends on the strategy
we lay out the icons and Section~\ref{subsec:temporal_constraint} discusses the details.
The third is about which set of events form the best timeline. In general 
we have three requirements and Section~\ref{subsubsec:entity_relevance} gives the formal metric.
\begin{itemize}
  \item {\em Relevance:} event $e \in \bf E$ should be highly relevant to $\tt s$ 
    in search and in Web articles.
  \item {\em Content diversity:} the events in $\bf E$ should have different
    types (\eg, publishing an album vs. starring in a movie).
  \item {\em Temporal diversity:} the events in $\bf E$ are fairly evenly
    distributed along the timeline.
\end{itemize}

\smallskip
\noindent
{\bf Architecture and overview:}
Figure~\ref{fig:system_overview} depicts the architecture for timeline generation. 
We solve the problem in two steps. First, at offline time
the {\em Candidate Event Generation} component takes the KB 
and a subject as input, identifies the set of all historical events 
from the KB; for each event, it generates the representing entity and
a timestamp. The results should have high {\em correctness} and {\em coverage}.
Section~\ref{sec:generation} describes how we traverse the knowledge base 
for candidate generation. To obtain a high coverage, we consider not only
direct relationship such as {\em Robert Downey Jr. stared in movie 
The Avengers}, but also indirect relationship such as {\em Robert Downey
Jr. and Chris Evans co-star in The Avengers} (Section~\ref{subsec:event_generation}). 
To obtain a high correctness, we filter paths that are over-common in the KB 
or violate certain constraints (Section~\ref{subsec:event_filtering}). 

Second, the {\em Event Selection} component takes as input a particular
time period at runtime,  selects from the candidates a set of events to construct the timeline.
The selected events should be {\em relevant, diverse}, and satisfy
the layout constraint. Section~\ref{sec:selection} formalizes the problem
as an optimization problem, where the objective function captures the
relevance and diversity, and the constraint captures the layout restriction
(Section~\ref{subsec:timeline_optimization}). It then proves that the objective
function is {\em submodular} and the constraint forms an {\em independence family}
(we give the definition later), leading to a greedy algorithm with an approximation
guarantee (Section~\ref{subsec:optimization_algorithm}).



020generation.tex
% !TEX root = timelines-paper.tex


Recall from Figure~\ref{fig:system_overview} that there are two main steps: 
candidate event generation and event selection.
In this section, we describe how we generate candidate events
given a subject of interest. 
Our approach is to generate a large set of events, and then
to filter out ``irrelevant'' ones. We give an evaluation of this
filtering step. This is a necessary preparation step for 
our key contribution in this paper (described in the following section):
dynamically selecting a subset of the remaining events at runtime,
depending on the time span of interest and the available screen real estate.

% This section describes how we traverse the KB to generate candidate events (Section~\ref{subsec:event_generation})
% and how we filter irrelevant events (Section~\ref{subsec:event_filtering}).
% Section~\ref{subsec:candidate_generation_evaluation_results} gives an evaluation 
% of the coverage and correctness of the output of this offline step.




\subsection{Event Generation}
\label{subsec:event_generation}

\begin{figure}[t]
	\centering
	\includegraphics[width=0.8\linewidth]{candidate_generation_new.pdf}
   \vspace{-1mm}
	\caption{An illustration of the event candidate generation step.
  Events are short paths that are associated with a timestamp.
}
	\label{fig:event_generation}
  % \vspace{-0.5em}
\end{figure}


%%% HACK: moving figure here so it appears on earlier page.
\begin{figure*}[t]
  \centering
  % from:
  % file:///Users/tim/Dropbox/2014_google_timelines_project/google_files_bkp/cns_html_bkp_small/version-temp2/G2E-E2E-E2D-EmphasisE2E/timeline__m_016z2j.html
%  \includegraphics[width=\linewidth]{timeline_rdjr_zoom_hover.png}
  % \includegraphics[width=0.8\linewidth]{timeline_rdjr_zoom_hover.png}
    \includegraphics[width=0.8\linewidth]{timeline_rdjr_zoom_hover_smaller.pdf}
 \vspace{-4mm}
  \caption{An example timeline for Robert Downey Jr.,
where we have zoomed in on the most recent years of his life.
Note the description for the Sherlock Holmes event (award nomination) that gets displayed on hover.
}
  \label{fig:timeline_rdjr_zoom}
  % \vspace{-0.5em}
\end{figure*}



We can consider the KB as a graph with nodes representing subjects and objects,
and edges representing the relationship (predicate) between the nodes.
%The event generation phase relies on a knowledge \safa{replace "base" with "graph" .. method is specific to a graph}base of facts.
%We assume the \safa{replace "KB" with "KG"}KB is stored as a set of (subject, predicate, object) triples,
%following the RDF format using by the semantic web community.
%The corresponding multigraph has nodes which correspond to subjects/objects, and
% edges which represent the relationship (predicate) between the two nodes.
Given a particular subject represented by a node $N_s$ in the KB, we are interested in nodes
that are connected to $N_s$ through some paths and are associated with
a timestamp; we call such paths ``events''.
As we discuss below, we consider two kinds of events: simple and
compound.
% \kevin{I propose changing ``history x history'' to ``compound''.}
Figure~\ref{fig:event_generation} illustrates the overall process for Robert Downey Jr.


\xhdr{Simple events}
Simple events are nodes with timestamps that can be reached by paths of length one or two starting at $N_s$.
In the example in Figure~\ref{fig:event_generation}, we
can traverse along an edge of type {\em date-of-birth},
and reach a node representing the corresponding date; this is a path
of length one (1-hop event).
We can also traverse along an edge of type {\em starred-in}, and reach
the node representing the movie {\em The Avengers}. To find the corresponding date, we traverse
along a second edge of type {\em release-date} and reach a node with
the release date of the movie. This is a path of length two.
% \footnote{ 
% %
% Note that because of the existence of {\em Compound Value Type} in knowledge bases 
% such as {\em Freebase}, the process can be a bit more complex
% %; we skip the technical details in this paper. 
% than this, as explained in Section~\ref{sec:CVT} (impl. details).
% }
% \eventtwohop{sub1}{p1}{re1}{p2}{t}
%\newcommand{\eventtwohop}{4}{#1 \overset{#2}{\longrightarrow} #3\overset{#4}{\longrightarrow} #4}

We can formally represent a simple event (derived from a path of
length two) as follows:
%\eventtwohop{$s$}{$p_1$}{$re_1$}{$p_2$}{$t$}
 $\sub
 \overset{p_1}{\longrightarrow}re_1
 \overset{p_2}{\longrightarrow} t$,
where  $\sub$ is the subject,
$re_1$ is a related entity (such as {\em The Avengers}),
$t$ is the timestamp, and $p_1$ and $p_2$ are the predicates along the path.
For simplicity, we represent 1-hop events in a similar way, by
introducing a self-loop through
 $p_1 = \mathit{self}$ and $re_1 = \sub$.
For each event $e$, we define the {\em subject} of the event as $\subFun(e) = \sub$, 
the {\em related entity} as $\reFun(e) = re_1$,
the {\em timestamp} as $\tFun(e) = t$, 
the {\em entity path} as $\pathtore{e} = p_1$,
and the {\em time path} as 
$\pathtots{e} = p_1.p_2$.

%where sub is the timeline subject, $re_1$ is the related entity (\eg, {\em The Avengers}),
%t is the associated timestamp, and $p_1$ and $p_2$ are the connecting predicates.




%\subsubsection{History x History Expansion Step}
%\label{subsubsec:historyXhistory}

\xhdr{Compound events}
Extracting only simple events will
miss out on some implicit connections to other related entities.
For example, consider the collaboration
between Robert Downey Jr. and Samuel L Jackson in the movie {\em The Avengers} shown
in Figure~\ref{fig:event_generation}.
Even though there is no direct edge between Robert Downey Jr. and Samuel L Jackson, 
they are connected through a path as they starred in the same movie.

We can discover such connections as follows.
Suppose
we have simple events $\sub_1 \overset{p_1}{\longrightarrow}re_1 \overset{p_2}{\longrightarrow} t$ 
and
$s_2 \overset{p_3}{\longrightarrow}re_1 \overset{p_2}{\longrightarrow} t$,
which share the same related entity and timestamp,
but differ in their first hops. We join these events to generate
a new compound event
$e = \bfrac{\sub_1
  \xrightarrow{p_1}}{\sub_2
  \xrightarrow[p_3]{}} re_1
\xrightarrow{p_2} t$.
%which we call HxH {\em events}, short for history-cross-history.
We treat $\sub_2$ as another related entity $re_2$ for $\sub_1$, and vice versa; in other words, 
$\reFun(e) = re_2 = \sub_{2}$,
and
$\pathtore{e} = p_1.p_3$.
For a discussion of implementation details please refer to the appendix of the full version of this paper~\cite{althoff2015fullpaperarxiv}.

%Before we apply this HxH step we filter out irrelevant candidate events as described in Section~\ref{subsec:event_filtering}  to avoid multiplication of irrelevant events.


\xhdr{Event descriptions}
To ensure an event can be understood by an end-user when they hover
over the corresponding box on the timeline, we have to
convert these paths 
into natural language form.
We do this by manually defining some templates 
%(e.g., ``$\sub$ married $re_1$ on date $t$'')
for the 100 most frequently occurring paths
% resulting in proper English sentences for all commonly shown event types
(see Figure~\ref{fig:timeline_rdjr_zoom} for an example).
For the remaining paths, we simply concatenate the English names of the
corresponding predicates and entities.


% % Candidate for removal for space.
% \xhdr{Implementation details}
% \label{sec:CVT}
% The KB used in this paper, Freebase, uses Compound Value Type (CVT) nodes 
% as a way to represent n-ary relations in triple form.
% (In the semantic web community, CVTs are known as ``blank nodes''.\footnote{
% See \url{http://en.wikipedia.org/wiki/Blank_node}.})
% Such CVTs reify the n-ary relation itself as a node;
% each property of this CVT node corresponds to one of the slots in the n-ary relation.
% For example, the event that Robert Downey Jr starred in {\em The Avengers} while playing the role of {\em Iron Man} is represented by the following triples:
% \begin{eqnarray*}
% /m/Robert  & \xrightarrow{/film/actor/film} & \texttt{CVT} \\
% \texttt{CVT}  & \xrightarrow{/film/performance/character} & /m/IronMan\\
% \texttt{CVT}  & \xrightarrow{/film/performance/film} & /m/Avengers
% \end{eqnarray*}
% This representation makes the movie more than one hop away from the actor,
% and therefore makes the process outlined above a bit more complex.
% To address this, we ``collapse'' the CVT nodes by replacing each path 
% $a \xrightarrow{p_1} \texttt{CVT} \xrightarrow{p_2} b$ 
% by a single edge 
% $a \xrightarrow{p_1.p_2} b$. 

% The second issue  that CVTs raise can 
% be illustrated through the following example.
% When a musician plays for a band, this event is represented by a CVT,
% which captures the role he played (\eg, singer or drummer),
% the name of the band,
% and the date he joined.
% If two musicians play for the same band, their corresponding CVTs will have different IDs.
% This will break the above compound event heuristic.
% We solve this issue by replacing the CVT ID by the ID of the corresponding band.
% More generally, we replace a CVT ID by following the predicate that leads to the most diverse 
% set of entities in the knowledge base (\eg, we use the band ID not the less diverse role ID).
% Formally, for each ``incoming'' predicate $p_1$ we choose the ``outgoing'' predicate $p_2^*$ such that
% $$
% p_2^*(p_1) = \argmin_{p_2} \max_{b} |\{ b \;|\; \exists a,\texttt{CVT} : e = a \xrightarrow{p_1} \texttt{CVT} \xrightarrow{p_2} b \}|.
% $$



% % Note that the second issue is different from the first one since here we are interested in the timestamp from the CVT (e.g. joined/left the band) whereas in the first case the relevant timestamp is connected to an entity connected to the CVT node (e.g. the movie release date).
% % In practice, we found that the process described was both necessary and sufficient to cover all relevant events (that existed in the incomplete knowledge base).


%Let $E$ be the set of all generated events for a given subject of interest.
\eat{
\smallskip
In summary, given an entity {\tt s}, we consider two types of events.
A {\em simple event} $e \in E$ has the form
$s \overset{p_1}{\longrightarrow}re_1 \overset{p_2}{\longrightarrow} t$;
and an {\em HxH event} has the form
$\bfrac{s \xrightarrow{p_1}}{re_2 \xrightarrow[p_3]{}} re_1 \xrightarrow{p_2} t$.
For a simple event, we have
For an HxH event, everything is the same except that
$\reFun(e) = re_2$,
and
$\texttt{PathToRE}(x) = p_1.p_3$.
}


% We now define some notation for the generated candidate events that will be useful in Section~\ref{sec:selection}. 
% Let $E$ be the space of all generated events where events $e \in E$ have either the form
% $sub \overset{p_1}{\longrightarrow}re_1 \overset{p_2}{\longrightarrow} t$ 
% or the form
% $\bfrac{sub \xrightarrow{p_1}}{re_2 \xrightarrow[\texttt{p}_\texttt{3}]{}} re_1 \xrightarrow{p_2} t$ as in the HxH case.
% We then define $\subFun(x) = sub$, 
% $\reFun(x) = re_1$ in the former case and 
% $\reFun(x) = re_2$ in the latter, 
% $\tFun(x) = t$, 
% $\texttt{PathToRE}(x) = p_1$ in the former case and 
% $\texttt{PathToRE}(x) = p_1\texttt{.p}_\texttt{3}$ in the latter, 
% and $\texttt{PathToTS}(x) = p_1\texttt{.p}_2$.


% \pagebreak[4] %otherwise alone
\vspace{-.5\baselineskip}
\subsection{Event Filtering}
\label{subsec:event_filtering}
The event generation steps we have just described may generate some irrelevant events.
For example, it can discover a path {\em ``nationality $\rightarrow$ date founded''},
so everyone with nationality {\em USA}
has a candidate event with timestamp {\em July 4, 1776},
the date on which the USA was founded.
However, arguably this event is irrelevant to most people,
since it is not specific to them, and it occurred well before many of them were born.\footnote{
%
% Even for {\em George Washington}, a founding father of the USA,
% it is safe to eliminate the {\em ``nationality $\rightarrow$ date founded''} path,
% as he is connected to the USA and its foundation date in
% several other ways.
Even for George Washington, a founding father of the USA,
it is safe to eliminate the {\em ``nationality $\rightarrow$ date founded''} path,
as there are other paths connecting him to the USA and its foundation date.
} %
We propose two simple heuristics that capture these intuitions
and filter out many irrelevant events.


The {\em Frequency Filter} uses the concept of {\em inverse document frequency}~\cite{modern-ir} 
from the IR community. The idea is that an event that is commonly associated 
with a large number of subjects is unlikely to be particularly interesting.
To formalize this, consider the set of all events $(s,re,\pi_t,t)$.
Let $N(\pi_t, re, t)$ be the number of subjects that are connected to $re$ and $t$ through path $\pi_t$, 
and let $N(\pi_t)$ be the number of distinct $(re, t)$ pairs that are connected to any subject via $\pi_t$.
% and let $N(\pi_t)$ be the total number of events with path $\pi_t$.
Furthermore, let $C(\pi_t)=|\{(re, t) : N(\pi_t, re, t) > \theta_1 \}|$ be the number of $(re, t)$ pairs for which there are more than $\theta_1$ subjects connected through path $\pi_t$. 
% Let $N(\pi_t,re,t)$ be the number of subjects $s$ that are connected to $re$ and $t$ through path $\pi_t$,
% and let $N(\pi_t)$ the total number of events of type $\pi_t$.
% Further, let $C(\pi_t) = \sum_{(re,t)} \mathds{1}(N(\pi_t,re,t) > \theta_1)$ 
% the number of $(re,t)$ pairs for which we have more than $\theta_1$ subjects connected through path $\pi_t$ (``complaints'').
Then for any given path $\pi_t$, if $C(\pi_t) / N(\pi_t) > \theta_2$, where
$\theta_2$ is some threshold, we drop that path for all subjects. 
%
Note that this will generalize across entities.
For example, discovering that {\em ``nationality $\rightarrow$ date founded''} is a irrelevant path 
based on people born in some countries allows us to drop
instances of this path also for people born in all other countries.

% The {\em IDF filter} uses the concept of {\em inverse document frequency}~\cite{modern-ir} 
% from the IR community. The idea is that a date that is commonly associated 
% with a large number of subjects is unlikely to be particularly interesting.
% To formalize this, consider the set of all subject-path-timestamp triples $(s,p,t)$.
% Let $N(p,t)$ be the number of such triples (from any subject) that traverse $p$
% and end up at time point $t$, and let $N(p)=\sum_t N(p,t)$ be the total number of paths of type $p$.
% Then for any given path $p$ and time $t$, if $N(p,t) / N(p) >
% \theta_1$, where
% $\theta_1$ is some threshold, we drop that path
% for all subjects. Note that this will generalize across many entities.
% For example, discovering that {\em ``nationality $\rightarrow$ date founded''} is a bad path 
% based on people born in {\em USA} allow us to drop
% instances of this path also for people born in other countries.

Further, entities in a KB are naturally associated with a period of \textit{existence}:
individuals are born and pass away, 
companies get founded and go out of business,
and musical groups get formed and split up.
The second filter, {\em Existence Filter}, filters out events 
that occurred before an entity began to exist.
If we find that a particular kind of path is filtered out for a large
fraction (say more than $\theta_3$) of entities,
we filter the path out for all entities. 
%
A canonical example is {\em ``parent $\rightarrow$ date of birth''} which obviously occurs before the subject entity is born (\ie, $\theta_3=100\%$). 
% Since we know the subject DOB, we can automatically discover that this path leads to timestamps that in most cases (here: all) happen before the subject's DOB. 
%
Based on our experiments (discussed next), we chose
$\theta_1=50$ and $\theta_2=\theta_3=0.5$, 
and we observed that slightly varying the parameters had very little impact on the results.

% The event generation steps described in Section~\ref{subsec:event_generation} generate some events that while technically correct are clearly irrelevant for our purpose. 
% For example, every person is connected to their nationality which in turn is connected to its date of foundation.
% This means that every American has an candidate event with timestamp July 4, 1776.
% However, this event is irrelevant to any of them.
% One might argue that it would be relevant to George Washington (founding father of the USA) for instance but note that we only filter paths such as ``nationality $\rightarrow$ date founded'' while George Washington is connected to the USA and its date of foundation in multiple other ways. %\texttt{/people/person/nationality/}.\texttt{location/dated\_location/date\_founded}

% Two simple heuristics are used to filter out irrelevant events.

% The \textit{IDF Filter} uses the concept of inverse document frequency (IDF) from information that captures the idea that terms occurring in most documents are unlikely to be relevant. 
% Similarly, we argue that events generated for many subjects are not relevant to anyone's timeline.
% For each path leading from the timeline subject to a timestamp we record the number of cases where this path leads to the same related entity \& timestamp pair (for at least $N$ subjects each \tim{I can't remember the threshold? 25? 50?}). 
% If this number is higher than 50\% of the number of total occurrences for this path we blacklist that path.

% The second filter, called \textit{Birthdate Filter} is based on the idea that events before someone's birth are unlikely to be relevant to them.
% Similar to the IDF Filter, we record the number of times a path leads to a timestamp before the subject's birthdate.
% Again, if the fraction of events before the birthdate compared to the total number of occurrences exceeds 50\% \tim{check fraction numbers} we blacklist that path.

% Note that in both cases we generalize blacklisted paths to the schema level to reflect that e.g. if foundation dates of your country of nationality are irrelevant for many countries, they are irrelevant for entities from less frequently occurring countries like Monaco as well.
% The 50\% thresholds were chosen after manual inspection of the data and led to good results in practice as the evaluation results below will show.


\vspace{-.5\baselineskip}
\subsection{Evaluation of Event Filtering}
\label{subsec:candidate_generation_evaluation_results}

\eat{
\begin{table}[tb]
\begin{center}
\setlength{\tabcolsep}{2pt}
    \begin{tabular}{lr}
    \toprule
         & \textbf{Accuracy} \\
        \midrule
        IDF Filter & 84\%\\
        Existence Filter & 100\%\\
        %\sectionrule
        \midrule
        Remaining Paths & 87\%\\
        \bottomrule
    \end{tabular}
\end{center}
\vspace{-1mm}
\caption{Accuracy of two filter heuristics and of the remaining paths after filtering. Even very simple heuristics lead to good results.
\todo{Should we save the space for this table?}}
\vspace{-3mm}
\label{table:filter_accuracy}
\end{table}
}

\eat{
We will provide an extensive evaluation of our end-to-end system (including subset selection)
in Section~\ref{sec:evaluation}.
Here we just evaluate the quality of the generation and filtering steps.
}

We used Freebase~\cite{Bollacker08} to generate candidate events for four types of entities: 
music artists, actors, politicians, and athletes. We generated candidate events
for all entities of these types in Freebase and evaluated 
the quality of the results.

We evaluated the quality of our filtering using
%precision-recall
{\em true positive / negative rate metrics} as follows.
% {\em correctness} by 
First, for each filtering heuristic, we estimate the fraction of filtered paths that
were correctly filtered (\ie, judged irrelevant by a human) or the true negative rate.
Second, we estimate the fraction of non-filtered paths
that are correctly not filtered (\ie, judged relevant by a human)
or the true positive rate.
For each metric, we evaluated the top 100 most frequent path types 
covering over 90\% of all generated event instances 
(out of 5269 different path types generated in total).
Two domain experts manually judged each path as relevant or irrelevant.

%The results are shown in Table~\ref{table:filter_accuracy}.
We observe that the Frequency Filter is 84\% correct (\ie, it accidentally filters out
only 16\% of the relevant paths), and the Existence Filter is 100\% correct
(\ie, everything it filters out is irrelevant).
The main failure case for the Frequency Filter consisted of relevant events involving many entities, 
such as large award ceremonies or military conflicts.  
We also observe that among the paths that pass both filters,
87\% are correct.
The main failure case are birthdates of related people (\eg, members of the same band), 
which are arguably irrelevant to the subject.

In addition to high correctness, we need the event generation phase to have high {\em coverage}.
Figure~\ref{fig:path_coverage} 
plots the number of events on the X-axis versus the number of
entities for which we extracted at least this many events on the
Y-axis (after filtering).
Suppose we require at least 100 candidate
events for an entity before we consider it to be
``history rich'' enough for us to generate its timeline.
The figure shows that we can generate timelines for 12k entities if we
use simple events, and for 64k entities if we use compound events 
(see Section~\ref{subsec:event_generation}).
This shows that Freebase has a sufficiently rich set of events
to make our approach possible, even though it is incomplete
in many other ways \cite{Dong14}.
With the advent of systems for automated knowledge-base population
such as Knowledge Vault \cite{Dong14}, we can expect the coverage to improve further in the future.

% Given the very large number of candidate events for each entity,
% we see that the problem of subselecting the most relevant few events 
% for online timeline construction is very challenging.
%  We describe our solution to this problem next.

% \todo{Kannan et al, KDD 2014 claim coverage in terms of fraction of queries served. Should we try and express what percentage of ``entity queries'' the top 64k cover?}


% We are interested in the accuracy two filter heuristics, IDF Filter and Birthdate Filter, \ie what fraction of \textit{filtered} paths are correctly filtered out?
% In addition, we are interested in the accuracy of the remaining paths after applying both filters to the generated candidate events, \ie what fraction of \textit{remaining} paths are correct?

% To investigate these questions, two domain experts manually annotate the most frequent paths for both IDF Filter and Birthdate Filter as well as the most frequent remaining paths after applying both filters.
% Disagreement between the annotations was resolved through discussion.
% Note that we restrict ourselves to only the most frequent 100 paths in all three cases.
% While there is a long tail of 1000s of extracted paths the top 100 paths account for more than 90\% of all extracted events and therefore provide a reasonable accuracy estimate.
%\safa{worth mentioning that for 1000s of facts we can design a path ranking algorithm or create a long term curation project}


% The results are shown in Table~\ref{table:filter_accuracy}.
% The main failure case for the IDF filter (16\% error) are start/end dates of events involving many entities, e.g. large award ceremonies or military conflicts.
% The Birthdate heuristic was found to always correctly filter paths.
% The main failure case for the remaining paths are birthdates of related people (e.g. members of the same band or political party).
% Overall, the results show that even very simple filtering heuristics lead to good results.
% We note that the failure cases could easily be addressed by tweaking the thresholds or through additional heuristics.
% However, since our focus lies on an end-to-end system for generating timelines and the more challenging subproblem of selecting relevant events (see Section~\ref{sec:selection}) we leave such incremental improvements to future work.

% In addition to high accuracy we require the event candidate generation phase to have high coverage, \ie to extract a large number of events for a large number of entities.
% A coverage plot is shown in Figure~\ref{fig:path_coverage} that displays \#events on the X-axis (log) versus \#entities for which we extracted at least this many events on the Y-axis (log).
% It demonstrates that the proposed approach has high coverage (100+ extracted events for over 65k entities).
% Given that there is a large number of candidate events for each entity, the problem of subselecting the most relevant few events becomes very challenging.
% We describe our approach for event selection next.

\begin{figure}[t]
  \centering
  % this image comes from musictimelines/results/pathanalysis/new/pathsstats
  % unsure where I stored ipython notebook...
  \includegraphics[width=0.9\linewidth]{results_coverage_geq.pdf} % results_coverage_new.pdf
 \vspace{-5mm}
  \caption{Log-log coverage plot showing the number of entities with X or more candidate events % (similar to CCDF).
  and illustrating the impact of adding compound events (dashed line).
  % Log-log coverage plot showing the number of entities with X or more candidate events. % (similar to CCDF).
  % The difference between the solid and the dashed line illustrates the
  % impact of adding compound events.
% HistoryXHistory step. % (Section~\ref{subsubsec:historyXhistory}).
 % The proposed approach has high coverage with more than 100 extracted events for over 64K entities.
   \vspace{-1mm}
  }
  \label{fig:path_coverage}
  % \vspace{-0.5em}
\end{figure}

030selection.tex
% !TEX root = timelines-paper.tex

We showed in the previous section that a given entity may have hundreds of
candidate events associated with it.
In this section, we discuss our main contribution,
a way of selecting a small subset of
events to be shown on the timeline, given the
time span of interest and a specified amount of space on the screen.

Our approach will be based on submodular optimization,
which we explain in general terms in
Section~\ref{subsec:submodular_function_maximization}
(following \cite{calinescu2011maximizing,krause2012submodular}).
We define our specific optimization problem in
Section~\ref{subsec:timeline_optimization},
and give details in Section~\ref{subsec:relevance} and Section~\ref{subsec:temporal_constraint}.
In Section~\ref{subsec:optimization_algorithm},
we describe our efficient approximation algorithm,
which we prove in 
Section~\ref{subsec:approximation_guarantee} 
to yield close-to-optimal solutions.
Finally in Section~\ref{subsec:zoom},
we discuss how our algorithm enables user interactions,
such as zooming in (or out) on the timeline.


% \pagebreak[4] % otherwise alone
\enlargethispage{1\baselineskip} % to get eq 2 on page 4
\subsection{Submodular Function Maximization}
\label{subsec:submodular_function_maximization}

Suppose we have a set (\eg, events) denoted by $X$,
and an evaluation function for sets $f : 2^X \rightarrow \mathds{R}$. 
Let $f_S(e) = f(S \cup \{e\}) - f(S)$ be the {\em marginal gain} of adding
element $e \in X$ to set $S$. 

A function $f : 2^X \rightarrow \mathds{R}$ is {\em submodular} if
for every pair of subsets $A \subseteq B \subseteq X$ and element $e \in X\setminus B$ we have
$f_A(e) \geq f_B(e)$.
Intuitively this means that the benefit of adding element $e$
to the smaller set $A$ is bigger than adding it to the bigger set $B$,
so $f$ exhibits the property of {\em diminishing returns}.
% A function $f$ is \textit{submodular} iff
% \begin{align*}
% f(A \cup B) + f(A \cap B) \leq f(A) + f(B)
% \end{align*}
% for all $A, B \subseteq X$. 
We restrict our attention to {\em monotone} functions;
that is, $f(A) \leq f(B)$ for all $A \subseteq B$. We also assume 
$f(\emptyset) = 0$; that is, $f$ is non-negative.

\xhdr{Constraints}
We want to compute 
$\max_{S\subseteq X} f(S)$ subject to some constraints on $S$.
A common constraint is on the size or cardinality of $S$
 \cite{krause2012submodular}.
However, in our case, we have more complex constraints,
related to temporal diversity and overlap.
To formalize these constraints, we need the notion of an
independence family, defined as follows.
An {\em independence family}
 $\mathcal{I} \subseteq 2^X$
is a family of subsets that is downward closed; that is, $A \in \mathcal{I}$ and $B \subseteq A$ implies that $B \in \mathcal{I}$. 
A set $A$ is called {\em independent} if $A \in \mathcal{I}$.
Popular independence families include {\em matroids} and
intersection of matroids \cite{calinescu2011maximizing}.
As an example, given $X = \{a,b,c\}$, an independence family is as follows: 
$\mathcal{I} = \{ \emptyset, \{a\},\allowbreak \{b\}, \{c\}, \{a,c\} \}$.
% Later we will see how our temporal constraints define an independence family.
%Our temporal constraints define a more general independence family
%called $p$-system, defined next.

% We follow the definition of \cite{calinescu2011maximizing}. 
% Given an independence family $\mathcal{I}$ and a set $Y \subseteq X$, let
% $\mathcal{B}(Y)$ be the set of maximal independent sets of $I$ included in $Y$, that is $\mathcal{B}(Y) = \{A \in I | A \subseteq Y$ and there is no $A' \in I$ such that $A \subset A' \subseteq Y \}$. 
% Then $I$ is a $p$-system if for all $Y \subseteq X$,
% \begin{align*}
% \frac{\max_{A\in\mathcal{B}(Y)} |A|}{\min_{A\in\mathcal{B}(Y)} |A|} \leq p.
% \end{align*}

\xhdr{p-system}
%\begin{definition}{$p$-system\\}
For a set $Y \subseteq X$, a set $J$ is called a \textit{base} of $Y$ if $J$ is a maximal independent subset of $Y$; 
in other words $J \in \mathcal{I}$ and for each $e \in Y \setminus J$, we have $J \cup \{e\} \notin \mathcal{I}$. 
Note that $Y$ may have multiple bases, and further, a base of $Y$ may not be a base of a superset of $Y$. 
In our example of $X$ and $\cal I$, in the case of $Y=X$, the bases are $\{b\}$ and $\{a,c\}$
(since $\mathcal{I}$ does not include $\{a,b\}$, $\{b,c\}$, or $\{a,b,c\}$).

We will now use this concept to define a more general 
notion of independence families parametrized by an integer $p$,
as follows.
$(X, \mathcal{I})$ is said to be a \textit{$p$-system} if for each $Y \subseteq X$, the cardinality of the largest
base of $Y$ is at most $p$ times the cardinality of the smallest base
of $Y$:
\begin{align}
\label{eq:p_systems_property}
\frac{\max_{J:J \text{ is a base of } Y} |J|}{\min_{J:J \text{ is a base of } Y} |J|} \leq p.
\end{align}
%\end{definition}
To continue with our example of $X, Y, \cal I$, there are two bases and
%An example for a $p$-system is $X = \{a,b,c\}$ and $\mathcal{I} = \{ 
%\emptyset, \{a\},\allowbreak \{b\}, \{c\}, \{a,c\} \}$.
%In the case of $Y=X$, the bases are $\{b\}$ and $\{a,c\}$
%(since $\mathcal{I}$ does not include $\{a,b\}$, $\{b,c\}$, or $\{a,b,c\}$) and 
$p = |\{a,c\}|/|\{b\}| = 2$.
For all other choices of $Y \subseteq X$, we have $p = 1$.
Thus, $(X, {\cal I})$ is a 2-system.
%Our constraints form a $p$-system for
%$p=2$ (see Section~\ref{subsec:temporal_constraint}).
The notion of $p$-systems will be useful in Section~\ref{subsec:approximation_guarantee} to prove certain approximation guarantees.

\xhdr{Advantages}
Before continuing, it is worth discussing why we are using
submodular optimization.
A simple alternative would be to just
score each event independently, sort the events by score, and return
the top events (as long as they fit into the timeline).
Such static rankings are insufficient for our purposes since they do not consider diversity.
For instance, even though the movie {\em The Avengers} is very relevant to
Robert Downey Jr.,
the timeline should not solely consist of {\em The Avengers} events (filming, production, release date, award ceremonies, sequels, \etc).
Furthermore, we want diversity in the temporal spacing of the events
(we show in Section~\ref{sec:evaluation} that users strongly prefer diverse timelines)
which depends on the time period or zoom factor chosen by the user.

The best way to capture these effects is to reason about the entire
\textit{set} of events that should make up the timeline. 
A submodular set function allows for exactly that, and is able to
encourage different notions of diversity,
as we show in Section \ref{subsec:relevance}.
In addition, there are computational benefits to using monotone
submodular set functions.
In particular, as we show in Section \ref{subsec:approximation_guarantee}, we can devise
a greedy algorithm that enjoys certain optimality guarantees.


% \pagebreak[4] % otherwise header alone
% \vspace{-1\baselineskip}
% \enlargethispage{1\baselineskip} % to get eq 2 on page 4
\subsection{Timeline Optimization Problem}
\label{subsec:timeline_optimization}

We now formalize our problem.
Let $E \subset \mathcal{E}$
be the set of all candidate events for a particular subject
entity $\sub$ constrained to events 
within the user-specified or default time span.
We will display each event as a small box of width $w$ and height $h$,
as shown in 
Figure~\ref{fig:timeline_rdjr_full}.
Assume we have available screen space of width $\mathcal{W}$ and height $\mathcal{H}$.
Let $n = \floor{\mathcal{H} / h}$ be the number of boxes that can be
stacked vertically within $\mathcal{H}$.
Our goal is to find the optimal timeline $T^*$, which we define as follows:
% 2 row version
\begin{align}
T^* =& \argmax_{T\subseteq E} \relevance (\sub, T) \label{eq:timeline_optimization}\\
& \text{ s.t. } \temporalconstraints(T, E, \mathcal{W}, w, n) \nonumber
\end{align}
% % 1 row version
% \begin{align}
% T^* = \argmax_{T\subseteq E} \relevance (\sub, T)   \text{ s.t. } \temporalconstraints(T, E, \mathcal{W}, w, n)\label{eq:timeline_optimization}
% \end{align}
%\begin{align}
%T^* =& \argmax_{T\subseteq E} \textsc{Relevance}(\texttt{s}, T) \label{eq:timeline_optimization}\\
%& \text{s.t. } \textsc{TemporalConstraint}(T, w, n) 
%\end{align}
The relevance function \relevance~evaluates how relevant each event is to the
subject and how diverse they are;
this is described in more detail in Section~\ref{subsec:relevance}.
The temporal constraint \temporalconstraints~requires that all events can fit into the
provided space without overlapping or occluding each other;
this is described in more detail in Section~\ref{subsec:temporal_constraint}.

Note also that our algorithm is able to adapt to different form
factors, for example for mobile or desktop, since height and width are just
parameters to the optimization algorithm. 

%fix pagebreak
% \pagebreak[4]
% \vspace{-0.5\baselineskip}
\subsection{Relevance Function}
\label{subsec:relevance}
% \subsubsection{Quality/Relevance Function}
The function $\relevance(\sub,T)$
captures the quality of the selected subset of events $T$
% \footnote{
%   \todo{
%   The timeline set $T$ has no arguments and is not to be confused with
%   the event timestamp function $\texttt{T}(e)$
%   (from Section~\ref{subsec:event_generation}).
%   }
% }
with respect to the timeline subject $\sub$.
This is defined as a linear combination of two different kinds of
relevance functions:
\begin{align*}
\relevance (s, T) = \lambda \, \entityrelevance (s, T) 
+ (1 - \lambda) \, \daterelevance (s,T)
\end{align*}
%\begin{align*}
%\textsc{Relevance}(s, T) &= \lambda \textsc{Entity\textsc{Relevance}}(s, T) \\
%&+ (1 - \lambda) \textsc{Date\textsc{Relevance}}(s, T)
%\end{align*}
where $0 \leq \lambda \leq 1$ trades off the importance of related
entities (\entityrelevance) versus the importance of related dates (\daterelevance).\footnote{
  We set $\lambda=0.75$ throughout,
  based on preliminary experiments on a holdout set showing that users slightly prefer
  entity relevance to date relevance.
}
We define these terms next.
% (Note: We set $\lambda=0.75$ throughout,
% based on preliminary experiments on a holdout set showing that users slightly prefer
% entity relevance to date relevance.)
%\todo{Note: Our full system uses $\lambda=0.75$, i.e. three times more importance on EntityRelevance.}


%\subsubsection{\textsc{EntityRelevance}}
\subsubsection{Entity Relevance}
\label{subsubsec:entity_relevance}

We define the relevance of a set of events $T$ to an entity $s$ as
follows:
\[
\entityrelevance (\sub,T) =
w^e_1 \, \EtoE(\sub, T)
+ w^e_2 \, \EtoEPath(T) 
+ w^e_3 \, \GtoE(T)
\]
where \EtoE~measures how relevant the specific {\em events} are,
\EtoEPath~ \linebreak[4]measures how relevant the {\em paths} are,
and \GtoE~measures how relevant the events are {\em globally} (\ie, independent of $s$).
As we show shortly, we combine \EtoE\ with \EtoEPath\ and \GtoE\ to handle data sparsity,
\cf, backoff-smoothing \cite{Katz87estimationof}.
This enables inductive reasoning that certain relationships hold
generally
when we only see a few examples of them.
For example, on average, movie roles are more relevant to actors than TV episode roles (\EtoEPath).
We discuss how we set the weight parameters in Section~\ref{sec:evaluation}.
%We set $w^e_1 = 1$, $w^e_2 = 10^{-2}$, and $w^e_3= 10^{-4}$,
%based on preliminary experiments.



% Here $\EtoE(\sub, T)$ measures entity-to-entity
% relatedness through web-based co-occurrence signals
% and $\EtoEPath(\sub, T)$ and $\GtoE(\sub, T)$ help with generalization of the sparse signal in way that is conceptually similar to backoff-smoothing \cite{Katz87estimationof}.
% \todo{Note: We use $w^e_1 = 1$, $w^e_2 = 10^{-2}$, and $w^e_3= 10^{-4}$. In the spirit of backoff we set the parameters manually. However, they could also be learned to optimally match a set of ground truth timelines.}

In more detail, we measure the entity-to-entity score
 as follows:
\[
\EtoE(\sub, T) = \sum_{re \in \{\reFun(e)
  \;|\; e \in T\}}  \EtoECooc(\sub, re) 
\]
where $\EtoECooc(\sub, re)$ measures
co-occurrence of the entities, and is defined in
Section~\ref{sec:cooc}.

Since a path from a subject to a specific entity may occur too rarely
to be reliably estimated, we also consider measuring
how good the path is, by averaging the co-occurrence
score over all entities that can be
reached via all the paths in the timeline:
\begin{eqnarray*}
% \begin{split}
\lefteqn{\EtoEPath(T) } \\
 &=&
\sum_{p \in \{\pathtore{e} \;|\; e \in T\} }
\average_{e \in \mathcal{E},\, \pathtore{e} = p} \EtoECooc(\subFun(e), \reFun(e))
% \nonumber
% \end{split}
\end{eqnarray*}


% \begin{align*}
% \EtoEPath(\sub, T) 
%  &= \sum_{\texttt{p} \in \{\texttt{PathToRE}(e) \;|\; e \in T\}}  \textsc{AvgE2ECooc}(\texttt{p})\\
% \textsc{AvgE2ECooc}(\texttt{p}) 
% &= \average_{e \in E,\, \texttt{PathToRE}(e) = \texttt{p}} \EtoECooc(\subFun(e), \reFun(x))
% \end{align*}

Finally, since even the $\EtoEPath$ signal may be too sparse to
reliably estimate, we consider
\GtoE, which estimates the global importance of each entity in
the timeline:
\begin{align*}
\GtoE(T) = \sum_{re \in \{\reFun(e) \;|\; e \in T\}}  \globalimportance(re)
\end{align*}
% We estimate $\globalimportance(re)$ based
% on the number of queries for entity $re$ on a popular search
% engine
% (though other measures of global importance could be used instead).

We estimate $\globalimportance(re)$ as
the fraction of search queries that mention the entity $re$,
measured from a 3-month query log
(though other measures of global importance could be used instead).
Inferring the entity mentioned in a query is done using a proprietary
system that applies standard entity linkage algorithms
(such as \cite{Shen2015}) to the landing page of the query.




All three functions, $\EtoE$, $\EtoEPath$, and $\GtoE$, are weighted coverage functions 
defined over a {\em set} rather than a {\em multiset} of related entities (or paths to related entities).
As such, they naturally favor content diversity as duplicate entities or paths are only counted once.


% \pagebreak[4] % otherwise header alone
\subsubsection{Date Relevance}
We define the relevance of a set of dates as follows:
\[
\daterelevance (\sub,T) = 
 w^d_1 \, \EtoD(\sub, T) 
+ w^d_2  \, \EtoDPath(T)
\]
%(We set $w^d_1 = 1$, and $w^d_2 = 10^{-2}$ based on preliminary experiments.)
% where $\EtoD(\sub, T)$ measures entity-to-date
% relatedness through web-based co-occurrence and
% $\EtoDPath(\sub, T)$ again helps with generalization of
% the
%  sparse signal in way that is conceptually similar to backoff-smoothing \cite{Katz87estimationof}.
% \todo{Note: We use $w^d_1 = 1$, and $w^d_2 = 10^{-2}$.}:
The functions \EtoD~and \EtoDPath~ are defined in a very
similar way to their \EtoE~counterparts.
For specific dates we have
\[
\EtoD(\sub, T) = \sum_{t \in \{\tFun(e) \;|\; e \in T\}}  \EtoDCooc (\sub, t) 
\]
Recall that $\tFun(e)$ is the timestamp of event $e$, so
$\EtoDCooc$ measures how often an entity and date co-occur,
as explained below.
Then for the path level we have
\begin{eqnarray*}
\lefteqn{\EtoDPath(T) } \\
&=& \sum_{p\in \{\pathtots{e} \;|\; e \in T\}}  
\average_{e \in \mathcal{E},\,  \pathtots{e} = p}
\EtoDCooc(\subFun(e), \tFun(e))
\end{eqnarray*}
% \begin{align*}
% \EtoD(\sub, T) &= \sum_{t \in \{t(x) \;|\; x \in T\}}  \EtoDCooc (\sub, t) \\
% \EtoDPath(\sub, T) &= \sum_{\texttt{p} \in \{\texttt{PathToTS}(x) \;|\; x \in T\}}  \textsc{AvgE2DCooc}(\texttt{p}) \\
% \textsc{AvgE2DCooc}(\texttt{p} ) &= \average_{e \in E,\,
%   \texttt{PathToTS}(e) = \texttt{p}} 
% \EtoDCooc(\subFun(e), t(e))
% \end{align*}

Similarly, we again use a set instead of a multiset for the timestamps and time paths
to favor temporal diversity.
% that is, duplicate timestamps or time paths are only counted once.

\subsubsection{Web-based Co-occurrence Scores}
\label{sec:cooc}

We use co-occurrence signals between entities on the web
 to capture how related two entities are (\EtoECooc).
Similarly, we use co-occurrence between
entities and dates
(\EtoDCooc) to capture how related 
a particular date is to an entity.
We compute these quantities as follows:
\vspace{-1mm}
\begin{enumerate}
\item We run a suite of standard NLP tools (named entity recognition,
  coreference resolution, \etc) over a large corpus of 10B web
  documents using a set of in-house tools, 
  similar to the Stanford CoreNLP package.\footnote{
  \small
  \url{http://nlp.stanford.edu/software/corenlp.shtml}
  }
  We extract entity mentions (which are resolved to Freebase IDs)
and date mentions (both year and full date if available), 
using techniques similar to those described
in \cite{Shen2015}.
%\cite{Grishman12}.

\item For each entity mention, we
 collect all entity-entity and entity-date co-occurrences within a
 small window around the mention (window of 100 characters or 10-12 words on average).

\item We count these co-occurrences,
and convert to probabilities (by normalizing the counts).
We define the co-occurrence scores using {\em normalized pointwise mutual
information}
\linebreak[4](\textsc{NPMI})
as follows:
\end{enumerate}
\vspace{-5mm}
\begin{align*}
\EtoECooc(\sub, re) &= \textsc{NPMI}(\sub; re) = \frac{\textsc{PMI}(\sub; re) }{- \log p(\sub, re)}\\
\textsc{PMI}(\sub; re) &= \log \frac{p(\sub, re)}{p(\sub) \, p(re)}
\end{align*}
\EtoDCooc~is defined exactly like \EtoECooc~with the
only difference that a timestamp $t$ is substituted for entity
$re$. 

PMI measures the difference between the co-occurrence probability and
the probability expected by chance if the events were independent.
It is critical to account for particularly popular entities
(\eg, Barack Obama) or dates (\eg, 2014), and dividing the co-occurrence
probability by the popularity of the co-occurring entities/dates 
is a principled way of achieving this. 

NPMI normalizes PMI to the range $[-1, 1]$.
Since we are only interested in the most related pairs of entities (or
entity/date pairs), we only retain positive \textsc{NPMI} scores.
Furthermore,
we require that this co-occurrence was extracted from at least 
five different web domains for robustness.
Computing co-occurrence statistics from a large web corpus (10B documents) and generating candidate events (for over 1M entities) takes about six hours using map-reduce.




\subsubsection{Submodularity of Objective Function}

We now show that our objective function is a monotone submodular set
function.

\begin{theorem}{}
\label{theorem:submodular_objective}
Let $f(T) = \relevance(\sub, T)$ for any given subject $\sub$.
Then $f: 2^T \rightarrow \mathds{R}^+$  is a monotone submodular set function.
\end{theorem}
\begin{proof}
First we note that $f$ is a non-negative linear combination of
weighted coverage functions 
(since $w_1^e, w_2^e, w_3^e, w_1^d, w_2^d \geq 0$).
Each of these are
known to be submodular \cite{feige1998threshold,
  krause2012submodular},
which is easy to see,
due to the diminishing returns property of weighted coverage functions.
%This is easy to see,
%since for every $A \subseteq B \subseteq E$ and $e \in E\setminus B$ it holds that $$f_A(e) \geq f_B(e).$$
%Since B covers as least as many events as A and therefore the marginal
%gain on A can only be larger
 %(diminishing returns property of weighted coverage function).
Furthermore, a non-negative linear combination of submodular functions is submodular as well.

Second, we note that $f$ is also monotone.
This holds since all individual weighted coverage functions are
non-negative (because 
 \EtoECooc, \EtoDCooc, and \textsc{Global\-Importance}
 are all non-negative),
so adding up more terms makes the sum bigger.

Third, we have $f(\emptyset)=0$, again because all weighted coverage functions lead to empty sums.
\end{proof}


% \subsubsection{Schema-based Generalization to Path Level}

% Section \ref{subsubsec:entity_relevance} defines \EtoEPath and \EtoDPath that generalize the co-occurrence scores to a path level similar in spirit to backoff-smoothing \cite{Katz87estimationof}.
% It enables inductive reasoning that certain relationships hold generally when we only see examples of them.
% For example, on average, movie roles are more relevant to actors and actresses than TV episode roles (\EtoEPath).
% The death of a bandmember is more relevant to the subject than the bandmember's birth (\EtoDPath).
% Your own birth date is much more relevant to you than their birth date.
% Understanding these relationships helps when we have little data -- when we encounter a less well-known actor we can assume that their movie roles are more important than their TV episode roles.
% This schema-based generalization is one of the greatest benefits of using KBs for knowledge/event representation.



% otherwise sitting alone
% \pagebreak[3]
\subsection{Temporal Diversity Constraint}
\label{subsec:temporal_constraint}

The layout constraint requires that all events can fit into a timeline
of width $\mathcal{W}$ and height $\mathcal{H}$ without overlap.
We consider a simple layout strategy: 
if the boxes (of width $w$) depicting
two events have a temporal overlap,
we can stack one on top of the other,
as shown in
Figure~\ref{fig:timeline_rdjr_full},
but we require that the height of this stack be at most
$n = \floor{\mathcal{H} / h}$.

We can define this constraint more formally as follows.
%Let $Y \subseteq E$ be any subset of events.
Recall that each event $e \in E$ has a timestamp $\tFun(e) \in \mathds{R}$.
%We also define $\tFun(Y) = \{ \tFun(y) \;|\; y \in Y \}$ as the set of timestamps for all events in $Y$.
Let $R$ be an interval $R = [a,b] \subset \mathds{R}$.
We denote the set of events in $T \subseteq E$  with timestamps within $R$ as $T \sqcap R= \{ e\in T \;|\; \tFun(e) \in R \}$. 
%(Note that it is not enough to simply use $\tFun(Y)$ since we need to allow for multiple events with the same timestamp.)
We define $t_w$ as the length of a time period that corresponds to the width of $w$ on the timeline;
% \todo{(\ie, the width of the event boxes in Figure~\ref{fig:timeline_rdjr_full})} 
$t_w$ can be easily computed according to $\mathcal{W}, w$, and the beginning and ending timestamps for $E$.
Finally,
we say a set $T \subseteq E$ of events satisfies the layout constraint $\temporalconstraints(T, E, \mathcal{W}, w, n)$  if
\begin{align}
\forall t\in \mathds{R}: |T \sqcap [t, t+t_w) | \leq n \label{eq:LayoutConstraint}
\end{align}
This constraint can be interpreted as follows:
for any point in time $t\in \mathds{R}$, draw a line of width up to $t_w$ starting at $t$.
Consider the intersection of all timestamps in $T$ with this line.
If the size of the intersection is less or equal to $n$, then we know that we can vertically stack the events in the intersection without violating the height constraint.

%% too detailed.
% The constraint depends implicitly on $E$ and $\mathcal{W}$ since, for simplicity, we assume that we have timestamps $\tFun(e) \in \mathds{R}$.
% Let \texttt{ts} be the timestamp associated with event $e$, say in Unix time,
% and let $\texttt{ts}_{\min}$ and $\texttt{ts}_{\max}$ be the minimum and maximum timestamp within $E$ (in the same units).
% Then we map all timestamps using
% $$\tau(e) = (\mathcal{W} - w) \frac{\texttt{ts} - \texttt{ts}_{\min}}{\texttt{ts}_{\max} - \texttt{ts}_{\min}} + \frac{1}{2}w \in \Big[ \frac{1}{2}w, \mathcal{W}-\frac{1}{2}w \Big] \subset \mathds{R},$$
% where the $1/2w$ comes from ``padding'' on either side of the timeline in case $\texttt{ts}_{\min}$ or $\texttt{ts}_{\max}$ get chosen.



% It turns out that this constraint forms a special independence family that enables us to prove approximation guarantees (see Sec.~\ref{subsec:approximation_guarantee}).
% In the Appendix, we show that our temporal constraint forms an
% independence family.

It turns out that this constraint forms a $p$-system that enables us to prove approximation guarantees (see Section~\ref{subsec:approximation_guarantee}).
\begin{theorem}{}
\label{theorem:layout_constraints_psystem}
Let $(E,\mathcal{I})$ be an independence family based on our layout
constraint where $T \in \mathcal{I}$ if $T \subseteq E$ satisfies
Equation~\eqref{eq:LayoutConstraint}.
Then $(E,\mathcal{I})$ forms a $p$-system for $p=2$.
\end{theorem}
\vspace{-0.5\baselineskip}
\begin{proof-idea}
For the full proof please refer to the appendix of the full version of this paper~\cite{althoff2015fullpaperarxiv}.
The idea is as follows:
%
We need to show that $|J_{\max}| / |J_{\min}| \leq 2$ where $J_{\min}$ and $J_{\max}$ are minimal and maximal bases of an arbitrary subset $T \subseteq E$.
We can show that $J_{\max}$ can be at most twice as large as $J_{\min}$ 
by ``deleting'' all elements from $J_{\max}$ eventually,  
where in each step we delete an element $b \in J_{\min}$, 
and up to two elements in $J_{\max}$ (if they exist) in close proximity to $b$.
%
Intuitively this process works because we can never have an element in $J_{\max}$ that we cannot delete in this way
since then either 
$J_{\min}$ has too few points to be a maximal independent set (base),
or $J_{\max}$ has too many points to be an independent set (it would violate the layout constraint).
Both would contradict our assumption that both $J_{\min}$ and $J_{\max}$ are bases of $Y$.
\end{proof-idea}
\vspace{-2\baselineskip}




\subsection{Optimization Algorithm}
\label{subsec:optimization_algorithm}

Our problem is reduced to the problem of finding a solution $T^*$ that obtains $\max_{T \in \mathcal{I}} \relevance(s,T)$, 
where $\mathcal{I}$ is the independence family that we defined in Section~\ref{subsec:temporal_constraint} (see Theorem~\ref{theorem:layout_constraints_psystem}).
Unfortunately, such problems are NP-hard for many classes of
submodular functions,
including weighted coverage \cite{feige1998threshold} (our case).
Therefore we focus our attention
on efficient algorithms with theoretical approximation guarantees.

As we show in Section~\ref{subsec:approximation_guarantee},
a greedy algorithm (see Algorithm \ref{alg:greedy}) 
 has certain approximation guarantees.
The algorithm incrementally builds an approximate solution $\hat{T}$ (without backtracking), starting with the empty set. 
In each iteration it adds an element $e$ from the set of valid candidates $C$ that most improves the current
solution (according to the marginal gain $\relevance_{\hat{T}}(e)$),
while maintaining independence of the solution (see line 3).
%This is shown more precisely in Algorithm~\ref{alg:greedy}. 


\begin{algorithm}[t]
  \caption{{\sc GreedyTimeline}\label{alg:greedy}}
  \begin{algorithmic}[1]
  \State $\hat{T} \leftarrow \emptyset, C \leftarrow \emptyset$ 
    \Repeat
        \State $C \leftarrow \{e \in E\setminus \hat{T} \;|\; \hat{T} \cup \{e\} \in \mathcal{I}\}$
        \If{$C \neq \emptyset$} 
           \State $e \leftarrow \argmax_{e' \in C} \relevance_{\hat{T}}(e')$
           \State $\hat{T} \leftarrow \hat{T} \cup \{e\}$
        \EndIf
    \Until{$C = \emptyset$}
  \State \Return $\hat{T}$
  \end{algorithmic}
\end{algorithm}


% old - general version
% We need to solve the following problem:
% $\max_{S \in \mathcal{I}}  f(S)$,
% where $\mathcal{I}$ is an independent family.
% Unfortunately, this simple problem is NP-hard for many classes of
% submodular functions,
% including weighted coverage \cite{feige1998threshold}.
% Therefore  we focus our attention
% on efficient algorithms with theoretical approximation guarantees.

% As we show in Section~\ref{subsec:approximation_guarantee},
% the following greedy algorithm (Algorithm \ref{alg:greedy})
%  has certain approximation guarantees.
% The algorithm incrementally builds a solution $S$ (without backtracking), starting with the empty set. 
% In each iteration it adds an element from $A$ that most improves the current
% solution (according to $f$),
% while maintaining independence of the solution (see line 3).
% %This is shown more precisely in Algorithm~\ref{alg:greedy}. 


% \begin{algorithm}
%   \caption{Greedy Algorithm \label{alg:greedy}}
%   \begin{algorithmic}[1]
%   \State $S \leftarrow \emptyset, A \leftarrow \emptyset$ 
%     \Repeat
%         \State $A \leftarrow \{e \in E\setminus S \;|\; S \cup \{e\} \in \mathcal{I}\}$
%         \If{$A \neq \emptyset$} 
%            \State $e \leftarrow \argmax_{e' \in A} f_S(e')$
%            \State $S \leftarrow S \cup \{e\}$
%         \EndIf
%     \Until{$A = \emptyset$}
%   \State \Return $S$
%   \end{algorithmic}
% \end{algorithm}

This greedy algorithm has complexity $\mathcal{O}(|E|^2)$ 
(assuming computing $\relevance_{\hat{T}}(\cdot)$ takes constant time).
In practice, it can be sped up significantly in practice by using
lazy evaluations, as 
first proposed in \cite{minoux1978accelerated}
(see also \cite{leskovec2007cost} and Section 2 of \cite{krause2012submodular}).
This ``lazy greedy'' algorithm exploits the fact that the marginal gain for each element only decreases with each iteration; 
that is, $\relevance_{\hat{T}}(e) \geq \relevance_{\hat{T}'}(e)$ for $\hat{T} \subseteq \hat{T}'$, and therefore we can use previously computed values as upper bounds to save many evaluations of $\relevance_{\hat{T}}$.
%This idea was originally proposed in \cite{minoux1978accelerated} and has been shown to be useful beyond the greedy algorithm \cite{leskovec2007cost}.
We use this more efficient implementation of the greedy algorithm.



% \pagebreak[4] % otherwise header alone
\subsection{Approximation Guarantee}
\label{subsec:approximation_guarantee}



% To prove some properties about our greedy algorithm, we 
% first need to introduce
% some additional definitions
% from the field of submodular optimization.

% \subsubsection{p-systems}

% %\begin{definition}{$p$-system\\}
% For a set $Y \subseteq X$, a set $J$ is called a \textit{base} of $Y$ if $J$ is a maximal independent subset of $Y$; 
% in other words $J \in \mathcal{I}$ and for each $e \in Y \setminus J$, we have $J \cup \{e\} \notin \mathcal{I}$. 
% Note that $Y$ may have multiple bases, and further, a base of $Y$ may not be a base of a superset of $Y$. 

% We will now use this concept to define a more general 
% notion of independence families parametrized by an integer $p$,
% as follows.
% $(X, \mathcal{I})$ is said to be a \textit{$p$-system} if for each $Y \subseteq X$, the cardinality of the largest
% base of $Y$ is at most $p$ times the cardinality of the smallest base
% of $Y$:
% \begin{align}
% \label{eq:p_systems_property}
% \frac{\max_{J:J \text{ is a base of } Y} |J|}{\min_{J:J \text{ is a base of } Y} |J|} \leq p.
% \end{align}
% %\end{definition}
% An example for a $p$-system is $X = \{a,b,c\}$ and $\mathcal{I} = \{ 
% \emptyset, \{a\},\allowbreak \{b\}, \{c\}, \{a,c\} \}$ where $\{b\}$ and $\{a,c\}$ are the bases 
% of $Y=X$
% (since $\mathcal{I}$ does not include $\{a,b\}$, $\{b,c\}$, or $\{a,b,c\}$) and $p = |\{a,c\}|/|\{b\}| = 2$.
% For all other choices of $Y \subseteq X$ we have $p = 1$.

% In the Appendix, we show that our temporal constraint forms a $p$-system for
% $p=2$.





% \subsubsection{Theoretical Results}

Before we can prove our main theoretical result,
we introduce the following lemma.
It is proved in~\cite{nemhauser1978analysis} for the special
case where $\mathcal{I}$ is defined by 
the intersection of $p$ matroids on $X$,
and for the more general case of $p$-systems in Appendix B of \cite{calinescu2011maximizing}.

\vspace{-1mm}
\begin{lemma}
\label{theorem:general_approximation_ratio}
~\cite{calinescu2011maximizing,nemhauser1978analysis}
The algorithm {\sc GreedyTimeline} to compute
$\max_{S \in \mathcal{I}} f(S)$, where $(X, \mathcal{I})$ is a
$p$-system and $f : 2^X \rightarrow \mathds{R}^+$
 is a monotone submodular set function, has a tight approximation ratio of $1/(p + 1)$.
\end{lemma}
\eat{\vspace{-1.0\baselineskip}
\begin{proof}
See \cite{nemhauser1978analysis} for the special
case where $\mathcal{I}$ is defined by 
the intersection of $p$ matroids on $X$.
A proof for the more general case of $p$-systems is given in Appendix B of \cite{calinescu2011maximizing}.
These ratios are tight for all $p$ \cite{calinescu2011maximizing}.
\end{proof}
}
\vspace{-2mm}

We have shown in Theorem~\ref{theorem:submodular_objective}
that \relevance~is a monotone submodular set function  
and in Theorem~\ref{theorem:layout_constraints_psystem} that the temporal constraints 
\temporalconstraints~form a $p$-system for $p=2$.
% \todo{(and proven in the Appendix).}
Following Lemma~\ref{theorem:general_approximation_ratio}, our greedy algorithm
has the following approximation bound.
% \vspace{-2mm}
\begin{theorem}
\label{theorem:our_approximation_ratio}
%Our greedy timeline optimization
Algorithm {\sc GreedyTimeline} has an approximation ratio of $1/3$;
that is, 
$$\relevance(s,\hat{T}) / \relevance(s,T^*) \geq 1/3,$$
for any subject $s$, where $\hat{T}$ is the output of our algorithm {\sc GreedyTimeline},
and $T^*$ is the optimal solution.
\label{theorem:our_approximation_guarantee}
\end{theorem}
\vspace{-2mm}
\eat{\vspace{-1.0\baselineskip}
\begin{proof}
We showed that \relevance~is a monotone submodular set
function  in Theorem~\ref{theorem:submodular_objective}.
The temporal constraints 
\temporalconstraints~form a $p$-system for
$p=2$ as stated in Theorem~\ref{theorem:layout_constraints_psystem}. 
% \todo{(and proven in the Appendix).}
Finally, invoking Lemma~\ref{theorem:general_approximation_ratio} concludes the proof.
\end{proof}
}





\subsection{Zooming in or out of the Timeline}
\label{subsec:zoom}

% \begin{figure*}[t]
%   \centering
% %  \includegraphics[width=\linewidth]{timeline_rdjr_zoom_hover.png}
%   % \includegraphics[width=0.8\linewidth]{timeline_rdjr_zoom_hover.png}
%     \includegraphics[width=0.9\linewidth]{timeline_rdjr_zoom_hover_smaller.png}
%   \caption{An example timeline for Robert Downey Jr,
% where we have zoomed in on the most recent years of his life.
% Note the description for the Sherlock Holmes event (award nomination) that gets displayed on mouse over.
% }
%   \label{fig:timeline_rdjr_zoom}
%   % \vspace{-0.5em}
% \end{figure*}

We have proposed an efficient algorithm for generating timelines.
This efficiency (in particular, the
``lazy greedy'' property that allows us to re-use previously computed values)
enables us to quickly (re)compute the optimal timeline
if the user chooses to dynamically zoom in or out of a specific time period. 
In practice, we observe running times roughly linear in the number of events taking a few hundred milliseconds which is much faster than the quadratic theoretical worst case bound.
An example was given in Figure~\ref{fig:timeline_rdjr_zoom},
where we show the timeline
for the most recent few years of Robert Downey Jr.'s life
(\cf, Figure~\ref{fig:timeline_rdjr_full}).
% Compare this to the timeline shown in
% Figure~\ref{fig:timeline_rdjr_full},
% which summarizes his entire life to date.
% The zoomed-in version focuses attention on more recent events,
% such as his award for {\em Tropic Thunder}
% and his role in the {\em Sherlock Holmes} movies.

The default interval for each timeline is computed as follows:
we choose the shortest time
period that covers at least 90\% of all generated events (restricted
to the lifetime of the entity).
Note that for person entities, this time period usually corresponds to less than 90\% of their lifetime
based on the intuition that most interesting events happen to people
after they grow up, but before they retire.
(See Section~\ref{sec:future} for a discussion of when this
heuristic can fail.)

% Note also that our algorithm is able to adapt to different form
% factors, for example for mobile or desktop, since height and width are just
% parameters to the optimization algorithm. 


% \vspace{-.5\baselineskip}

040evaluation_old.tex
% !TEX root = timelines-paper.tex

\todo{I probably jump in verb tense a lot. Check and unify.}
\todo{stress more that we perform qualitative evaluation (see examples and demo, maybe talk about RDJr improvements)}
\todo{stress that we have quantitative evaluation through user study}


This section presents the evaluation of our proposed approach to generate timelines through a series of user studies.
Qualitative examples were shown in Figure~\ref{fig:timeline_rdjr_full} and Figure~\ref{fig:timeline_rdjr_zoom} (zoom).
For more examples, try out our demo\footnote{\label{footnote:demo}\url{http://cs.stanford.edu/~althoff/timelines} (user ``timelines'', password ``84orangehorses'')}.

We investigate the importance of the three\todo{?} quality criteria introduced in Section~\ref{sec:introduction}: Relevance, Temporal Diversity, and Content Diversity.
Since there is are ground truth timeline datasets available we evaluate the relative importance of each of the three quality criteria through a series of user studies on Amazon Mechanical Turk \todo{citation needed}.


\subsection{User Study Instructions}
\label{subsec:user_study_instructions}
Initial user studies showed that evaluating timelines can be challenging and require some domain knowledge.
In particular, raters were often overwhelmed when asked to consider multiple criteria at the same time or when they were not familiar with the timeline subject.
To address these challenges, we ask raters
(1) for relative judgments between two timelines generated by similar approaches so that they can focus on a limited number of differences (we randomize the order of the two timelines shown), 
(2) to only focus and judge one criterion at a time (we control the other two criteria), and 
(3) we largely use head entities that raters would be more likely to be familiar with and ask them to first familiarize themselves with the entity in question by reading the corresponding Wikipedia article and perform searches as needed.
We also ask them to carefully consider all events in the timelines and their respective descriptions (see Section~\ref{subsec:experimental_setup} and Figure~\ref{fig:timeline_rdjr_zoom}).

In addition to the relative judgment for each timeline pair, raters are asked to explain their decision in a few sentences and highlight important differences between the two timelines.
Example explanation of a rating of Robert Downey Jr's timeline (rejecting \textsc{G2E+E2D} in favor of the proposed approach): ``Bottom time line does not include any reference to iron man. Iron man catapulted his comeback in the film industry and should definitely been included in his timeline.''
% There are longer and more expert-like quotes but I think it's good to go with RDJr again.
We also provided a multiple-choice list of major failure cases: 
``Too many repetitions of the same types of events or explanations'', 
``Some descriptions are confusing'', 
``Timelines are identical'', 
``Other reasons'').



\subsection{Baseline}
\label{subsec:baseline}
We compare our approach to a baseline that uses a static global signal (\GtoE~as described in Section~\ref{subsubsec:entity_relevance}) without any reranking or dynamic updates based on temporal or content diversity.
Early user studies showed very negative reactions to bad layout or insufficient content diversity which lead us to explicitly model these criteria and consider user studies that test the three criteria separately.
Otherwise, failures in temporal or content diversity would almost always trump differences in relevance signals requiring explicit control of diversity.
We also found the increased focus to yield more useful and less noisy ratings.

Since the \GtoE~baseline was outperformed so strongly in initial studies, we augment it by enforcing temporal diversity as well as a hard content diversity constraint (do not show the same related entity more than once).
We show below that this augmented baseline (referred to as \textsc{G2E+Div}) is still significantly outperformed by our proposed approach.



\subsection{Experimental Setup}
\label{subsec:experimental_setup}
For the event generation phase (see Section~\ref{sec:generation}) we use the public knowledge base Freebase \cite{Bollacker08}.
While Freebase is known to be incomplete \todo{citation needed} the proposed approach still obtains high coverage (recall Figure~\ref{fig:path_coverage}).

As discussed in Section~\ref{subsec:zoom}, our approach allows for different form factors and can optimally select events for both mobile and desktop environments.
For the evaluation, we only focus on desktop environments and use a height of $n=2$ (1000px width).

Through a number of initial user studies we learned that users tend to prefer the \entityrelevance~signal over the \daterelevance~signal.
Therefore, we emphasize the \entityrelevance~signal in our ``full'' approach \textsc{G2E+E2E+E2D} ($\lambda=0.75$, $w^e_1 = w^d_1 = 1$, $w^e_2 = w^d_2 = 10^{-2}$, and $w^e_3= 10^{-4}$).
This set of parameters is used for all experiments unless noted otherwise.
Note that we use plus signs (+) to indicate addition of signals or components and and use minus signs (-) to indicate removal of signals or components.

To allow users in our user study to understand, differentiate, and judge timeline events it is necessary to explain the events and relationships in natural language (instead of abstract paths over KB predicates).
To this end, we generate English descriptions for each KB path and display them when the user hovers over the event (see Figure \todo{Illustrate hover explanation in zoomed in example} or our interactive demo\footnotemark[\value{footnote}]). %\footnotemark[\ref{footnote:demo}]
We achieve this through a manual mapping of paths to simple patterns such as ``$\sub$ married $re_1$ on $t$.'' for the most frequently occurring 100 paths.
For rare paths we fall back to the English names for the individual predicates in the path which yields understandable but grammatically incorrect descriptions of the relationship captured by the path.




\subsubsection{Evaluation Metrics}
\label{subsubsec:evaluation_metrics}

Each experiment corresponds to a pairwise comparison between two event selection methods for a fixed set of timeline subjects.
Each comparison (method A vs method B on entity \sub) is replicated five times and sent to different raters.
Ratings were collected on a 5 point scale even though we only consider 3 levels, preferring A, tie, or preferring B (initial experiments showed that a 5 point scale yields best ratings even if one is only interested in binary judgments).

We report two orthogonal metrics: rater agreement (how much do raters agree on which timeline is better?), and rater preference (how much do raters prefer one method over the other)?
Rater agreement (RAggr) is measured as the fraction of agreeing pairs of ratings for each entity (e.g. 3A vs 2B would lead to 40\% agreement).
Rater preference (RPref) is calculated by
first aggregating the ratings for each entity and then casting a vote if there is a majority for either A, tie, or B.
Ignoring ties, we compute the fraction of times method A was the majority preference.
If both methods were equally good one would expect a fraction of 50\%. 
We use exact, two-sided binomial tests to measure statistical significance of our results ($H_0: p=0.5)$.

\todo{should we include any other information from the table in \url{https://docs.google.com/spreadsheets/d/146BoTVZdh-h-p_vbfurJvGvJ1Srk3h4el08N8C8Wr7s/edit#gid=0}? e.g. results on rating level or kappa?}


\subsubsection{Experiments}
\label{subsubsec:experiments}
We designed a series of experiments to answer the following questions and shine a light on their relative importance for timeline generation.
Every experiment corresponds to a pairwise comparison between two different timelines selection approaches.
We use a set of 250 popular entities (75 music artists \& bands, 75 actors, 50 politicians, 50 athletes).
Most raters reported to already be familiar with these entities (79\%).
Each pair of timelines is rated by five different raters (1154 distinct raters total).

\xhdr{Relevance} \textit{What relevance signals in event selection are most appreciated by users?}\\
We compare the full approach \textsc{G2E+E2E+E2D} (referred to as \textsc{Full}) to a version without the \EtoD~signal (\textsc{G2E+E2E}; $\lambda=1$), 
a version without \EtoE~signal (\textsc{G2E+E2D}; $w_1^e = w_2^e = 0$), 
\todo{$\lambda=0$ is actually incorrect since it zeroes out G2E.}
and the augmented baseline (\textsc{G2E+Div}; $\lambda = w_3^e = 1$, $w_1^e = w_2^e = 0$; as described in Section~\ref{subsec:baseline}).

\xhdr{Temporal Diversity}: \textit{Do users appreciate having a constrained layout the never overpopulates parts of the timeline?}\\
We compare the full approach \textsc{Full} to a version that does not consider the temporal diversity constraint \textsc{Full-TempDiv} (see Section~\ref{subsec:temporal_constraint}).
More specifically, this version selects the same number of events as the full approach without consideration of the layout constraint, i.e. solving the optimization problem in Equation~\eqref{eq:timeline_optimization} with a simple cardinality constraint instead of \temporalconstraints.
We then remove overlapping event boxes (removing the less relevant event) in the visualization since that causes raters to rate this version worse as shown by previous user studies.
\todo{Should we note that this can be achieved by simply rerunning the optimization with temporal constraints on the candidate set that is the output of the previous ``unconstrained'' run?}
Since this effect was found to be very strong in early studies across a diverse set of entities we use a smaller set of 30 entities for this experiment. 

\xhdr{Content Diversity} \textit{Do users appreciate more diverse events potentially at the expense of relevance?}\\
We compare two different versions of content diversity, hard constraints (strictly permit any duplicate related entities; used in \textsc{Full} approach in previous experiments to ensure that they are not impacted by differences in content diversity), and soft constraints\linebreak[4] \textsc{Full+Soft} using the weighted coverage functions as described in Section~\ref{subsubsec:entity_relevance}
to a version that does not encourage content diversity \textsc{Full-ContDiv}.
In this version, we replace the coverage functions \EtoE, \EtoEPath, and \GtoE~by simple sums over all entities in the timeline (i.e. a sum over a multiset of related entities), including duplicate related entities, and give the full ``reward'' each time.
In contrast, coverage functions are functions over the set of related entities (without duplicates) that only reward one occurrence and thereby encourage diversity).



\subsection{Experimental Results \& Discussion}
\label{subsec:experimental_results}

\newcommand{\signone}{\textsuperscript{}}
\newcommand{\sigone}{\textsuperscript{*}}
\newcommand{\sigtwo}{\textsuperscript{**}}
\newcommand{\sigthree}{\textsuperscript{***}}

\begin{table}[t]
\small
% \fontsize{6}{7.2}\selectfont
\begin{center}
%\setlength{\tabcolsep}{6pt}
\begin{tabular}{p{0.2\columnwidth} p{0.3\columnwidth} r r r@{}l } % p{0.2\columnwidth} %@{\hspace{6pt}} 
\toprule
\textbf{Method A} & \textbf{Method B} & \textbf{\#Raters} & \textbf{RAggr} & \multicolumn{2}{c}{\textbf{RPref}} \\
\midrule
\textsc{Full} & \textsc{G2E+Div} & 344 & 61.8 & 83.8 & \sigthree \\
\textsc{Full} & \textsc{G2E+E2E} & 463 & 60.0 & 59.8 & \sigtwo \\
\textsc{Full} & \textsc{G2E+E2D} & 676 & 56.6 & 64.4 & \sigthree \\
\sectionrule
% \midrule
\textsc{Full} & \textsc{Full-TempDiv} & 53 & 59.3 & 86.7 & \sigthree \\
\sectionrule
% \midrule
\textsc{Full} & \textsc{Full-ContDiv} & 665 & 68.1 & 91.1 & \sigthree \\
\textsc{Full+Soft} & \textsc{Full-ContDiv} & 677 & 68.6 & 90.3 & \sigthree \\
\bottomrule
\sectionrule
\multicolumn{4}{l}{\scriptsize{\textsuperscript{***}$p<0.001$, 
  \textsuperscript{**}$p<0.01$, 
  \textsuperscript{*}$p<0.05$}}
\end{tabular}
% \vspace{-1mm}
\caption{Summary statistics for a series of user studies that each correspond to a pairwise comparison between to different event selection approaches. We report the number of distinct raters that partook in each study, the fraction of agreeing rating pairs (RAggr), as well as the fraction of entities for which raters strictly prefer method A over method B (RPref).
\todo{fix font sizes and presentation somehow. We could add number of entities, ties, and eval on rating level and make it a double column table}. Make last column bold?}
\label{table:evaluation_results}
% \vspace{-3mm}
\end{center}
\end{table}


\begin{figure}[t]
  \centering
  \includegraphics[width=\linewidth]{results_with_conf_int.pdf}
  \caption{Median fraction of entities for which raters preferred method A (first) over method B (second) along with bootstrapped confidence intervals. 
  Raters significantly preferred the proposed approach in all cases.
  \todo{TIM: update figure with new labels.}}
  \label{fig:results_with_ci}
  % \vspace{-0.5em}
\end{figure}

% Tim: I merged results & discussion. Thoughts?
% \subsection{Discussion}
% \label{subsec:discussion}

The experimental results are summarized in Table~\ref{table:evaluation_results}.
Figure~\ref{fig:results_with_ci} shows the fraction of preference for our proposed approach along with bootstrapped confidence intervals.
All differences are statistically significant according to two-sided Binomial tests ($p\ll0.001$; \textsc{G2E+E2E}: $p<0.01$)

The augmented baseline \textsc{G2E+Div} is rejected in favor of our proposed approach in over 83\% of all cases.
This demonstrates that a global importance measure, even in the presence of temporal and content diversity, is clearly insufficient.
The \EtoE~signal is most strongly correlated with user preferences among the three individual signals. 
However, in 60\% of all cases users strictly preferred the full approach over \textsc{G2E+E2E}.
The \EtoD~signal performs quite well by itself, users prefer the full approach in 64\% of all cases.

% should this section with more detailed information about E2E and E2D go somewhere else?
% E2D works best for music artist -> Which events does E2D favor?
% E2E favors what? -> check additional doc
Analyzing the the verticals (music artists, actors, politicians, athletes) individually we found that the \EtoE~signal was more important for actors and athletes and that music artists benefited most from the \EtoD~signal.
Since both signals are based on web co-occurrence they both depend on entity/entity or entity/date co-mentions that are subject to certain conventions on the web.
We found this to be particularly for dates: many articles list date of birth/death, marriage explicitely and be much more vague about the exact time of other events.
For musicians, it is common to mention the date when an album was released (e.g. on semi-structured web-pages like online stores).
It is less common to directly associate e.g. a movie release date with a particular actor and when it is done often only very few star actors are mentioned in these promotional articles.
Restricting oneself to the \EtoD~signal only one also looses the ability to properly distinguish between events with the same timestamp, i.e. should one prefer to show the movie itself, other actors, or the producer at the movie release date?
We further found that the \EtoD~signal has less utility when events do no not exhibit a clear temporal focus such as long military conflicts (compared to birth/death/marriage dates or concert tours).
In these cases, the \EtoE is helpful in providing additional information in the event selection phase.


Users disliked cluttered and unbalanced very strongly in our experiments and prefer the enforcement of temporal diversity constraints (as described in Section~\ref{subsec:temporal_constraint}) 87\% of the time. 

We found equally strong effects when we did not encourage content diversity -- users preferred more diverse timelines over 90\% of the time.
In over 70\% of all cases, the rejected baseline was found to be ``too repetive'', compared to only 12\% for the proposed approach.

Over 70\% of ratings give ``too repetitive'' as a reason for rejecting the less diverse option compared to 12\% when rejecting the proposed approach. 
However, the reason ``irrelevant events'' increases slightly illustrating the trade-off between showing more diverse results and making more mistakes by taking this risk.
It did not matter whether this content diversity was enforced as a constraint (\textsc{Full}) or merely encouraged through diminishing returns as modeled in the submodular objective (\textsc{Full+Soft}).
This means that it is not necessary to add a manual hard constraint in addition to our less strict submodular objective.

Analyzing the ratings for temporal and content separately for each vertical we found that the effect was consistent and significant across all verticals.

We conclude that if one is restricted to a single signal one should go with the \EtoE~signal but that there is significant value in combining \EtoE~and \EtoD~signals.
Using a global static ranking of entity relevance is demonstrated to be insufficient.
We find that it is absolutely crucial to encourage both temporal and content diversity.





\subsection{Error Analysis} % Or conceptual limitations (and failure cases)
\label{subsec:error_analysis}
This section discusses the main error sources identified throughout the series of user studies.

\xhdr{Presentation}
Deciding which time period (or cluster of events) to show is a challenging problem in itself.
For many entities, the most important events happened during a short period of their life.
Therefore, we addressed this challenge by choosing the shortest time period that covers at least 90\% of all generated events (restricted to their lifetime if the timeline entity is a person).
One instance where this failed was for US president John F Kennedy for whom many important events occurred in the last few years of his life (assassination, presidency, Cuban missile crisis, Bay of Pigs invasion etc.).
Because of the algorithm by default attempts to cover 90\% of all generated events the timeline can only contain very few events from this short but important period.
In our concrete case, assassination, presidency, and his marriage to Jacqueline Kennedy Onassis are chosen first and then block other important events such as Cuban Missile Crisis or his involvement in the Vietnam war.
However, this can clearly be improved e.g. (1) by using \EtoD~scores to weight some time periods more important than others or (2) by including the search over suitable time periods as part of the the optimization problem.
Note however, that simply zooming into this period of his life quickly resolves the issue as well.


\xhdr{Representation}
We assume a very simple but flexible format of events (see Section~\ref{sec:generation}) that considers subject, related entity, timestamp and the paths connecting them.
In the vast majority of cases this simple framework encodes all the infqormation necessary.
However, it turns out that in Freebase some CVT nodes (see Section~\ref{sec:CVT}) \todo{Section got removed} are qualified by additional attributes that can be important.
For example the \texttt{/people/marriage/from} is not only used for marriages but also for domestic partnerships (and ignoring this qualification would result in false inferences).
We also found that users reported certain types of events to be confusing, for instance using the date of death as the date that the marriage ended, or describing US presidents as military commanders.
While the President of America is also the Chief of the Armed Forces, a president is never really thought of as a military commander giving military orders, but as a politician.
Additional filters might be necessary to deal with these cases where the powerful representation in knowledge bases can overwhelm the user.
We also note that our event representation only allows for a single timestamp and thus does not capture time periods. 
In this framework, start and end are simply treated as two events and often the algorithm chooses one or the other depending on temporal constraints.
However, our approach could be extended to allow for time periods as well (though the visualization of time periods might impact the formulation of the temporal constraint).


\xhdr{User Preferences \& Personalization}
Users have different preferences and opinions and timelines are not at all exempt to these.
The closer the presented two timelines are in terms of objective quality the easier you can observe when people simply have different opinions rather than all converging to the same objective answer.
Therefore, rater agreement (RAggr) will never be perfect unless there is such a big difference in objective quality that trumps any other personal preferences.
In our experiments, the biggest area of disagreement is over how much the timeline should be focused on professional life (e.g. created artifacts) and personal life and relationships (marriage, children etc).
Users had different opinions, even for the exact same timeline entities, which illustrates the need for personalization in this space.
This also leads to the question whether we should conceptually distinguish between artifacts (e.g. movies, albums, bills, books, military conflicts) and connections (e.g. people, relationships) and plan to investigate this matter in future work.
This would allow for controlled variation in professional vs. personal life events subject to personal preferences.


\xhdr{Extractive vs Abstractive Summarization}
The event selection phase can be viewed as a lifetime summarization task similar to text summarization.
Such tasks are commonly formulated as a selection problem (\todo{do we know of notable examples or exceptions?}) and conceptually belong to the category of extractive summarization methods.
In contrast, abstractive summarization methods build an internal semantic representation and then use natural language generation techniques to create a summary.
Most research, including ours, has focused primarily on extractive methods. 
However, we believe that abstractive techniques could be particularly useful for summarization tasks based on knowledge bases since an internal semantic representation is readily available.
Since our proposed framework subscribes to the extractive approach, the algorithm may be forced to select a single event to describe a multi-faceted relationship.
In the case of Robert Downey Jr, a user noted ``The bottom [timeline] includes more movies, plus includes his father (although the description for his father is weirdly specific).''
His father is also a filmmaker and Robert Downey Jr has starred in one of his father's movies (which is depicted by the event).



040evaluation.tex
% !TEX root = timelines-paper.tex

In this section, we evaluate the quality of our method for producing timelines\footnote{
%
A demo is available at\\
% \small 
\url{http://cs.stanford.edu/~althoff/timemachine}
}.
Since there is no ground truth to compare to, we asked Amazon Mechanical Turk 
%\cite{MechanicalTurk} 
raters
to vote for their preferred timeline.
We do this in a series of paired comparisons
in which we vary one component of the algorithm at a time,
resulting in six different models\footnote{
  Experiments on varying $w_1, w_2, w_3$ show that the results are insensitive to the exact parameter values as long as $w_1 \gg w_2 \gg w_3$ (\cf, backoff-smoothing \cite{Katz87estimationof}, see Section \ref{subsubsec:entity_relevance}).
},
summarized in Table~\ref{tab:experiments}.
The results are shown in 
Table~\ref{table:evaluation_results}
and Figure~\ref{fig:results_with_ci}, and are explained shortly.
%We also performed a bootstrap analysis to estimate a 95\% confidence
%interval on the fraction of users preferring the full model compared
%to each control; this is shown in Figure~\ref{fig:results_with_ci}.

In summary, our experiments show that (1) users always significantly
prefer our full method over baseline and state-of-the-art methods; 
(2) enforcing temporal diversity and content diversity significantly 
improves the results; and (3) both entity relevance and date relevance
contribute to generating a quality entity timeline.



\subsection{Experimental setup}
We generated timelines for
250 popular entities (75 music artists and bands, 75 actors, 50 politicians, 50 athletes)
for each of the six methods in Table~\ref{tab:experiments}.
We chose popular entities instead of random or tail entities because
evaluations cannot be trusted on entities that most raters are not at all familiar with.
% it is very problematic to evaluate timeline quality for entities that most raters would not at all be familiar with.
Popular entities also account for the major share of the total query volume
and their large number of candidate events and often long lifespan makes timeline generation particularly challenging.
%However, internal qualitative evaluations by domain experts showed reasonable quality even for tail entities.
Furthermore, we chose to evaluate timelines through pairwise preferences rather than absolute quality judgments as this has often been found to be less subjective and thus more reliable~\cite{carterette2008here}.


Let $T(e,m)$ denote the timeline for entity $e$ generated by model $m$;
let $m=0$ denote the full model (the control), and let $m=1:5$ denote
one of the ablated models (experimental conditions; described in
Table \ref{tab:experiments} and the following sections).
For each entity $e$, we displayed the control timeline $T(e,0)$ and
the experimental timeline $T(e,m)$ for $m>0$, one above the other;
we randomized the decision whether the experiment or control was shown
on top.

We asked each rater which timeline they preferred, on a 5-point scale,
corresponding to strongly preferring the top one, slightly preferring the top one, being neutral, slightly preferring the bottom one, and strongly preferring the bottom one.
We also asked each rater to give qualitative comments to justify their
decision, to gain further insight.
Each pair of timelines is rated by five different raters (1154 distinct raters in total).
% \todo{making it 1250 tasks per comparison} 
We encouraged raters to research each entity (\eg, using Wikipedia)
before evaluating each timeline about that entity; fortunately,
79\% of raters reported that they were already familiar with these entities.

To simplify the analysis, we collapsed the user
votes to a 3-point scale: prefer control (full model), neutral, or prefer experiment (ablated model).
Let $V(e,m,r) \in \{F, T, A\}$ be the vote by rater $r \in R$ for entity $e \in E$ and method $m \in M$,
where $F$ represents preferring the full model, $T$ represents a tie,
and $A$ represents preferring the ablated model.
% Let $N(e,m,v) = \sum_{r \in R} \delta(V(e,m,r) = v)$ 
Let $N(e,m,v) = |\{ r \in R : V(e,m,r) = v \}|$ 
be the number of raters who voted for category $v \in \{F, T, A\}$,
for entity $e$, and method $m$.
%and let $N(e,m)=5$ be the number of voters who voted for anything in this experiment.
Let $M(e,m) = \argmax_v N(e,m,v)$ be the majority vote.

We compute {\em agreement} between raters (RAggr) as the fraction of raters agreeing with the majority vote
(including tie votes and tied majorities):
\[
\mathit{RAggr}(m) =
\frac{ |\{ V(e,m,r) = M(e,m) : e \in E, r \in R\} | }
{|\{V(e,m,r) : e \in E, r \in R\} | }
\]

We define the rater {\em preference} (RPref) for the full method
as the fraction of times the majority of raters vote for the full
method,
excluding cases where there is no clear majority;
that is, we set $M(e,m)= \mathrm{NULL}$ if the majority is not unique
(\eg, if we have 2 votes for F, 2 for A, and 1 for T):
\[
\mathit{RPref}(m) =
\frac{ |\{ M(e,m)  = F : e \in E \} | }
{|\{M(e,m) \in \{ F, A\} :  e \in E\} | }
\]
(Note that a 5:0 vote in favor of full (5 F, 0 A) is treated the same as a 3:2 vote.)
If both methods are equally good, 
we would expect both the full and the ablated model to win exactly 50\% of the time;
that is, $\mathit{RPref}(m)=0.5$ (our {\em null hypothesis}). 
This allows us to use a simple two-sided Binomial hypothesis
test of significance.
%(null hypothesis $\mathcal{H}_0: RPref(m)=0.5$).




% For each paired comparison, we also compute the fraction
% of raters who agree with each other, as follows:
% \[
% RAggr(m) = 
% \frac{ \sum_{e \in E} \sum_{r \in R} \sum_{r' \neq r}
%   \delta(V(e,m,r) = V(e,m,r')) }
% { \sum_{e \in E} \sum_{r \in R} \sum_{r' \neq r} 1 }
% \]
% For example, for a single entity $e$,
% if we have 3 votes for control and 2 for the experiment,
% then we have 8 agreeing pairs and 12 disagreeing pairs,
% so $RAggr(m) = 0.4$.
% If we have 4 votes for control and 1 for the experiment.
% we have 12 agreeing pairs and 8 disagreeing pairs,
% so $RAggr(m) = 0.6$.
% \kevin{This seems totally messed up!}


% The methods that we compared are listed in Table~\ref{tab:experiments}.
% The goal is to evaluate how important the different relevance signals are,
% how important temporal diversity is, and how important content diversity is.
% We will discuss these methods in more detail below.

% \begin{table}
% \begin{center}
% \begin{tabular}{l|lll|ll|ll}
% \textbf{Name} & $\mathbf{w_1^e}$ & $\mathbf{w_2^e}$ & $\mathbf{w_3^e}$ 
% & $\mathbf{w_1^d}$ & $\mathbf{w_2^d}$ & \textbf{TD} & \textbf{CD} \\ \hline
% \textsc{Full} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 1 & 1 \\
% \textsc{Base} & 0 & 0 & 1 &0  & 0 & 1 & 1 \\
% \textsc{Full-E2D} & 1 & $10^{-2}$ & $10^{-4}$ &0  & 0 & 1 & 1 \\
% \textsc{Full-E2E} & 0 & 0 & $10^{-4}$ &1  & $10^{-2}$ & 1 & 1 \\
% \textsc{Full-TD} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 0 & 1 \\
% \textsc{Full-CD} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 1 & 0 
% \end{tabular}
% \end{center}
% \caption{Summary of experimental configurations.
% We fix $\lambda=0.75$ throughout.
% TD = temporal diversity, CD = content diversity.
% FULL-TD means the full model without temporal diversity, etc.
% Note that  all methods remove duplicate events, which is a minimal
% form of content diversity, but if CD=1, we ensure diversity amongst
% types of events as well; see text for details.
% \label{tab:experiments}
% }
% \end{table}

% table with new design
\begin{table}
\begin{center}
\resizebox{.9\columnwidth}{!}{%\columnwidth
  \begin{tabular}{l|lll|ll|ll}
  \toprule
  \textbf{Name} & $\mathbf{w_1^e}$ & $\mathbf{w_2^e}$ & $\mathbf{w_3^e}$ 
  & $\mathbf{w_1^d}$ & $\mathbf{w_2^d}$ & \textbf{TD} & \textbf{CD} \\
  \midrule
  \textsc{Full} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 1 & 1 \\
  \textsc{Base} & 0 & 0 & 1 &0  & 0 & 1 & 1 \\
  \textsc{Full-E2D} & 1 & $10^{-2}$ & $10^{-4}$ &0  & 0 & 1 & 1 \\
  \textsc{Full-E2E} & 0 & 0 & $10^{-4}$ &1  & $10^{-2}$ & 1 & 1 \\
  \textsc{Full-TD} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 0 & 1 \\
  \textsc{Full-CD} & 1 & $10^{-2}$ & $10^{-4}$ & 1 & $10^{-2}$ & 1 & 0 \\
  \bottomrule
  \end{tabular}}% end resizebox
\end{center}
\vspace{-5mm}
\caption{Summary of experimental configurations.
We fix $\mathbf{\lambda=0.75}$ throughout.
TD = temporal diversity, CD = content diversity.
FULL-TD means the full model without temporal diversity, etc.
Note that  all methods remove duplicate events, which is a minimal
form of content diversity, but if CD=1, we ensure diversity amongst
types of events (entities and paths) as well; see Section \ref{subsec:eval_content_diversity} for details.
\label{tab:experiments}
% \vspace{-2mm}
}
\end{table}


\newcommand{\signone}{\textsuperscript{}}
\newcommand{\sigone}{\textsuperscript{*}}
\newcommand{\sigtwo}{\textsuperscript{**}}
\newcommand{\sigthree}{\textsuperscript{***}}

\begin{table}[t]
% \small
\begin{center}
  \resizebox{.9\columnwidth}{!}{%\columnwidth
  \begin{tabular}{lrrll}
  \toprule
  \textbf{Ablated model} & \textbf{\#Tasks} & \textbf{\#Raters} & \textbf{RAggr} & \textbf{RPref} \\
  \midrule
  %% Table for RAggr = fraction of pairs agreeing
  % \textsc{Base} & 344 & 61.8\% & 83.8\% \sigthree \\
  % \textsc{Full-E2D} & 463 & 60.0\% & 59.8\% \sigtwo \\
  % \textsc{Full-E2E} & 676 & 56.6\% & 64.3\% \sigthree \\
  % \textsc{Full-TD} & 53 & 59.3\% & 86.7\% \sigthree \\
  % \textsc{Full-CD} & 665 & 68.1\% & 91.1\% \sigthree \\
  %% Table for RAggr= agree w majority vote.
  \textsc{Base} & 1250 & 344 & 77.0\% & 83.8\% \sigthree \\
  \textsc{Full-E2D} & 1250 &  463 & 75.7\% & 59.8\% \sigtwo \\
  \textsc{Full-E2E} & 1250 &  676 & 73.2\% & 64.3\% \sigthree \\
  \textsc{Full-TD} & 150 &  53 & 75.3\% & 86.7\% \sigthree \\
  \textsc{Full-CD} & 1250 &  665 & 81.0\% & 91.1\% \sigthree \\
  \bottomrule
  \sectionrule
  \multicolumn{4}{l}{\scriptsize{\textsuperscript{***}$p<0.001$, 
    \textsuperscript{**}$p<0.01$, 
    \textsuperscript{*}$p<0.05$}}
  \end{tabular}} % end resizebox
\vspace{-2.5mm}
\caption{Summary of the user studies.
Each row shows an ablated version that was compared to the full model.
The asterisks represent the p-value corresponding to a Binomial hypothesis test
that compares the RPref value to 50\%.
\vspace{-3.5mm}
}
\label{table:evaluation_results}
\end{center}
\end{table}


% \begin{table}[t]
% \small
% % \fontsize{6}{7.2}\selectfont
% \begin{center}
% %\setlength{\tabcolsep}{6pt}
% \begin{tabular}{p{0.2\columnwidth} p{0.3\columnwidth} r r r@{}l } % p{0.2\columnwidth} %@{\hspace{6pt}} 
% \toprule
% \textbf{Method A} & \textbf{Method B} & \textbf{\#Raters} & \textbf{RAggr} & \multicolumn{2}{c}{\textbf{RPref}} \\
% \midrule
% \textsc{Full} & \textsc{G2E+Div} & 344 & 61.8 & 83.8 & \sigthree \\
% \textsc{Full} & \textsc{G2E+E2E} & 463 & 60.0 & 59.8 & \sigtwo \\
% \textsc{Full} & \textsc{G2E+E2D} & 676 & 56.6 & 64.3 & \sigthree \\
% \sectionrule
% % \midrule
% \textsc{Full} & \textsc{Full-TempDiv} & 53 & 59.3 & 86.7 & \sigthree \\
% \sectionrule
% % \midrule
% \textsc{Full} & \textsc{Full-ContDiv} & 665 & 68.1 & 91.1 & \sigthree \\
% %\textsc{Full+Soft} & \textsc{Full-ContDiv} & 677 & 68.6 & 90.3 & \sigthree \\
% \bottomrule
% \sectionrule
% \multicolumn{4}{l}{\scriptsize{\textsuperscript{***}$p<0.001$, 
%   \textsuperscript{**}$p<0.01$, 
%   \textsuperscript{*}$p<0.05$}}
% \end{tabular}
% % \vspace{-1mm}
% \caption{Summary statistics for a series of user studies that each correspond to a pairwise comparison between to different event selection approaches. We report the number of distinct raters that partook in each study, the fraction of agreeing rating pairs (RAggr), as well as the fraction of entities for which raters strictly prefer method A over method B (RPref).
% \todo{fix font sizes and presentation somehow. We could add number of entities, ties, and eval on rating level and make it a double column table}. Make last column bold?}
% \todo{update labels.}
% \label{table:evaluation_results}
% % \vspace{-3mm}
% \end{center}
% \end{table}



\vspace{-.4\baselineskip}
\subsection{Baseline Algorithms}
\label{sec:baseline}

In our initial trial, we defined the baseline algorithm as follows:
rank all the candidate events by the \GtoE~global entity score,
and then show the top $K$ events (where each event is represented
by a box on a timeline of width 1000 pixels,
and we allow up to $n=2$ boxes to be stacked vertically).
However, we found that the \GtoE~score sometimes picked
the same related entity more than once
(\eg, if Robert Downey Jr. starred in {\em Iron Man} and later won an award for it,
we may display {\em Iron Man} twice, at two different time points).
Users strongly disliked this in preliminary experiments, so
we decided to augment the baseline through post-filtering all results by removing duplicate entities from all methods
(except Section \ref{subsec:eval_content_diversity}),
keeping the highest scoring event in each case (we never allow duplicate events).

In addition, we noticed that the baseline model would sometimes result in visual crowding,
since it does not enforce temporal diversity. 
Users strongly disliked this as well,
so we decided to further improve the baseline by post-processing all results and
removing temporally overlapping events, keeping the highest scoring
event in each case.

In practice, we can implement this modified baseline \textsc{Base} by using our
constrained submodular optimization algorithm, but setting
the weights so that $w_1^e=w_2^e=w_1^d=w_2^d=0$ and $w_3^e=1$,
thus putting all the emphasis on the \GtoE~signal. 
This is because the greedy optimization algorithm will ensure that it 
never adds an event that temporally overlaps an existing event.
Most of the time our submodular coverage function does not yield any duplicate entities.
In the rare case that the optimization does lead to duplicate entities,
we explicitly remove them to ensure that entity diversity has no impact on any other experiment 
(except Section \ref{subsec:eval_content_diversity} that explicitly measures the importance of content diversity).

% Note that we do measure the impact of both content and temporal diversity quantitatively through additional experiments (see Section \ref{subsec:eval_temporal_diversity} and \ref{subsec:eval_content_diversity}).
%Note that the submodular optimization method naturally enforces both content and temporal diversity,
%but we decided to apply these two hard filters to all the methods,
%so that we could focus on more subtle differences between the methods.


We can see from the results
(Table~\ref{table:evaluation_results} and Figure~\ref{fig:results_with_ci})
that on average, 84\% of the time raters prefer our full model 
(significant difference at $p<0.001$ according to a Binomial test).
This shows that a global relevance score is inadequate, even when augmented by temporal diversity and content diversity.







% moved this a bit back to make sure it's after both tables
\begin{figure}[t]
  \centering
  \includegraphics[width=\linewidth]{results_with_conf_int_newlabels.pdf}
  \vspace{-8mm}
  \caption{Fraction of entities for which raters preferred Full approach over ablated version (RPref) along with 
bootstrapped 95\% confidence intervals.
Results show significant preference for our proposed approach in all cases.
\vspace{-1mm}
}
  \label{fig:results_with_ci}
  % \vspace{-0.5em}
\end{figure}


The only other relevant baseline known to us is the CATE system described in~\cite{tuan2011cate}.
CATE ranks related entities by co-occurrence with the timeline entity within documents of a given context. 
%While the authors present a language generation perspective on their approach 
This approach is very similar to the \EtoE~approach described in Section~\ref{subsubsec:entity_relevance}. 
We consider our \EtoE~signal as an improvement over the CATE baseline since, 
first, we only consider more direct connections between entities in a KB compared to co-occurrence within the same document.
Second, our relevance signal captures co-occurrence on a large web corpus within a small window which gives higher coverage and more focus compared to document-wide co-occurrence within Wikipedia only.
And third, we perform subset selection instead of a static ranking
which allows selected events to influence which other events are
selected next.
Section~\ref{subsec:eval_relevance_signals} shows that our methods
outperform \EtoE.
% no fallback on G2E
%Therefore, the reported result also shows indirectly that our technique outperforms the current state of the art.




% \pagebreak[4] % header alone
\subsection{Evaluating Relevance Signals}
\label{subsec:eval_relevance_signals}

To compare the  different ways of measuring event relevance,
we performed two experiments.
First, we ``turned off'' the date signal \daterelevance, by setting
$w_1^d=w_2^d=0$. We call this model Full-E2D, meaning the full model
without the E2D signal. Raters prefer our full model to this version about 60\%
of the time, which is a significant difference at the level of $p<0.01$
(Binomial test).

The utility
of the date signal depends on which kind of entity we are creating a
timeline for. For people, it is common to find the date of 
birth, death, marriage or other key events to be explicitly mentioned on the web;
this makes it relatively easy to determine that these events are
important.\footnote{Of course, our system treats birth and death dates as special, since
they inform the beginning and end of the timeline for a person (see Section \ref{subsec:zoom}).}


Second, we ``turned off'' the \entityrelevance~signal, 
by setting $w_1^e=w_2^e=0$. We call this model Full-E2E.
Raters prefer our full
model to this about 64\% of the time, indicating that the E2E signal is somewhat
more important than E2D (significant at $p<0.001$). 

However,
the benefit of the E2E signal varied by domain/vertical: we found it
most useful for actors and athletes, 
whereas for musicians, the E2D signal was more helpful.
We attribute this to conventions in what entities and dates are co-mentioned on the web (in close proximity).
E2D works well for music artists because important dates such as album release dates and tour dates are frequently mentioned across many websites (online stores, ticketing websites, etc.).
%
However, this is different in the movie domain.
There are many more entities related to the movie (director, producer, dozens of actors, etc.) and only a few of them will be highlighted in close proximity to the movie release date (usually one or two star actors). 
How helpful the E2D signal is depends on what usually gets mentioned in close proximity of the date,
which is subject to certain conventions and marketing decisions.
%
For instance, the first {\em Pirates of the Caribbean} movie (2003) has a lower E2D score for actor Johnny Depp
than later sequels even though the first movie was the bigger milestone for Johnny Depp's career.
The sequel promotions just featured Johnny Depp (who had gained in popularity) more prominently.
We found the \EtoE~signal to be more generally applicable and less influenced by such effects.

We further found that the \EtoD~signal has less utility when events do not exhibit a clear temporal focus such as long military conflicts (compared to birth/death/marriage dates or concert tours).
In these cases, the \EtoE~signal is helpful in providing additional information in the event selection phase.


\subsection{Evaluating Temporal Diversity}
\label{subsec:eval_temporal_diversity}

As we mentioned in Section~\ref{sec:baseline}, users strongly dislike
when displayed events overlap in time, since it is not easy to see the corresponding
images and descriptions. 
Indeed, we see that in 86\% of the experiments,
raters prefer our full model over 
an ablated version, which we call Full-TD,
that maximizes relevance and content
diversity but without any temporal constraint 
(significant at $p<0.001$).
This is despite the fact
that the ablated model also includes the simple overlap filter we
described in Section~\ref{sec:baseline}.
The number of events we show is controlled and set to the number of events in our Full approach,
as we aim to measure the impact of temporal diversity while controlling for the amount of information shown
(though the overlap filter may remove some of them).
The reason the full model works better is that it can take into
account the temporal overlap during the optimization process, so if
one event is removed, another (non-overlapping) event can be added instead.


% \pagebreak[4] % otherwise alone
\subsection{Evaluating Content Diversity}
\label{subsec:eval_content_diversity}

As we mentioned in Section~\ref{sec:baseline}, users strongly dislike
when the same entity is repeated (with different timestamps), so we
always remove such cases from all methods.
Here, we quantify the importance of content diversity in generating timelines.
Note that in addition to entity diversity there are other, 
slightly more subtle forms of content diversity that we might
wish to consider. For example, we might not want to list only the
different movies that an actor has been in, even if they all have high relevance
scores; instead we wish to include awards, TV shows, and personal relationships as well.
Our submodular set cover objective captures this by using the \EtoEPath\ 
feature, which gives higher score to a set of events with distinct path types
 (see Section~\ref{subsubsec:entity_relevance}).

To evaluate this, we consider an alternative model
in which we evaluate the score by summing over the multiset (rather
than set) of related entities (or paths to related entities),
allowing for duplicate entities or paths during the optimization
process; we call this Full-CD. We see that raters prefer our full
model 91\% of the time compared to this ablated model 
(significant at $p<0.001$).
Again, we attribute this to the fact that the full model is aware of
the penalty for duplication during the optimization process, and can
adjust its output appropriately.



\eat{
\subsection{Summary}
\label{subsec:eval_summary}
\vspace{-1\baselineskip}
\todo{
\begin{itemize}
\item We evaluate timeline quality through a series of paired comparisons 
      in which we vary one component of the algorithm at a time 
      and ask raters for relative judgments.
\item A static ranking based on a global relevance score is inadequate, 
      even when augmented by temporal diversity and content diversity.
\item The \EtoE~and the \EtoD~signal lead to significant performance improvements 
      but are outperformed by the full model representing a combination of both signals.
\item Raters show a very strong preference for temporal diversity as well as content diversity.
\end{itemize}
}
\vspace{-1\baselineskip}
}

050relatedwork.tex
% !TEX root = timelines-paper.tex

% based on: https://docs.google.com/document/d/1wzJbxfrU3eeh5-KZtsTvddiYw13J3LEVb20kliUQxlI/

There has been much
work on extracting temporal events from text
\cite{ji2013tackling,ling2010temporal},
 and in summarizing large text corpora
such as tag streams \cite{dubinko2007visualizing}, news corpora \cite{do2012joint}, Wikipedia biographies \cite{bamman2014unsupervised}, and Wikipedia edit histories \cite{tran2014wikipevent}.
%There has even been work on predicting future events given textual evidence %\cite{radinsky2012learning,radinsky2013mining}.
There has also been work on mining temporal patterns across such textual data sets
\cite{huet2013mining,suchanek2014semantic,weikum2011longitudinal}. %mei2005discovering removed for space


Another body of related work concerns document summarization
\cite{allan2001temporal,sparck2007automatic}.
The evaluation of summarization approaches has always been challenging,
and measures like Rouge \cite{lin2004rouge} are often used if ground truth summaries are available.
In our case, we use paired comparisons, since we do not have ground truth.

The summarization and IR communities have identified diversity as an important quality criterion \cite{carbonell1998use,lin2012learning}.
More recently, research has focused on complementing traditional corpus-based relevance measures with signals such as social attention \cite{zhao2013timeline}.
Early work on timeline generation by Swan and Allan \cite{swan2000automatic} attempted to summarize a news corpus by displaying major events and topics along a timeline. % TODO consider: swan2000timemines
In a similar spirit, Shahaf et al. \cite{shahaf2013information} have created maps of information that summarize complex storylines across news documents.
Similar techniques have been applied to scientific literature \cite{shahaf2012metro,sipos2012temporal}.
Our paper extends this line of work by using multiple relevance signals 
(based on web co-occurrence), 
as well as showing that content and temporal diversity are critical for quality timelines.

Submodular optimization has been shown to be a powerful framework for summarization \cite{kannan2014mining,lin2012learning,shahaf2012metro,shahaf2013information,sipos2012temporal},
since it naturally captures notions of diversity through its diminishing returns properties \cite{dasgupta2013summarization}.
Furthermore, there are 
efficient approximation algorithms with theoretical guarantees
\cite{ahmed2012fair,calinescu2011maximizing,krause2012submodular,leskovec2007cost,minoux1978accelerated,nemhauser1978analysis}.

Some recent work has focused on generating personalized timelines based on Facebook \cite{graus2013yourhistory} or Twitter feeds \cite{li2014timeline}.
Timelines generated based on information from KBs have been considered in \cite{mazeika2011entity,tuan2011cate,wang2010timely}; 
these papers are the ones most related to our approach.
However, there are several differences.
First, 
\cite{mazeika2011entity,wang2010timely} do not consider a ranking of individual events
(required when space is limited) nor visual space constraints, so there is no optimization algorithm involved. 
Instead, they simply display all events which is not an option in our context as each timeline entity might have hundreds of candidate events (see Figure~\ref{fig:path_coverage}).
We have empirically shown that it is absolutely necessary to address relevance, redundancy, and space constraints to generate quality timelines.
Second, \cite{tuan2011cate} considers ranking related entities but uses a different notion of relatedness (sharing many contexts rather than more direct connections in the KB). 
In this approach, it is impossible to capture relationships between selected events as the ranking is static.
To the best of our knowledge, this is the only relevant baseline and we show in Section~\ref{subsec:eval_relevance_signals} that our proposed method outperforms an improved reimplementation of this approach.
Third, none of these papers conducts any quantitative evaluation of their timelines.

Finally, we should mention that
Bing \cite{BingTimeline} has released a system called ``Timeline'' that is somewhat similar to ours.
However, there are (to the best of our knowledge) no published accounts of how their system works.
Furthermore, their timelines are static, and do not allow the user to interact with the timeline, a feature which we consider to be very important, especially for mobile browsing.


% \pagebreak[4] % header alone


\begin{comment}
% Knowledge Base
In recent years, there has been substantial progress on the creation, curation, extension, and use of knowledge bases
such as early work on Yago \cite{suchanek2007yago} and Freebase \cite{Bollacker08}, spatial and temporal extensions \cite{wang2010timely,hoffart2011yago2,hoffart2013yago2}, and, very recently, automatic extraction methods to create Web-scale probabilistic knowledge bases such as Knowledge Vault \cite{Dong14}.
% Vision Paper
Very recently, Suchanek and Predia \cite{suchanek2014semantic} discussed the potential of combining textual documents with semantic knowledge from KB to discover trends in history and culture (``Semantic Culturomics'').
Similar visions have been discussed in \cite{weikum2011longitudinal} and exemplified in \cite{huet2013mining}.
This work represents a step into this direction attempting to summarize and communicate history effectively based on a KB of facts.

% Temporal Information Extraction
Building timelines from KBs requires high coverage of events and temporal information.
Temporal information extraction has been a research topic in the natural language processing community for several years \cite{ling2010temporal} and is regaining popularity in the context of temporal knowledge base population \cite{ji2013tackling}.
The importance of time in classic information retrieval was recognized in \cite{alonso2009clustering}.
Recent work has focused on extracting events from sources such as news corpora \cite{do2012joint}, Wikipedia biographies \cite{bamman2014unsupervised}, and Wikipedia edit histories \cite{tran2014wikipevent}.
% Event Prediction (Radinsky et al)
Some work has focused on predicting future events \cite{radinsky2012learning,radinsky2013mining}.

% Document Summarization
We find that even incomplete knowledge bases such as Freebase \cite{Bollacker08} contain enough event information that it becomes challenging to decide on which to focus and how to summarize the entity's lifetime most appropriately.
Such challenges have been addressed in the context of document summarization \cite{allan2001temporal,sparck2007automatic}.
The evaluation of summarization approaches has always been challenging and measures like Rouge \cite{lin2004rouge} are often used if ground truth summaries are available.
The summarization as well as the information retrieval community has identified diversity as an important quality criterion \cite{carbonell1998use,lin2012learning} shells.
More recently, research has focused on complementing traditional corpus-based relevance measures with signals such as social attention \cite{zhao2013timeline}.
Early work on timeline generation by Swan and Allan \cite{swan2000automatic} attempted to summarize a news corpus by displaying major events and topics along a timeline.
In a similar spirit, Shahaf et al. \cite{shahaf2013information} have created maps of information that summarize complex storylines across news documents.
Similar techniques have been applied to scientific literature \cite{shahaf2012metro,sipos2012temporal} and summarizing text snippets describing image content \cite{kannan2014mining}.
The present paper extends this line of work in mining the web for additional relevance signals to summarize large sets of historical events as well as proving that both content and temporal diversity are critical in building quality timelines.
% Submodular optimization.
In many cases, submodular optimization has proven to be a powerful framework for summarization \cite{lin2012learning,shahaf2013information,shahaf2012metro,sipos2012temporal,kannan2014mining} for which efficient approximation algorithms with theoretical guarantees exist \cite{leskovec2007cost,ahmed2012fair,krause2012submodular,minoux1978accelerated,nemhauser1978analysis,calinescu2011maximizing}, and which can naturally capture notions of diversity through its diminishing returns properties \cite{dasgupta2013summarization}.

% Timelines (personal; then in KB context)
Some recent work has focused on generating personalized timelines based on Facebook \cite{graus2013yourhistory} or Twitter feeds \cite{li2014timeline}.
Timelines generated based on information from KBs have been considered in \cite{mazeika2011entity,tuan2011cate,wang2010timely} and represent the work most related to ours.
However, this work has considered simple and indirect notions of relatedness (sharing many contexts rather than more direct connections in the KB) \cite{tuan2011cate} or not considered ranking events at all \cite{wang2010timely,mazeika2011entity} .
Previous work has not explicitly considered timeline generation as a summarization problem nor identified temporal and content diversity as important criteria.
It has, however, used the KB type hierarchy for generalization \cite{mazeika2011entity}.
Furthermore, it has lacked quantitative evaluation thus far as ground truth timelines are not readily available.
\end{comment}

060conclusion.tex
% !TEX root = timelines-paper.tex

We presented a system called \systemname\ for automatic timeline generation for entities in a knowledge base.
The timeline generation problem is formulated in a submodular optimization framework that jointly optimizes for relevance, content diversity and temporal diversity.
Web-based co-occurrence signals are used to determine the relevance of other entities and dates to the timeline subject.
We proved that an efficient greedy approximation algorithm achieves near-optimal performance.
The proposed approach is evaluated through a comprehensive series of user studies demonstrating that both temporal diversity and content diversity are crucial, and that web-based co-occurrence signals significantly improve over a baseline model that relies on global importance.


070appendix.tex
% !TEX root = timelines-paper.tex

%\subsection{Layout Constraint}
%\label{subsec:appendix_layout_constraint}
\subsection{Proof of Approximation Guarantee}
We repeat the definition from Section \ref{subsec:temporal_constraint}: A set $T \subseteq E$ of events satisfies the layout constraint $\temporalconstraints(T, E, \mathcal{W}, w, n)$  if
\begin{align}
\forall t\in \mathds{R}: |T \sqcap [t, t+t_w) | \leq n \tag{\ref{eq:LayoutConstraint}}
\end{align}

This can be checked very efficiently because of the following equivalent formulation:
Let $\tFun(Y) = \{ \tFun(y) \;|\; y \in Y \}$ be the set of timestamps for all events
in some subset of events $Y \subseteq E$.

\begin{theorem}{Equivalence of layout constraints}
\eqref{eq:LayoutConstraint} $\Leftrightarrow$~\eqref{eq:LayoutConstraintAlternative}
\begin{align}
\forall S\subseteq T, |S| \geq n+1: \max(\tFun(S)) - \min(\tFun(S)) \geq t_w \label{eq:LayoutConstraintAlternative}
\end{align}
\end{theorem}
\vspace{-3mm}
\begin{proof}
1. Show $\neg$~\eqref{eq:LayoutConstraintAlternative} $\Rightarrow$ $\neg$~\eqref{eq:LayoutConstraint}:
\begin{align*}
\exists S\subseteq T, |S|\geq n+1: \max(\tFun(S)) - \min(\tFun(S)) < t_w
\end{align*}
Let $S^*$ be a witness for such a set $S$, 
Let $t' = \min(\tFun(S^*))$ and $t'' = \max(\tFun(S^*))$ (note that $t'+t_w > t''$). 
Then with $S^* = S^* \sqcap [t', t'') = S^* \sqcap [t', t'+t_w) \subseteq T$ 
\begin{align*}
& |S^* \sqcap [t', t'+t_w) | >= n + 1\\
\Rightarrow& |T \sqcap [t', t'+t_w) | >= n + 1\\
\Rightarrow& \exists t\in \mathds{R}: |T \sqcap [t, t+t_w) | >= n + 1 \;\; \lightning
\end{align*}


2. Show $\neg$~\eqref{eq:LayoutConstraint} $\Rightarrow$ $\neg$~\eqref{eq:LayoutConstraintAlternative}
\begin{align*}
\exists t\in \mathds{R}: |T \sqcap [t, t+t_w) | >= n + 1
\end{align*} 
Let $t^*$ be one such $t$. Define $S^* = T \sqcap [t^*, t^*+t_w)$.
\begin{align*}
\exists S^*\subseteq T, |S^*|\geq n: \max(\tFun(S^*)) - \min(\tFun(S^*)) < t_w \;\; \lightning
\end{align*} 
\end{proof}


In order to show that we can get a good approximation to the optimal solution to Equation~\eqref{eq:timeline_optimization} (see Section~\ref{subsec:timeline_optimization}) through an efficient greedy algorithm 
we now show that the independence family $(E,\mathcal{I})$, where $T \in \mathcal{I}$ if $T$ satisfies Equation~\eqref{eq:LayoutConstraint} ($T \subseteq E$), is a $p$-system for $p=2$.

Let $J_{\max}$ and $J_{\min}$ be bases of $Y \subseteq E$ with $|J_{\max}| =$\\
$\max_{J:J \text{ is a base of } Y} |J|$ and $|J_{\min}| = \min_{J:J \text{ is a base of } Y} |J|$ 
(recall Section \ref{subsec:submodular_function_maximization}).
We choose $Y \subseteq E$ instead of $T \subseteq E$ in this definition to highlight that the $p$-systems property (Equation \eqref{eq:p_systems_property}) has to hold for all subsets of events and not only for the timeline subset $T$.

\begin{definition}%{\textit{Blocked}\\}
We say an element $a \in E$ is \textit{blocked} in independent set $T$
(below this will be either $J_{\min}$ or $J_{\max}$)
if it could not be added to $T$ without violating the layout constraint (Equation~\eqref{eq:LayoutConstraint}). 
Formally, this means $T \in \mathcal{I}$ but $T \cup \{a\} \notin \mathcal{I}$.
\end{definition}

\begin{definition}%{\textit{ball} neighborhood\\}
We define a $2 \, t_w$ \textit{ball} around $e \in E$ as the following interval: $ball(e) = (\tFun(e)-t_w, \tFun(e)+t_w)$.
%One property that we make use of is that if $a$ blocked in $T$ we have 
%$(T \sqcap ball(a)) \geq n$ since there must be some interval of size
%$w$ containing $a$ that has at least $n$ elements. 
%Otherwise $a$ would not be blocked and could be added to $T$ while remaining an independent set.
\end{definition}

\begin{lemma}
If $a$ is blocked in $T$ we have $(T \sqcap ball(a)) \geq n$.
\end{lemma}
\vspace{-5mm}
\begin{proof}
There must be some interval of size
$t_w$ containing $a$ that has at least $n$ elements,
otherwise $a$ would not be blocked and could be added to $T$ while
remaining an independent set. 
\end{proof}

\begin{definition}%{\textsc{DeletionStep}}\\
We define the \textsc{DeletionStep} algorithm as follows:
Input: $J_{\min}, J_{\max}$\\
Output: $J_{\min}', J_{\max}'$
\begin{enumerate}
\item Let $b$ be the minimum element in $J_{\min}$. 
Let $J_{\min}' = J_{\min} \setminus \{b\}$; that is, we delete $b$.
\item Let $a_1, \dots, a_n$ be all elements in $J_{\max} \sqcap ball(b)$ in sorted order (i.e. $a_1 \leq a_2 \leq \dots \leq a_n$).
Let $J_{\max}' = J_{\max} \setminus \{a_1, a_2\}$; that is, we delete the first two elements 
(if both elements exists, otherwise just delete one or zero elements).
\end{enumerate}
\end{definition}
This algorithm is helpful in proving Theorem~\ref{theorem:layout_constraints_psystem}
for the following reason. 
If we can delete all elements from $J_{\max}$ eventually using multiple iterations of \textsc{DeletionStep} 
then $J_{\max}$ can be at most twice as large as $J_{\min}$ (which is exactly what we need to show). 


\begin{definition}%{\textit{Invariant}\\}
We define the following \textit{invariant}:
Let $J_{\min}$ and $J_{\max}$ be minimal and maximal bases of $Y$.
\begin{align}
\forall a \in J_{\max}: J_{\min} \sqcap ball(a) \neq \emptyset \label{eq:DeletionInvariant}
\end{align}
This invariant captures the necessary condition to be able to delete every element in $J_{\max}$ eventually because for every such element we have an element in $J_{\min}$ that could still delete it. 
Next we show that this condition is actually invariant under the previously defined \textsc{DeletionStep}.
This means that we will be able to delete every element in $J_{\max}$ eventually (used in the proof of Theorem~\ref{theorem:layout_constraints_psystem}).
\end{definition}



\begin{figure}[t]
  \centering
  \includegraphics[width=0.8\linewidth]{proof_intuition.pdf}
  \vspace{-2mm}
  \caption{Intuition for proof of Lemma \ref{Lemma:DeletionInvariance} ($n=1$ for simplicity). 
  Case (a) is possible while (b) and (c) show impossible situations (see proof for details).
}
  \label{fig:proof_intuition}
  % \vspace{-0.5em}
\end{figure}


% candidate for shortening.
Intuitively, this invariant holds because we can never have an element
in $J_{\max}$ 
which is not covered in the sense of the invariant,
 since then either (1)
$J_{\min}$ has too few points to be a maximal independent set (base),
or (2) $J_{\max}$ has too many points to be an independent set.
This intuition is illustrated in Figure \ref{fig:proof_intuition} (for $n=1$).
Case (a) shows a possible situation in which each element in
$J_{\max}$ has an element in $J_{\min}$ ``in range'' and both
$J_{\min}$ and $J_{\max}$ are valid bases. 
Case (b) illustrates an impossible case in which there is no
corresponding element in $J_{\min}$ for the rightmost element of
$J_{\max}$.  
In this case the rightmost element could be added to $J_{\min}$ while remaining an independent set so $J_{\min}$ cannot be a base.
Case (c) illustrates a different impossible case in which $J_{\max}$
has too many points to be an independent set.
We have $n=1$ but there are two points in close proximity.


\begin{lemma}%{Invariant under \textsc{DeletionStep}\\}
\label{Lemma:DeletionInvariance}
Let $J_{\min}$ and $J_{\max}$ be minimal and maximal bases of $Y$.
Let $J_{\min}'$ and $J_{\max}'$ be the sets obtained from $J_{\min}$ and $J_{\max}$ after one or more iterations of \textsc{DeletionStep}.
The invariant (Eq.~\ref{eq:DeletionInvariant}) holds initially and after any iteration of \textsc{DeletionStep}.
\end{lemma}
\vspace{-3mm}
\begin{proof}
\textit{Invariant holds initially.\\}
Let $a \in J_{\max}$.
Initially, $J_{\min} \sqcap ball(a) \neq \emptyset$ since otherwise $a$ could be added to $J_{\min}$ ($a$ not blocked in $J_{\min}$) for a contradiction with $J_{\min}$ maximal independent set or base (cf. Figure~\ref{fig:proof_intuition} (b)). $\lightning$

\textit{Invariant holds after any number of \textsc{DeletionStep}.\\}
We now show by contradiction that the invariant holds after one or more iterations of
\textsc{DeletionStep}.
Let $J_{\min}$ and $J_{\max}$ be the bases before the \textsc{DeletionStep}(s),
and let $J'_{\min}$ and $J'_{\max}$ be the bases afterwards.
Assume the invariant holds before but not after.
Let $a^* \in J_{\max}$ be an element for which the invariant is now
violated,
so $J_{\min}' \sqcap ball(a^*) = \emptyset$.
We do a case analysis on $a^*$.
%Let $b$ be the element we last removed from $J_{\min}$ before the invariant became violated.
%Note that $a \in ball(b) = (b-w, b+w)$ since otherwise removing $b$ could not cause $a$ to violate the invariant.

%\todo{Would this be easier to read in bullet point format?}

\textit{Case 1:} $a^*$ is not blocked in $J_{\min}$\\
If $a^*$ is not blocked in $J_{\min}$ we could add it to the base and obtain an independent set which is in contradiction with $J_{\min}$ being a base (cf. Figure~\ref{fig:proof_intuition} (b)); same as in the initial case above). $\lightning$

\textit{Case 2:} $a^*$ is blocked in $J_{\min}$\\
Element $a^*$ can only be blocked in
 $J_{\min}$ if $J_{\min} \sqcap ball(a^*) \geq n$.
Since we assume the invariant does not hold for the new bases,
we have  $J_{\min}' \sqcap ball(a^*) = \emptyset$,
so we must have deleted at least $n$ elements from $J_{\min}$ in
previous iterations of \textsc{DeletionStep}.
However, we now show this results in a contradiction.

We know element $a^*$ has not been deleted yet.
All of the $n$ or more elements in $J_{\min} \sqcap ball(a^*)$ would have in ``in range'' to delete $a^* \in J_{\max}$. 
Therefore, we must have deleted at least $2n$ elements from $J_{\max}$ previously.
These elements must have been in $(a^*-2t_w, a^*+2t_w)$, the range covered by the $n$ or more elements in $J_{\min} \sqcap ball(a^*)$.

Note that we delete elements in $J_{\max}$ in ascending order.
Since $a^*$ was not deleted yet, all deleted elements must be smaller than or equal to $a^*$, i.e. at least $2n$ elements from $J_{\max}$ are actually all in $(a^*-2t_w, a^*]$.
Together with $a^*$ we have at least $2n+1$ elements in $J_{\max} \sqcap (a^*-2t_w, a^*]$, an interval of length smaller than $2t_w$.
This contradicts with $J_{\max}$ being an independent set or base since our layout constraint in
Eq.~\eqref{eq:LayoutConstraint} dictates that we cannot have more
than $2n$ elements in an interval of that length
(cf. Figure~\ref{fig:proof_intuition} (c)). $\lightning$ 


% Let us analyze the situation in $J_{\min}$ and $J_{\min}'$.
% \begin{itemize}
% \item We assume the invariant does not hold:  $J_{\min}' \sqcap ball(a) = \emptyset$.
% \item Element $a$ can only be blocked in $J_{\min}$ if $J_{\min} \sqcap ball(a) \geq n$.
% \item Since we now have $J_{\min}' \sqcap ball(a) = \emptyset$ we must have deleted at least $n$ elements from $J_{\min}$ in previous iterations of \textsc{DeletionStep}.
% \end{itemize}

% Let us now analyze the situation in $J_{\max}$.
% \begin{itemize}
% \item Element $a \in J_{\max}$ was not deleted yet.
% \item All of the $n$ or more elements in $J_{\min} \sqcap ball(a)$ would have in ``in range'' to delete $a \in J_{\max}$. 
% \item Therefore, we must have deleted at least $2n$ elements from $J_{\max}$ previously.
% These elements must have been in $(a-2w, a+2w)$, the range covered by the $n$ or more elements in $J_{\min} \sqcap ball(a)$.
% \item Note that we delete elements in $J_{\max}$ in ascending order.
% Since $a$ was not deleted yet all deleted elements must be smaller than or equal to $a$, i.e. at least $2n$ elements from $J_{\max}$ are actually all in $(a-2w, a]$.
% \item Together with $a$ we have at least $2n+1$ elements in $J_{\max} \sqcap (a-2w, a]$, an interval of length smaller than $2w$.
% This is a contradiction with $J_{\max}$ being an independent set or base (since our layout constraint in Equation~\eqref{eq:LayoutConstraint} dictates that we cannot have more than $2n$ elements in an interval of that length). $\lightning$
% \end{itemize}

Therefore, the invariant has to hold initially and after any number of iterations of \textsc{DeletionStep}.
\end{proof}

\begin{reptheorem}{theorem:layout_constraints_psystem}
% Layout Constraints $(E,\mathcal{I})$ form a $p$-system for $p$=2.
Let $(E,\mathcal{I})$ be an independence family based on our layout constraint where $T \in \mathcal{I}$ if $T$ satisfies Equation~\eqref{eq:LayoutConstraint} ($T \subseteq E$).
$(E,\mathcal{I})$ forms a $p$-system for $p=2$.
\end{reptheorem}
% \begin{theorem}[\ref{theorem:layout_constraints_psystem}]{}
% \label{theorem:layout_constraints_psystem2}
% Layout Constraints $(E,\mathcal{I})$ form a $p$-system for $p$=2.
% \end{theorem}
\vspace{-2mm}
\begin{proof}
From Equation~\ref{eq:p_systems_property},
we need to show that $J_{\max}| / |J_{\min}| \leq 2.$
% \begin{align*}
% \frac{|J_{\max}|}{|J_{\min}|} \leq 2.
% \end{align*}

From Lemma~\ref{Lemma:DeletionInvariance} we know that the invariant holds initially.
We now recursively apply \textsc{DeletionStep}.
In each step we delete one element from $J_{\min}$ and up to two elements from  $J_{\max}$.
In the end we have $J_{\min}^\text{end} = \emptyset$ and $|J_{\max}^\text{end}| \geq |J_{\max}| - 2 |J_{\min}|$.

From Lemma~\ref{Lemma:DeletionInvariance} we know that the invariant still holds after any number of iterations.
Therefore, $J_{\min}^\text{end} = \emptyset$ implies $J_{\max}^\text{end} = \emptyset$ and we get $|J_{\max}^\text{end}| = 0 \geq |J_{\max}| - 2 |J_{\min}|$.
Because all this holds for arbitrary minimal and maximal bases $J_{\min}$ and $J_{\max}$
this is equivalent to our proposition: $|J_{\max}| / |J_{\min}| \leq 2.$
\end{proof}

This shows that we can obtain a close-to-optimal solution to Equation~\eqref{eq:timeline_optimization} using an efficient greedy algorithm (see Section~\ref{subsec:approximation_guarantee}).



\subsection{Implementation Details of the Candidate Generation Step}

% Candidate for removal for space.
% \xhdr{Implementation details}
% \label{sec:CVT}
The KB used in this paper, Freebase, uses Compound Value Type (CVT) nodes 
as a way to represent n-ary relations in triple form.
(In the semantic web community, CVTs are known as ``blank nodes''.\footnote{
See \url{http://en.wikipedia.org/wiki/Blank_node}.})
Such CVTs reify the n-ary relation itself as a node;
each property of this CVT node corresponds to one of the slots in the n-ary relation.
For example, the event that Robert Downey Jr. starred in {\em The Avengers} while playing the role of {\em Iron Man} is represented by the following triples:
\begin{eqnarray*}
/m/Robert  & \xrightarrow{/film/actor/film} & \texttt{CVT} \\
\texttt{CVT}  & \xrightarrow{/film/performance/character} & /m/IronMan\\
\texttt{CVT}  & \xrightarrow{/film/performance/film} & /m/Avengers
\end{eqnarray*}
This representation makes the movie more than one hop away from the actor,
and therefore makes the process outlined above a bit more complex.
To address this, we ``collapse'' the CVT nodes by replacing each path 
$a \xrightarrow{p_1} \texttt{CVT} \xrightarrow{p_2} b$ 
by a single edge 
$a \xrightarrow{p_1.p_2} b$. 

The second issue  that CVTs raise can 
be illustrated through the following example.
When a musician plays for a band, this event is represented by a CVT,
which captures the role he played (\eg, singer or drummer),
the name of the band,
and the date he joined.
If two musicians play for the same band, their corresponding CVTs will have different IDs.
This will break the above compound event heuristic.
We solve this issue by replacing the CVT ID by the ID of the corresponding band.
More generally, we replace a CVT ID by following the predicate that leads to the most diverse 
set of entities in the knowledge base (\eg, we use the band ID not the less diverse role ID).
Formally, for each ``incoming'' predicate $p_1$ we choose the ``outgoing'' predicate $p_2^*$ such that
$$
p_2^*(p_1) = \argmin_{p_2} \max_{b} |\{ b \;|\; \exists a,\texttt{CVT} : e = a \xrightarrow{p_1} \texttt{CVT} \xrightarrow{p_2} b \}|.
$$



% Note that the second issue is different from the first one since here we are interested in the timestamp from the CVT (e.g. joined/left the band) whereas in the first case the relevant timestamp is connected to an entity connected to the CVT node (e.g. the movie release date).
% In practice, we found that the process described was both necessary and sufficient to cover all relevant events (that existed in the incomplete knowledge base).

future.tex
% !TEX root = timelines-paper.tex

%\subsection{Qualitative Analysis}
%\label{sec:qualitative}

%In addition to the above quantitative analysis of the model variants,
%we performed some qualitative analysis of the results
In this section, we suggest some directions for future work,
based in part
on the comments written by the raters.

{\bf Choosing a better default timespan.}
As we discussed in Section~\ref{subsec:zoom}, the algorithm
picks a default time span for a person that covers 90\% of their generated life events.
However, sometimes this is suboptimal.
For example, consider the US president John F Kennedy:
many important events occurred in the last few years of his life
(assassination, presidency, Cuban missile crisis, Bay of Pigs invasion, \etc). 
Our default timespan misses many of these.
In particular, his assassination, his presidency, and his marriage to
Jacqueline Kennedy Onassis are chosen first,
and these then block other important events such as Cuban Missile
Crisis or his involvement in the Vietnam war.

We address this problem by allowing the user to zoom in to the appropriate period.
Other potential solutions include 
using the E2D scores to weight some time periods higher than others, 
and including the search over suitable time periods as part of the
optimization.
% There are several possible solutions to this problem:
% using the E2D scores to weight some time periods higher than others;
% including the search over suitable time periods as part of the
% optimization problem;
% or just allowing the user to zoom in to the appropriate period
% (which we already support).

{\bf Time points vs intervals.}
Our algorithm represents events based on a single point in time.
However, some events (\eg, wars) are more naturally associated with
intervals. Currently our method may pick the start or end of a war,
but might not show both, due to the diminishing returns property.
This could be fixed by modifying the algorithm to reason about
temporal intervals.

{\bf Choosing how to describe an event.}
Sometimes a related entity is connected to the subject via many different
paths, and all have the same timestamp. In this case, it is hard to
know which relation to show to the user.
For example, the system sometimes describes a date
associated with someone's death as the end of their marriage; while
technically true, this is rather unintuitive.
Another example concerns US presidents: sometimes such people are
described as being a military commander.
Again, while technically true (since the US president is also
the Chief of the Armed Forces), this is unintuitive to users.
We may be able to fix this problem by learning a ranking model
applied to particular candidate values for any given subject and
relation
or by influencing the way the data is curated.


{\bf User preferences and subjectivity.}
In some cases, raters did not agree on which timeline was best.
%The agreement between raters was not as high as we expected.
The reason often seems to boil down to individual preferences.
In our experiments, the biggest area of disagreement is over how much
the timeline should be focused on
professional life (\eg, jobs, albums, books) vs personal life and
relationships (\eg, marriage, children).
Users had different opinions, even for the exact same timeline subjects, which illustrates the need for personalization in this space.
One approach would be to  distinguish between
professional and personal events, and to allow some trade-off parameter
between them.

{\bf Extractive vs abstractive summarization.}
Our current approach to building a timeline is similar to ``extractive
summarization'' techniques in the NLP community, in the sense that we
select a set of events from a candidate pool.
However, sometimes this is suboptimal, since the relationship between
two entities may be more complex.
For example, Robert Downey Jr.'s father (Robert Downey Sr.) shows up on his timeline,
but is described being a co-star in a movie rather than being his
father. While technically correct, it would be more satisfying to
create an abstract summarization of the relationship, describing that 
Robert Downey Sr. is both the father and a co-star.
We leave this to future work.
% \tim{RDSr is the director. Does that count as the co-star?}

\eat{
% kevin says: Best to not highlight this weakness
{\bf Using machine learning}. In the future, we might try to learn
the parameters of the model from data (\eg, pairwise judgments from human raters). 
(We did not do this in the  current paper due to lack of training data.)
Such machine learning approaches could also involve personalization, for instance to trade off professional career content versus personal life content individually for each user.
}

{\bf Creating timelines for collections}.
In the future, we would like to go
beyond timelines for single entities, and derive a
method to summarize collections of entities (\eg, 1930s jazz artists),
periods of time (1920s in the U.S.), or long-lasting events (World War II).

%It would also be useful to allow for temporal intervals, instead of just points in time,
%and to use abstractive summarization techniques instead of just extractive ones.
% This could include abstractive summarization techniques that concisely summarize entire subsets of events
% into natural language form.
% For example, such a system could generate a summary such as this:
% ``In his active career, Robert Downey Jr won four major awards including the Golden Globe Award for best actor in Sherlock Holmes (2010).''.

% Limitations of user interface: we could utilize space much better if we could have overlapping cards, or cards that aren’t centered on their respective timestamp etc

timelines-paper.tex
\pdfoutput=1
\documentclass{sig-alternate}
% something in the document class defines proof.
\let\proof\relax
\let\endproof\relax
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{color}
% \usepackage{caption}
% \usepackage{subcaption}
\usepackage{booktabs}
\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}
\usepackage[hyphens]{url}
\usepackage{verbatim} % allows multiline comments
%\usepackage{subfigure} % for the subfloat in the figs
\usepackage{multirow}
% \usepackage{algorithm}
% \usepackage[noend]{algorithmic}
\usepackage{xspace}
\usepackage{graphicx}
\usepackage{epsfig}
% \usepackage{amsmath}
% \usepackage{amssymb}
\usepackage{times}
\usepackage{dsfont}
\usepackage{paralist}
\usepackage{balance}

%for algorithms
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}

\newcommand\todo{\textcolor{red}}
% \newcommand\todo[1]{}
\newcommand{\tim}[1]{{\bf [Tim: #1]}}
\newcommand{\kevin}[1]{{\bf [Kevin: #1]}}
\newcommand{\luna}[1]{{\bf [Luna: #1]}}
\newcommand{\evgeniy}[1]{{\bf [Evgeniy: #1]}}
\newcommand{\safa}[1]{{\bf [Safa: #1]}}
\newcommand{\van}[1]{{\bf [Van: #1]}}
\newcommand{\wei}[1]{{\bf [Wei: #1]}}

% Remove for camera ready
% \pagenumbering{arabic}


% for tight everything, e.g around equations
\usepackage{etoolbox}
\newcommand{\zerodisplayskips}{%
  \setlength{\abovedisplayskip}{4pt} %try 2pt
  \setlength{\belowdisplayskip}{4pt}
  \setlength{\abovedisplayshortskip}{4pt}
  \setlength{\belowdisplayshortskip}{4pt}}
\appto{\normalsize}{\zerodisplayskips}
\appto{\small}{\zerodisplayskips}
\appto{\footnotesize}{\zerodisplayskips}

% tight figure/float/table captions
\setlength{\textfloatsep}{6pt}%{18pt plus 2pt minus 18pt}
\setlength{\floatsep}{6pt}%{11pt plus 2pt minus 12pt }
\setlength{\intextsep}{6pt}%11pt plus 2pt minus 2pt  
\setlength{\dbltextfloatsep}{6pt}%{18pt plus 2pt minus 18pt}
\setlength{\dblfloatsep}{6pt}%{11pt plus 2pt minus 12pt }

% for tight enumerate environment
\let\oldenumerate\enumerate
\renewcommand{\enumerate}{
  \vspace{-0.7\topsep} % removing space at top
  \oldenumerate
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
  \setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
}
\let\olditemize\itemize
\renewcommand{\itemize}{
  \vspace{-0.7\topsep}
  \olditemize
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
  \setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
}

% for fraction without dividing line
% from http://www.latex-community.org/forum/viewtopic.php?f=46&p=54967
\newcommand*{\bfrac}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}

% for argmin argmax
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\average}{mean}
%\DeclareMathOperator*{\average}{average}

%\newcommand{\relevance}{\textsc{Relevance}}
%\newcommand{\entityrelevance}{\textsc{EntityRelevance}}
%\newcommand{\daterelevance}{\textsc{DateRelevance}}

\newcommand{\relevance}{\textsc{Rel}}
\newcommand{\entityrelevance}{\textsc{ERel}}
\newcommand{\daterelevance}{\textsc{DRel}}


\newcommand{\temporalconstraints}{\textsc{Constraints}}
\newcommand{\EtoE}{\textsc{E2E}}
\newcommand{\EtoEPath}{\textsc{E2EPath}}
\newcommand{\EtoECooc}{\textsc{E2ECooc}}
\newcommand{\EtoD}{\textsc{E2D}}
\newcommand{\EtoDPath}{\textsc{E2DPath}}
\newcommand{\EtoDCooc}{\textsc{E2DCooc}}
\newcommand{\GtoE}{\textsc{G2E}}
\newcommand{\globalimportance}{\textsc{GlobalImportance}}

\newcommand{\sub}{s}
\newcommand{\pathtore}[1]{\mbox{$\pi_{re}(#1)$}}
\newcommand{\pathtots}[1]{\mbox{$\pi_{t}(#1)$}}

% Fun for function.
\newcommand{\reFun}{\textsc{RE}}
\newcommand{\subFun}{\textsc{Sub}}
\newcommand{\tFun}{\text{$\tau$}}


% Defining theorem environments.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
% from http://inst.eecs.berkeley.edu/~cs294-40/fa08/scribes/cs294-40.sty
\newenvironment{proof-idea}{\noindent{\it Proof Sketch.}\hspace*{0.1em}}{\qed\bigskip\\}

% for repeating a theorem
% http://www.faqoverflow.com/tex/422.html
\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
 \def\rep@title{#2 \ref{##1}}%
 \begin{rep@theorem}}%
 {\end{rep@theorem}}}
\makeatother
\newreptheorem{theorem}{Theorem}


% Def floor/ceil.
\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

% lightning bolt 
\usepackage{ stmaryrd }

% doublestroke chars, e.g. indicator function
\usepackage{dsfont}

% shrink space around headings
% \usepackage[compact]{titlesec}


\usepackage{booktabs} % for tables, bottom rule etc
%% from Cristian: http://snap.stanford.edu/svn/snap2/docs/papers/2013/cristian-politeness/cristian-politeness.tex
\newcommand{\totalrule}{\midrule}
\newcommand{\sectionrule}{\addlinespace[0.5ex]}

% don't allow footnotes spanning multiple pages (or columns)
\interfootnotelinepenalty=10000


\newcommand{\eat}[1]{}
\newcommand{\tightlist}{\itemsep=-2pt}
\newcommand{\rbox}{\hfill $\Box$}
\newcommand{\etc}{{\em etc.}}
\newcommand{\cf}{{\em cf.}}
\newcommand{\gap}{\mbox{Gap}}
\newcommand{\avg}{\mbox{Avg}}
\newcommand{\Sim}{\mbox{sim}}

\newcommand{\nedge}{k}
\newcommand{\bt}{\mathbf{t}}
\newcommand{\note}[1]{{{\textcolor{red}{#1}}}}
\newcommand{\hide}[1]{}
\newcommand{\xhdr}[1]{\vspace{1mm}\noindent{{\bf #1.}}}
\newcommand{\casc}{{\mathbf{t}}}
\newcommand{\alphs}{{\mathbf{A}}}
% \newtheorem{proposition}{Proposition}
% \newtheorem{theorem}{Theorem}
% \newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{lemma}{Lemma}
\newcommand{\xsketch}{\noindent {\it Proof Sketch.}}
\newcommand{\netinf}{{\textsc{Net\-Inf}}\xspace}
\newcommand{\multitree}{{\textsc{Multi\-Tree}}\xspace}
\newcommand{\netrate}{{\textsc{Net\-Rate}}\xspace}
\newcommand{\connie}{{\textsc{Co\-nNIe}}\xspace}
\newcommand{\maxinf}{{\textsc{Max\-Inf}}\xspace}
\newcommand{\expo}{{\textsc{Exp}}\xspace}
\newcommand{\pow}{{\textsc{Pow}}\xspace}
\newcommand{\ray}{{\textsc{Ray}}\xspace}
\newcommand{\eg}{\emph{e.g.}}
\newcommand{\ie}{\emph{i.e.}}
\newcommand{\unobs}{{\infty}}
\newcommand\T{\rule{0pt}{2.6ex}}
\newcommand\B{\rule[-1.2ex]{0pt}{0pt}}
%\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\denselist}{ \itemsep -2pt\topsep-10pt\partopsep-10pt }
\newcommand{\systemname}{{\sc TimeMachine}}

\graphicspath{{./FIG/}}


\newfont{\mycrnotice}{ptmr8t at 7pt}
\newfont{\myconfname}{ptmri8t at 7pt}
\let\crnotice\mycrnotice%
\let\confname\myconfname%
\permission{Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author(s). Copyright is held by the owner/author(s).}
\conferenceinfo{KDD'15,}{August 10-13, 2015, Sydney, NSW, Australia.} 
\copyrightetc{ACM \the\acmcopyr}
\crdata{978-1-4503-3664-2/15/08. \\
DOI: http://dx.doi.org/10.1145/2783258.2783325 }
\clubpenalty=10000 
\widowpenalty = 10000

\hyphenation{time-stamp}
\hyphenation{time-stamps}
\hyphenation{Time-Machine}

\begin{document}

%\title{It's about Time:\\ Timeline Generation for Knowledge-Base  Entities}
\title{TimeMachine:\\ Timeline Generation for Knowledge-Base Entities}

%\numberofauthors{6}
\author{
\alignauthor
Tim Althoff*,
Xin Luna Dong\textsuperscript{\textdagger},
Kevin Murphy\textsuperscript{\textdagger},
Safa Alai\textsuperscript{\textdagger},
Van Dang\textsuperscript{\textdagger},
Wei Zhang\textsuperscript{\textdagger}\\
% Evgeniy Gabrilovich\textsuperscript{\textdagger}\\
\vspace{2mm}
\affaddr{*Computer Science Department, Stanford University, Stanford, CA 94305}\\
\affaddr{\textsuperscript{\textdagger}Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043}\\
\vspace{1mm}
\email{*althoff@cs.stanford.edu \hspace{1mm} \textsuperscript{\textdagger}\{lunadong, kpmurphy, safa, vandang, weizh\}@google.com} %, gabr
}

%\numberofauthors{6} %  in this sample file, there are a *total*

% author order? tim luna kevin van safa wei evgeniy?
%\% author{
% \alignauthor
% Tim Althoff\\
%       \affaddr{Stanford University}\\
%       \email{althoff@cs.stanford.edu}
% \alignauthor
% Author 2 \\
%       \affaddr{Google}\\
%       \email{author2@google.com}
% \alignauthor
% Author 3 \\
%       \affaddr{Google}\\
%       \email{author3@google.com}
% \and
% Author 4 \\
%       \affaddr{Google}\\
%       \email{author4@google.com}
% \alignauthor
% Author 5 \\
%       \affaddr{Google}\\
%       \email{author5@google.com}
% \alignauthor
% Author 6 \\
%       \affaddr{Google}\\
%       \email{author6@google.com}
% }

\maketitle

\begin{abstract}
\input{000abstract}
\end{abstract}

%\vspace{1mm}
%\category{H.2.8}{Database Management}{Database Applications}[data mining]

%\keywords{Information diffusion, cascade prediction, contagion}

\vspace{1mm}
\noindent {\bf Categories and Subject Descriptors:} H.2.8 {\bf
[Database Management]}: Database applications---{\it Data mining}

\noindent {\bf General Terms:} Algorithms, Experimentation. 
 % Algorithms, Experimentation,
 %  Human Factors, Languages, Legal Aspects, Management, Measurement, Performance, Reliability, Security, Standardization, Theory, Verification

\noindent {\bf Keywords:} Summarization, Timeline, Knowledge Base, Submodular Optimization.

\vspace{-0.5\baselineskip}
\section{Introduction}
\label{sec:introduction}
\input{010introduction}

%\section{Problem Definition}
%\label{sec:problem}
%\input{015problem}

% \vspace{-0.5\baselineskip}
\section{Event Candidate Generation}
\label{sec:generation}
\input{020generation}

\vspace{-0.75\baselineskip}
\section{Event Selection}
\label{sec:selection}
\input{030selection}

\vspace{-0.5\baselineskip}
\section{Evaluation}
\label{sec:evaluation}
\input{040evaluation}

\vspace{-0.5\baselineskip}
\section{Related Work}
\label{sec:relatedwork}
\input{050relatedwork}

\vspace{-0.5\baselineskip}
\section{Future work}
\label{sec:future}
\input{future}

\vspace{-1.0\baselineskip}
\section{Conclusions}
\label{sec:conclusion}
\input{060conclusion}


% \section{Acknowledgments}
\xhdr{Acknowledgments}
We thank Evgeniy Gabrilovich for many helpful discussions, 
Arun Chaganty, Stefanie Jegelka, Karthik Raman, Sujith Ravi, and Ravi Kumar for their insights on submodular optimization,
Jeff Tamer and Patri Friedman for their support with the user studies,
Danila Sinopalnikov and Alexander Lyashuk for their help with the co-occurrence pipeline,
and Jure Leskovec, David Hallac, Caroline Suen, and the anonymous reviewers for their valuable feedback.



% this gets us to less than 10p if we remove appendix.
% \small
% \enlargethispage{1\baselineskip}
% \balance
%\newpage
% \vspace{-20mm} % important when using small font

\vspace{-1.5\baselineskip}
{\small
\bibliographystyle{abbrv}
\vspace{1mm} % important when using small font
\bibliography{refs}
\enlargethispage{1\baselineskip} % important layout hack
}

% \eat{
\newpage
\normalsize
\section{Appendix}
\label{sec:appendix}
\input{070appendix}
% }

% \newpage
% \balance
% \bibliographystyle{abbrv}
% \bibliography{refs}

%\newpage
% \clearpage
% \pagebreak
% \appendix

\end{document}

timelines-paper.bbl
\begin{thebibliography}{10}

\bibitem{ahmed2012fair}
A.~Ahmed, C.~H. Teo, S.~Vishwanathan, and A.~Smola.
\newblock Fair and balanced: Learning to present news stories.
\newblock In {\em WSDM}, 2012.

\bibitem{allan2001temporal}
J.~Allan, R.~Gupta, and V.~Khandelwal.
\newblock Temporal summaries of new topics.
\newblock In {\em SIGIR}, 2001.

\bibitem{althoff2015fullpaperarxiv}
T.~Althoff, X.~L. Dong, K.~Murphy, S.~Alai, V.~Dang, and W.~Zhang.
\newblock {TimeMachine: Timeline Generation for Knowledge-Base Entities}.
\newblock {\em arXiv:1502.04662}, 2015.

\bibitem{modern-ir}
R.~A. Baeza-Yates and B.~Ribeiro-Neto.
\newblock {\em Modern Information Retrieval}.
\newblock ACM Press, New York, 1999.

\bibitem{bamman2014unsupervised}
D.~Bamman and N.~Smith.
\newblock Unsupervised discovery of biographical structure from text.
\newblock {\em TACL}, 2(10):363--376, 2014.

\bibitem{Bollacker08}
K.~Bollacker, C.~Evans, P.~Paritosh, T.~Sturge, and J.~Taylor.
\newblock Freebase: a collaboratively created graph database for structuring
  human knowledge.
\newblock In {\em SIGMOD}, 2008.

\bibitem{calinescu2011maximizing}
G.~Calinescu, C.~Chekuri, M.~P{\'a}l, and J.~Vondr{\'a}k.
\newblock Maximizing a monotone submodular function subject to a matroid
  constraint.
\newblock {\em SIAM Journal on Computing}, 40(6):1740--1766, 2011.

\bibitem{carbonell1998use}
J.~Carbonell and J.~Goldstein.
\newblock {The use of MMR, diversity-based reranking for reordering documents
  and producing summaries}.
\newblock In {\em SIGIR}, 1998.

\bibitem{carterette2008here}
B.~Carterette, P.~N. Bennett, D.~M. Chickering, and S.~T. Dumais.
\newblock {Here or there: Preference Judgments for Relevance}.
\newblock In {\em Advances in Information Retrieval}. Springer, 2008.

\bibitem{dasgupta2013summarization}
A.~Dasgupta, R.~Kumar, and S.~Ravi.
\newblock Summarization through submodularity and dispersion.
\newblock In {\em ACL}, 2013.

\bibitem{do2012joint}
Q.~X. Do, W.~Lu, and D.~Roth.
\newblock Joint inference for event timeline construction.
\newblock In {\em EMNLP-CoNLL}, 2012.

\bibitem{Dong14}
X.~Dong, E.~Gabrilovich, G.~Heitz, W.~Horn, N.~Lao, K.~Murphy, T.~Strohmann,
  S.~Sun, and W.~Zhang.
\newblock Knowledge vault: A web-scale approach to probabilistic knowledge
  fusion.
\newblock In {\em SIGKDD}, 2014.

\bibitem{dubinko2007visualizing}
M.~Dubinko, R.~Kumar, J.~Magnani, J.~Novak, P.~Raghavan, and A.~Tomkins.
\newblock Visualizing tags over time.
\newblock {\em TWEB}, 1(2):7, 2007.

\bibitem{feige1998threshold}
U.~Feige.
\newblock A threshold of ln n for approximating set cover.
\newblock {\em Journal of the ACM (JACM)}, 45(4):634--652, 1998.

\bibitem{graus2013yourhistory}
D.~Graus, M.-H. Peetz, D.~Odijk, O.~de~Rooij, and M.~de~Rijke.
\newblock {yourHistory--Semantic linking for a personalized timeline of
  historic events}.
\newblock {\em Workshop: LinkedUp Challenge at OKCon}, 2013.

\bibitem{huet2013mining}
T.~Huet, J.~Biega, and F.~M. Suchanek.
\newblock Mining history with le monde.
\newblock In {\em AKBC}, 2013.

\bibitem{ji2013tackling}
H.~Ji, T.~Cassidy, Q.~Li, and S.~Tamang.
\newblock Tackling representation, annotation and classification challenges for
  temporal knowledge base population.
\newblock {\em KAIS}, 2013.

\bibitem{kannan2014mining}
A.~Kannan, S.~Baker, K.~Ramnath, J.~Fiss, D.~Lin, L.~Vanderwende, R.~Ansary,
  A.~Kapoor, Q.~Ke, M.~Uyttendaele, et~al.
\newblock Mining text snippets for images on the web.
\newblock In {\em SIGKDD}, 2014.

\bibitem{Katz87estimationof}
S.~M. Katz.
\newblock Estimation of probabilities from sparse data for the language model
  component of a speech recognizer.
\newblock In {\em IEEE Trans Sig. Process.}, 1987.

\bibitem{krause2012submodular}
A.~Krause and D.~Golovin.
\newblock Submodular function maximization.
\newblock In {\em Tractability: Practical Approaches to Hard Problems (to
  appear)}. Cambridge University Press, 2014.

\bibitem{leskovec2007cost}
J.~Leskovec, A.~Krause, C.~Guestrin, C.~Faloutsos, J.~VanBriesen, and
  N.~Glance.
\newblock Cost-effective outbreak detection in networks.
\newblock In {\em SIGKDD}, 2007.

\bibitem{li2014timeline}
J.~Li and C.~Cardie.
\newblock Timeline generation: tracking individuals on twitter.
\newblock In {\em WWW}, 2014.

\bibitem{lin2004rouge}
C.-Y. Lin.
\newblock Rouge: A package for automatic evaluation of summaries.
\newblock In {\em Proc. ACL Text Summarization Workshop}, 2004.

\bibitem{lin2012learning}
H.~Lin and J.~A. Bilmes.
\newblock Learning mixtures of submodular shells with application to document
  summarization.
\newblock In {\em UAI}, 2012.

\bibitem{ling2010temporal}
X.~Ling and D.~S. Weld.
\newblock Temporal information extraction.
\newblock In {\em AAAI Conference on Artificial Intelligence}, 2010.

\bibitem{mazeika2011entity}
A.~Mazeika, T.~Tylenda, and G.~Weikum.
\newblock Entity timelines: Visual analytics and named entity evolution.
\newblock In {\em CIKM}, 2011.

\bibitem{minoux1978accelerated}
M.~Minoux.
\newblock Accelerated greedy algorithms for maximizing submodular set
  functions.
\newblock In {\em Optimization Techniques}, pages 234--243. Springer, 1978.

\bibitem{nemhauser1978analysis}
G.~L. Nemhauser, L.~A. Wolsey, and M.~L. Fisher.
\newblock {An analysis of approximations for maximizing submodular set
  functions — I}.
\newblock {\em Mathematical Programming}, 14(1):265--294, 1978.

\bibitem{BingTimeline}
R.~Qian.
\newblock {Timeline: Understanding Important Events in People’s Lives}.
\newblock {\small
  \url{http://blogs.bing.com/search/2014/02/21/timeline-understanding-important-events-in-peoples-lives/}},
  February 2014.
\newblock Last retrieved on Feb 18, 2015.

\bibitem{shahaf2012metro}
D.~Shahaf, C.~Guestrin, and E.~Horvitz.
\newblock Metro maps of science.
\newblock In {\em SIGKDD}, 2012.

\bibitem{shahaf2013information}
D.~Shahaf, J.~Yang, C.~Suen, J.~Jacobs, H.~Wang, and J.~Leskovec.
\newblock Information cartography: creating zoomable, large-scale maps of
  information.
\newblock In {\em SIGKDD}, 2013.

\bibitem{Shen2015}
W.~Shen, J.~Wang, and J.~Han.
\newblock Entity linking with a knowledge base: Issues, techniques, and
  solutions.
\newblock {\em TKDE}, 2015.

\bibitem{sipos2012temporal}
R.~Sipos, A.~Swaminathan, P.~Shivaswamy, and T.~Joachims.
\newblock Temporal corpus summarization using submodular word coverage.
\newblock In {\em CIKM}, 2012.

\bibitem{sparck2007automatic}
K.~Sp{\"a}rck~Jones.
\newblock Automatic summarising: The state of the art.
\newblock {\em Information Processing \& Management}, 43(6):1449--1481, 2007.

\bibitem{suchanek2007yago}
F.~M. Suchanek, G.~Kasneci, and G.~Weikum.
\newblock Yago: a core of semantic knowledge.
\newblock In {\em WWW}, 2007.

\bibitem{suchanek2014semantic}
F.~M. Suchanek and N.~Preda.
\newblock {Semantic Culturomics (Vision paper)}.
\newblock In {\em Very Large Databases (VLDB)}, 2014.

\bibitem{swan2000automatic}
R.~Swan and J.~Allan.
\newblock Automatic generation of overview timelines.
\newblock In {\em SIGIR}, 2000.

\bibitem{tran2014wikipevent}
T.~Tran, A.~Ceroni, M.~Georgescu, K.~D. Naini, and M.~Fisichella.
\newblock Wikipevent: Leveraging wikipedia edit history for event detection.
\newblock In {\em WISE}. Springer, 2014.

\bibitem{tuan2011cate}
T.~A. Tuan, S.~Elbassuoni, N.~Preda, and G.~Weikum.
\newblock {CATE: Context-Aware Timeline for Entity Illustration}.
\newblock In {\em WWW}, 2011.

\bibitem{wang2010timely}
Y.~Wang, M.~Zhu, L.~Qu, M.~Spaniol, and G.~Weikum.
\newblock {Timely Yago: harvesting, querying, and visualizing temporal
  knowledge from Wikipedia}.
\newblock In {\em EDBT}, 2010.

\bibitem{weikum2011longitudinal}
G.~Weikum, N.~Ntarmos, M.~Spaniol, P.~Triantafillou, A.~A. Bencz{\'u}r,
  S.~Kirkpatrick, P.~Rigaux, and M.~Williamson.
\newblock {Longitudinal Analytics on Web Archive Data: It's About Time!}
\newblock In {\em CIDR}, 2011.

\bibitem{zhao2013timeline}
X.~W. Zhao, Y.~Guo, R.~Yan, Y.~He, and X.~Li.
\newblock Timeline generation with social attention.
\newblock In {\em SIGIR}, 2013.

\end{thebibliography}
