%\documentclass{llncs}
\documentclass[11pt,onecolumn,oneside]{article}
\usepackage{llncsdoc}
\usepackage{amsfonts,stmaryrd}
\usepackage{wasysym}
\usepackage{dsfont}
\usepackage{float}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{fancyvrb}
\usepackage{wrapfig}
\usepackage{soul} %Strike through text package
\usepackage[export]{adjustbox} %figure left align
\usepackage{graphicx,subfigure}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{condition}[thm]{Condition}
\newtheorem{proof}[thm]{Proof}

%\setlength{\intextsep}{10pt plus 2pt minus 2pt}
\setlength{\evensidemargin}{0.05in}
\setlength{\oddsidemargin}{0.05in}
\setlength{\marginparwidth}{0.6in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.3in}
\addtolength{\parskip}{0.0 cm}

\setlength{\topmargin}{0.25in}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tables} \label{app:tables}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table}[ht]
%\scriptsize
%\small
\centering
\caption{Tokens' Resources and Costs}
\begin{tabular}{| c | c | c | c | c |}
\hline
\multirow{2}{*}{pattern type} & \multirow{2}{*}{scheme(\#edges)} & \multirow{2}{*}{measure} & max & max \& min\\
& & & constraints & constraints\\
\hline
& & \#comparisons & $O(n^2)$ & $O(n^2)$\\ 
continuous & history($O(n^2)$) & space & $O(n)$ & $O(n)$\\
& & \#graph tokens & $O(n)$ & $O(n)$\\
\hline
& & \#comparisons & $O(n)$ & $O(n)$\\ 
continuous & deadline($O(1)$) & space & $O(1)$ & $O(1)$\\
& & \#graph tokens & $O(n)$ & $O(n)$\\
\hline
& & \#comparisons & $O(n^2)$ & $O(n^2)$\\ 
sporadic & history($O(n^2)$) & space & $O(n)$ & $O(n)$\\
& & \#graph tokens & $O(n)$ & $O(k^n)$\\
\hline
& & \#comparisons & $O(n)$ & $O(n)$\\ 
sporadic & deadline($O(1)$) & space & $O(1)$ & $O(1)$\\
& & \#graph tokens & $O(n)$ & $O(k^n)$\\
\hline
\multirow{2}{*}{sporadic} & any scheme using & space used by $q$ & \multirow{2}{*}{$O(q(l+n))$} & \multirow{2}{*}{$O(q(l+n))$}\\
& a history tree & history trees and $l$ tokens & &\\
\hline
\end{tabular}
\label{table:cmplxtyptable}
\end{table}

\noindent$n$ is the number of pattern events, and $k = max\{ \overline{tw} - \underline{tw} \mid tw \in TW(TP) \wedge tw$ is a simple time window$\}$.
The measures are the number of comparisons per token, the space occupied by a token's data structures, and the maximum number of tokens on the graph at any point in time.
We analyze the history scheme for many (up to $O(n^2)$) graph edges, and the deadline scheme for few ($O(1)$) graph edges.
We distinguish between detection of continuous and sporadic patterns.

%\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Figures} \label{app:figures}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{figure}[ht!]
%  \centering
%      \includegraphics [width=15cm] {Fig11.pdf}
%      \caption[A temporal pattern graph]{A temporal pattern graph $G(TP)$}
%  \label{fig:partialhistory1}
%\end{figure}
%
%\begin{figure}[ht!]
%  \centering
%      \includegraphics [width=15cm] {Fig12.pdf}
%      \caption[A history-restricted pattern graph]{The graph $G(TP|_H)$ of $TP$'s restriction to the history $H=((a,0),(b,7),(c,18))$}
%  \label{fig:partialhistory2}
%\end{figure}

%\begin{figure}[htbp]
%  \centering
%      \includegraphics [width=15cm] {Fig13.pdf}
%      \caption[An illustration of the shortest paths induced by a history]{An illustration of the shortest paths induced by $H$. 1. illustrates the shortest $(a_r,a_{r+1})$-$path$ and 2. illustrates the shortest $(a_{r+1},a_r)$-$path$.}
%  \label{fig:linearrecompute}
%\end{figure}

\end{document} 
