\section{Introduction}
\label{sec-introduction}

The field of succinct data structures ({\sc{SDSs}}) has evolved rapidly in
the last decade.
New data structures such as the FM-Index, Wavelet Tree (\structname{WT}), Range
Minimum Query Structure (\structname{RMQ}), Compressed Suffix Array (\structname{CSA}), and
Compressed Suffix Tree (\structname{CST}) have been developed, and been shown to
be remarkably versatile.
These structures provide the same functionality as the corresponding
uncompressed data structures, but do so using space which is
asymptotically close to the information-theoretic lower bound needed
to store the underlying data or objects.
Using standard models of computation, the asymptotic runtime
complexity of the operations performed by {{\sc{SDSs}}} is also often
identical to their classical counterparts.
However, in practice, {{\sc{SDSs}}} tend to be slower than the uncompressed
structures, due to more complex memory access patterns on bitvectors,
including non-sequential processing of unaligned bits.
That is, they come in to their own only when the data scale means
that an uncompressed structure would not fit in to main memory (or
any particular level of the memory hierarchy), but a compressed
structure would.

Accessing (\method{access}), counting (\method{rank}), and selecting (\method{select})
bits in bitvectors ({\structname{BV}}s) are the fundamental operations from which
more intricate operations are constructed.
All three foundational operations can be supported in constant time
adding only sublinear space.
Wavelet trees build on {\structname{BV}}s and generalize the three operations to
alphabets of size $\sigma>2$, with a corresponding increase in time
to $\Order{\log\sigma}$.
A further layer up, some {\structname{CSA}}s use {\structname{WT}}s to realize their
functionality; in turn, {\structname{CSA}}s are the basis of yet more complex
structures such as {\structname{CST}}s.
Multiple alternatives exist at each level of this dependency
hierarchy.
For example, {\structname{WT}}s differ in both shape (uniform versus
Huffman-shaped) and in the choice made in the lower hierarchy levels
(whether compressed or uncompressed {\structname{BV}}s are used).
The diversity of options allows structures to be composed that have a
variety of time-space trade-offs.
In practice, many of the complex structures that have been proposed
are not yet fully implemented, since the implementations of
underlying structures are missing.
The use of non-optimized or non-composable substructures then
prevents thorough empirical investigations, and makes it difficult to
carry out impartial comparisons between complex structures.
The cost of implementing different approaches also creates a barrier
that makes it difficult for new researchers, including graduate
students, to enter the field.

As part of our investigation into {{\sc{SDSs}}}, a library of flexible and
efficient implementations has been assembled, providing a modular
``plug and play, what you declare is
what you get''
approach to
algorithm implementation.
Instrumentation and visualization tools are also included in the
library, allowing space costs to be accurately measured and depicted;
as are efficient routines for constructing (in-memory as well as
semi-external) and serializing all internal representations, allowing
files containing succinct structures to be generated and re-read.
We have also incorporated recent hardware developments, so that
built-in popcount operations are used when available, and hardware
hugepages can be enabled, to bypass address translation costs.

With this resource it is straightforward to {\emph{compose}} complex
structures; {\emph{measure}} their behavior; and {\emph{explore}} the
range of alternatives.
Having an established and robust code base also means that
experimental comparisons of new data structures and algorithms can be
made more resilient, providing greater consistency between
alternative structures, and allowing better baseline systems and
hence more reproducible evaluations.
For example, different {\structname{CST}} components might be appropriate to
different types of input sequence (integer alphabet versus
byte-based; highly-repetitive or not; and sampling rates for access
methods); with the library the right combination of components for
any given application can be readily determined.
The generality embedded in the library means that it is also useful
in other fields such as information retrieval
and bioinformatics.

We illustrate the myriad virtues of the library -- version~2 of
{{\sc{sdsl}}} -- through two case studies: first, a detailed recomposition
and re-evaluation of succinct document retrieval systems
(Section~\ref{sec-recomp}); and second, a detailed examination of the
construction processes used to create indexing structures
(Section~\ref{sec-constr}).

\section{Document Retrieval Recomposed}
\label{sec-recomp}

The {\emph{top-$k$ document retrieval problem}} is fundamental in
information retrieval (IR), and has become an active research topic
in the succinct data structures community, see {\citet{n14compsurv}}
for an excellent overview.
For a collection of $N$ documents $\ensuremath{\mathcal{C}}\!=\!\{d_1,\ldots,d_N\}$ over
an alphabet $\ensuremath{\Sigma}$ of size $\ensuremath{\sigma}$, a query {\ensuremath{\mathcal{Q}}} also a set
of strings over $\ensuremath{\Sigma}$, and a ranking function
$R:\ensuremath{\mathcal{C}}\!\times\!\ensuremath{\mathcal{Q}}\!\rightarrow\!\mathcal{R}$, the task is to
return the $k$ documents with highest values of $R(d_i,\ensuremath{\mathcal{Q}})$.
The simple {\emph{frequency}} version of the problem assumes that the
query consists of a single sequence (term) $q$ and that $R(d_i,q)$ is
the frequency $\tf(d_i,q)$ of $q$ in $d_i$.
The {\emph{tf-idf}} version of the problem computes
$R(d_i,\ensuremath{\mathcal{Q}})=\tf(d_i,q)\times\log({N}/{\df(q)})$, where $\df(q)$ is
the {\emph{document frequency}} of $q$, the number of documents in
which sequence $q$ occurs.
The {\emph{tf-idf}} formulation used here and in similar studies (for
example, {\citet{sad07tcs}}) is still a simplification of the
measures used in modern retrieval systems, which incorporate factors
like document length, static document components such as pagerank,
and queries with multiple terms.

We focus here on the single term {\emph{frequency}} and single term
{\emph{tf-idf}} versions of the problem.
{\citet{sad07tcs}} devised the first succinct structure for these
problems, an approach we refer to as {\algname{SADA}}.
An alternative mechanism, {\algname{GREEDY}}, was presented by
{\citet{CUL:NAV:PUG:TUR:2010}}.
{\citeauthor{CUL:NAV:PUG:TUR:2010}}~also describe implementations of
{\algname{SADA}} and {\algname{GREEDY}}, based on components that were available in
2009.
We first briefly explain {\algname{SADA}} and {\algname{GREEDY}}, and then recompose
and reimplement them using the library,
to study the impact of state-of-the-art components.
For both solution we use the conventions established by
{\citeauthor{sad07tcs}} and {\citeauthor{CUL:NAV:PUG:TUR:2010}}: the
set of documents is concatenated to form a text {\ensuremath{\mathcal{T}}} by appending
a sentinel symbol $\#$ to each $d_i$; then joining them all in to
one; then appending a further sentinel symbol $\$$ following $d_N$.
Both sentinels are lexicographical smaller than any symbol in
$\ensuremath{\Sigma}$, and $\$<\#$.
We use $n$ to represent $|{\ensuremath{\mathcal{T}}}|$.

\subsection{SADA and GREEDY revisited}

The {\algname{SADA}} structure is composed of several components.
First, a {\structname{CSA}} (denoted {\identifier{csa\_full}}) over {\ensuremath{\mathcal{T}}} identifies, for any
pattern $p$, the range $[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$ of matching suffixes in
{\ensuremath{\mathcal{T}}}, providing the functionality of a {\structname{SA}}.
Second, a {\structname{BV}} is constructed (denoted $\identifier{border}[0..(n-1)]$) with
$\identifier{border}[i]\!=\!1$ iff $\ensuremath{\mathcal{T}}[i]\!=\!\#$; supporting rank and select
structures ($\identifier{border\_rank}$ and $\identifier{border\_select}$) are also generated.
A {\emph{document array}} $\ensuremath{\mathcal{D}}[0..(n\!-\!1)]$ that maps the $i$\,th
suffix in $\ensuremath{\mathcal{T}}$ to the document that contains it can then be
emulated using {\identifier{border}} and {\identifier{csa\_full}}, since
$\ensuremath{\mathcal{D}}[i]\!=\!\identifier{border\_rank}(\ensuremath{\mathcal{SA}}[i])$.
Third, to generate all distinct document numbers in a range
$[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$, an {\structname{RMQ}} structure $\identifier{rminq}$ is used.
It is built over a conceptual array $C[0..(\!n-\!1)]$, defined as
$C[i]\!=\!\max\{j\!\mid\!j\!<\!i\!\wedge\!D[j]\!=\!D[i]\}$; that is, $C[i]$ is the
index in $\ensuremath{\mathcal{D}}$ of the last prior occurrence of $\ensuremath{\mathcal{D}}[i]$.
The number of distinct values in $\ensuremath{\mathcal{D}}[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$ corresponds to
$\df(q)$.
Locations of the values are identified by computing $x=\identifier{rminq}(\mbox{\emph{sp}},\mbox{\emph{ep}})$, the
index of the minimum element in $C[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$.
A temporary {\structname{BV}} of size $N$ is used to check if $\ensuremath{\mathcal{D}}[x]$ was
already retrieved; if it wasn't, the counting is continued by
recursing into $[\mbox{\emph{sp}}..(x\!-\!1)]$ and $[(x\!+\!1)..\mbox{\emph{ep}}]$.
Finally, a second {\structname{RMQ}} structure and individual {\structname{CSA}}s are built
for each document $d_i$, in order to calculate $\tf(d_i,q)$.
The top-$k$ items are then calculated by a partial sort on the
$\tf(d_i,q)$ values.
In total, {\algname{SADA}} uses
$
	|\structname{CSA}(\ensuremath{\mathcal{T}})|\!+\!|\structname{BV}(\ensuremath{\mathcal{T}})|\!+\!2|\structname{RMQ}|\!+\!%
		\sum_{i=0}^{N-1}|\structname{CSA}(d_i)|
$
bits.
Choosing an $H_k$-compressed {\structname{CSA}} for $\identifier{csa\_full}$, a
$2n\!+\!o(n)$-bit solution for $\identifier{rminq}$, and a compressed {\structname{BV}} for
$\identifier{border}$~{\cite{OKA:SAD:2007}}, results in a total bit count bounded
above by
$
	n H_k(\ensuremath{\mathcal{T}})\!+\!\sum_{i=0}^{N-1}|\structname{CSA}(d_i)|%
		+\!4n\!+\!o(n)\!+N(2\!+\!\log (n/N)).
$
The space for the document {\structname{CSA}}s was deliberately not substituted
by the cost of a concrete solution, for two reasons: (1) each {\structname{CSA}}
has an alphabet dependent overhead, which dominates the space for
small documents; and (2) only the inverse {\structname{SA}} functionality is
used.
Thus, in the recomposition, we opt for a {\emph{bit-compressed}}%
\footnote{%
That is, each item is encoded as a binary value in $\lceil\log|d_i|\rceil$ bits.
}
version of
the inverse {\structname{SA}}, with almost no overhead per document, and
benefiting from constant access time.

The second solution -- {\algname{GREEDY}} -- also uses {\identifier{csa\_full}} to translate
patterns $p$ to ranges $[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$.
In this solution the document array $\ensuremath{\mathcal{D}}$ is explicitly represented
by a {\structname{WT}}, denoted {\identifier{wtd}}.
The total size is then
$
	|\structname{CSA}(\ensuremath{\mathcal{T}})|+|\structname{WT}(\ensuremath{\mathcal{D}})|=nH_k(\ensuremath{\mathcal{T}})+nH_0(\ensuremath{\mathcal{D}}),
$
using compressed {\structname{BV}}s for
{\identifier{wtd}}~\cite{RAM:RAM:RAO:2002}.
{\citeauthor{CUL:NAV:PUG:TUR:2010}}~use these structures to solve the
frequency variant of the top-$k$ problem.
In the first step the pattern is translated to a range in $\ensuremath{\mathcal{D}}$.
A priority queue is then used to store pending nodes in the expansion
in $\structname{WT}$ of the range $[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$.
At each step the largest node is extracted, and, if it is not a leaf
node, its two children inserted.
This process is iterated until $k$ leaves -- corresponding to the
top-$k$ frequent documents -- have emerged.
The range size of a leaf corresponds to the term frequency $\tf(d_i,q)$.
In contrast to {\algname{SADA}}, not all documents have to be listed in order
to calculate the top-$k$.
However, {\algname{GREEDY}} does more work per document, since {\identifier{wtd}} has a
height of $\log N$.

\subsection{Experimental setup}

We adopt the experimental setup employed by
{\citet{CUL:NAV:PUG:TUR:2010}}, reusing the
{{\sc proteins}} file and adding the {{\sc enwiki}}
file.\footnote{We did not use the Wall
Street Journal file, since licensing issues meant that we could not
make it available for download. Our full setup is
available at \href{http://go.unimelb.edu.au/w68n}{http://go.unimelb.edu.au/w68n}.
 }
The {{\sc enwiki}} datafiles come in four versions:
parsed as either characters or words; and either a small prefix, or
the whole collection, see Table~\ref{tbl-collections}.
The character version was generated by removing markup from a
wikipedia dump file; the word-based version by then applying
the parser of the Stanford Natural Language Group.

We generated patterns of different lengths, again following the lead
of {\citet{CUL:NAV:PUG:TUR:2010}}, with $200$ patterns of each
length; reported query times are averages over sets of $200$
patterns.
All experiments were run on a server equipped with {\gb{144}} of RAM
and two Intel Xeon E5640 processors each with a {\mb{12}} L3 cache.
The experimental code is available within the benchmark suite of the library,
and all used library classes
(printed in fixed italic font) are linked to their
definitions.

\begin{table}
\centering
{\small
\begin{tabular}{@{}l@{}l@{}r*{5}{@{}l@{\hspace{1.8ex}}r}@{}}
\toprule
Collection && $n$ && $N$ && $\Sigma_{i=0}^{N-1}\frac{|d_i|}{N}$&&$\ensuremath{\sigma}$&& $|\ensuremath{\mathcal{T}}|$ in MB && $\approx H_k(\ensuremath{\mathcal{T}})$\\[0ex]
\cmidrule{3-3}
\cmidrule{5-5}
\cmidrule{7-7}
\cmidrule{9-9}
\cmidrule{11-11}
\cmidrule{13-13}
\multicolumn{2}{r}{\textit{character alphabet}} \\
{\sc  proteins }&& 58,959,815 && 143,244          && 412    && 40&&    56 && 0.90 \\
{\sc  enwiki-sml }&& 68,210,334 && 4,390          && 15,538 &&206&&    65 && 2.01 \\
{\sc  enwiki-big }&& 8,945,231,276 && 3,903,703   && 2,291  &&211&& 8,535 && 2.02 \\

\multicolumn{2}{r}{\textit{word alphabet}} \\
{\sc  enwiki-sml}&& 12,741,343    && 4,390     && 2,902 &&   281,577&& 29 && 5.03 \\
{\sc  enwiki-big}&& 1,690,724,944 && 3,903,703 &&  433 &&  8,289,354&& 4,646 && 4.45 \\
\bottomrule
\end{tabular}
}
\caption{Collection statistics: number of characters/words, number of
documents, average document length, total collection size, and
approximate $H_k$ (determined using {\tt xz --best}) in bits per
character/word. The character based collections use one byte
per symbol, while $\lceil\log\ensuremath{\sigma}\rceil$ bits
are used the word based case.
\label{tbl-collections}}
\end{table}

\subsection{Plug and play}

We start by composing an instance of {\algname{GREEDY}}.
For {\tt{csa\_full}}, {{\sc{sdsl}}} provides several {\structname{CSA}} types.
We opt for {\sdslclass{csa\_wt}{csa_wt.hpp}}, which is based on a {\structname{WT}}.
Choosing a Huffman-shaped {\structname{WT}} \cite{MAK:NAV:2005} ({\sdslclass{wt\_huff}{wt_huff.hpp}}) and parameterizing it
with a suitable {\structname{BV}} ({\sdslclass{rrr\_vector}{rrr_vector.hpp}}) results in an
$H_k$-compressed {\structname{CSA}}.
The {\sdslclass{rrr\_vector}{rrr_vector.hpp}}\ implements the on-the-fly decoding recently
described by {\citet{NAV:PRO:2012}}, which provides low redundancy.
Finally, we minimize the space of the {\structname{CSA}} by sampling (inverse)
{\structname{SA}} values only every millionth position.
This does not affect the runtime of {\algname{GREEDY}}, since it does not
require SA access.
For {\identifier{wtd}} we choose the alphabet-friendly {\structname{WT}} class {{\sdslclass{wt\_int}{wt_int.hpp}}}
and parameterize it with a fast uncompressed {\structname{BV}}
({\sdslclass{bit\_vector}{int_vector.hpp}}) and small overhead rank structure
({\sdslclass{rank\_support\_v5}{rank_support_v5.hpp}}).
No select functionality is required in {\algname{GREEDY}}.

We use the same toolbox to assemble a space- and time-efficient
version of {\algname{SADA}}.
The full {\structname{CSA}} in {\algname{SADA}} has to provide fast element access;
``plug-and-play'' exploration with different {\structname{CSA}}s showed
that {{\sdslclass{csa\_sada}{csa_sada.hpp}}} {\cite{SAD:2003}} is the preferred choice in this situation.
The suffix sampling rate is set to $32$.
Similar exploration revealed that a text-order sampling strategy
yields a more attractive time-space trade-off than suffix-order
sampling, provided the Elias-Fano compressed {\structname{BV}} \cite{OKA:SAD:2007}
({{\sdslclass{sd\_vector}{sd_vector.hpp}}}) is used to mark the sampled suffixes.
For components {\tt{rminq}} and {\tt{rmaxq}}
we select the
range min-max-tree based
{\structname{RMQ}} structure ({\sdslclass{rmq\_succinct\_sct}{rmq_succinct_sct.hpp}}).
The inverse {\structname{SA}}s of the documents are represented using
bit-compressed vectors ({\sdslclass{int\_vector}{int_vector.hpp}}), and the array of vectors
is denoted by {\identifier{doc\_isa}}.

Finally, we compose word alphabet versions of {\algname{GREEDY}} and {\algname{SADA}}
by replacing the character alphabet strategy ({\sdslclass{byte\_alphabet}{csa_alphabet_strategy.hpp}})
in
the definition of
{\tt{csa\_full}} by the word alphabet strategy
({{\sdslclass{int\_alphabet}{csa_alphabet_strategy.hpp}}}).

\begin{table}
\small
\centering
\begin{tabular}{@{}l@{\hspace{0.2ex}}*{2}{rr@{\hspace{1ex}}l}c*{2}{rr@{\hspace{1ex}}l}@{}}
\toprule
\multirow{2}{*}{Collection}
&\ &\multicolumn{5}{c}{character alphabet}                           &  &\multicolumn{5}{c}{word alphabet} \\
\cmidrule{3-7}\cmidrule{9-14}
&\ &\multicolumn{2}{c}{\algname{GREEDY}}&\ &\multicolumn{2}{c}{\algname{SADA}}   &  &\multicolumn{2}{c}{\algname{GREEDY}}&\ &\multicolumn{2}{c}{\algname{SADA}}&  \\[1ex]
{\sc  proteins}&& \dsu{PROTEINS.GREEDY.byte}{162} & (2.87)&&
                  \dsu{PROTEINS.SADA.byte}{136} & (2.42) &
                  &\multicolumn{5}{c}{\textit{-- no word parsing --}} & \\
{\sc  enwiki-sml}&& \dsu{ENWIKISML.GREEDY.byte}{130} & (2.01)&&
                    \dsu{ENWIKISML.SADA.byte}{204} & (3.13)  &  &
                    \dsu{ENWIKISMLINT.GREEDYINT.int}{38} & (1.32)&&
                    \dsu{ENWIKISMLINT.SADAINT.int}{50} & (1.72) &  \\
{\sc  enwiki-big}&& \dsu{ENWIKIBIG.GREEDY.byte}{27,043} & (3.17)&&
                    \dsu{ENWIKIBIG.SADA.byte}{24,404} & (2.86) & &
                    \dsu{ENWIKIBIGINT.GREEDYINT.int}{6,786} & (1.46)&&
                    \dsu{ENWIKIBIGINT.SADAINT.int}{5,703} & (1.23) &  \\
\bottomrule
\end{tabular}
\caption{Sizes of indexes, in MB and as a
multiple of the collection.
\label{tbl-sizes}}
\end{table}

\paragraph{Memory Usage.}

\begin{wrapfigure}[16]{right}{7.5cm}
\centering
\vspace*{-6ex}
\begin{tikzpicture}
\def6.3cm{6.3cm}

\node[overlay,right,inner sep=0,above right] (sunburst) at (0cm,0cm) {\scalebox{0.40}{\href{\dsl{ENWIKIBIG.SADA.byte}}{\includegraphics{fig-memorysun_SADA_ENWIKIBIG.pdf}}}};

\draw[white] (0cm,0cm) rectangle(7.0cm,6.3cm);

\coordinate (legend) at (5cm, 6.1cm);
\coordinate (medx) at (3.3cm, 7cm);
\sunburstbullet{l_docisa}{legend}{\identifier{doc\_isa}}{56.6\%}
\sunburstbullet{l_rmaxq}{l_docisa}{\identifier{rmaxq}}{11.2\%}
\sunburstbullet{l_rminq}{l_rmaxq}{\identifier{rminq}}{11.2\%}
\sunburstbullet{l_fullcsa}{l_rminq}{\identifier{csa\_full}}{21.0\%}

\sunburstconnect{1.10cm}{2.50cm}{docisa}
\sunburstconnect{2.25cm}{3.10cm}{rmaxq}
\sunburstconnect{2.50cm}{2.65cm}{rminq}
\sunburstconnect{2.45cm}{2.00cm}{fullcsa}

\end{tikzpicture}

\vspace*{-2ex}
\caption{Sunburst visualization of the memory
         usage of the character-based {\algname{SADA}}
         on file {{\sc enwiki-big}}. A dynamic
         version is available at
         \href{http://go.unimelb.edu.au/ba8n}{http://go.unimelb.edu.au/ba8n}.
\label{fig-sunburst}}
\end{wrapfigure}

Table~\ref{tbl-sizes} summarizes the space usage of the composed
structures.
They take considerably less space than those reported by
{\citeauthor{CUL:NAV:PUG:TUR:2010}}; for example, on {{\sc proteins}},
their {\algname{SADA}} is $6.4$ times larger than ours,
and their {\algname{GREEDY}} is $1.3$ times larger.
Also note that when the documents are short, our {\algname{SADA}} is smaller
than {\algname{GREEDY}}.
These space reductions result from the use of better-engineered
components; the only algorithmic change made was the use of
bit-compressed inverse {\structname{SA}}s, instead of high-overhead {\structname{CSA}}s.

Figure~\ref{fig-sunburst} depicts a space visualization of the type
that can be generated for any {{\sc{sdsl}}}
object.
It reveals that {\tt{doc\_isa}} still takes over half the space; that
{\tt{rmaxq}} and {\tt{rminq}} are close to the optimal $2n$ bits
($2.6n$ bits); and that the {\structname{CSA}} takes $5.3$ bits per character.
The latter differs from the optimal $H_k=2.02$ bits reported
in Table~\ref{tbl-sizes}, as samples were added for fast SA access,
which account for $2.4$ of the $5.3$
bits.
The largest component of {\algname{GREEDY}} (not shown here) is the document
array $\ensuremath{\mathcal{D}}$, which requires $n\log N$ bits plus the overhead of the
rank structure, around $92.2\%$ of the total space for
{{\sc enwiki-big}}.
Plugging in {\sdslclass{rrr\_vector}{rrr_vector.hpp}}\ results in $H_0$-compression of \identifier{wtd}\ and reduces
the overall size to {\dsu{ENWIKIBIG.GREEDY-RRR.byte}{\mb{25,\!320}}},
while the query time is slowed down by a factor of between $2$ and $4$.
Note that the word versions are smaller than the character-based
ones, because $n$ is smaller.
{\algname{SADA}} also benefits from smaller average document lengths.
Overall the word indexes are smaller than the character-based
indexes, and at around $2/3$ of the original text size, are
comparable to compressed positional inverted files.

\paragraph{Runtime.}

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1pt,y=1pt]
\definecolor[named]{fillColor}{rgb}{1.00,1.00,1.00}
\path[use as bounding box,fill=fillColor,fill opacity=0.00] (0,0) rectangle (397.48,144.54);
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) --
	(207.74, 24.00) --
	(207.74,126.54) --
	( 44.40,126.54) --
	( 44.40, 24.00);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.75,0.75,0.75}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) --
	(207.74, 24.00) --
	(207.74,126.54) --
	( 44.40,126.54) --
	( 44.40, 24.00);
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.83,0.83,0.83}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 63.62, 24.00) -- ( 63.62,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.66, 24.00) -- (111.66,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (159.70, 24.00) -- (159.70,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 24.00) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- (207.74, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- (207.74, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 15.66) -- (207.74, 15.66);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) -- (207.74, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 28.88) -- (207.74, 28.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 32.34) -- (207.74, 32.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- (207.74, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 37.23) -- (207.74, 37.23);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 39.08) -- (207.74, 39.08);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 40.69) -- (207.74, 40.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 42.11) -- (207.74, 42.11);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 51.72) -- (207.74, 51.72);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 56.60) -- (207.74, 56.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 60.07) -- (207.74, 60.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 62.75) -- (207.74, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 64.95) -- (207.74, 64.95);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 66.80) -- (207.74, 66.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 68.41) -- (207.74, 68.41);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 69.83) -- (207.74, 69.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- (207.74, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 79.44) -- (207.74, 79.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 84.32) -- (207.74, 84.32);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 87.79) -- (207.74, 87.79);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 90.47) -- (207.74, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 92.67) -- (207.74, 92.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 94.52) -- (207.74, 94.52);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 96.13) -- (207.74, 96.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 97.55) -- (207.74, 97.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- (207.74, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,107.16) -- (207.74,107.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,112.05) -- (207.74,112.05);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,115.51) -- (207.74,115.51);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,118.20) -- (207.74,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,120.39) -- (207.74,120.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,122.25) -- (207.74,122.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,123.85) -- (207.74,123.85);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,125.27) -- (207.74,125.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,134.88) -- (207.74,134.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,139.77) -- (207.74,139.77);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,143.23) -- (207.74,143.23);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- ( 44.40,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- ( 42.00, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- ( 42.00, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 62.75) -- ( 42.00, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- ( 42.00, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 90.47) -- ( 42.00, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- ( 42.00, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,118.20) -- ( 42.00,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- ( 42.00,126.54);

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 32.97) {0.05};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 41.31) {0.1};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 60.69) {0.5};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 69.03) {1};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 88.41) {5};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 96.75) {10};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40,116.13) {50};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40,124.47) {100};

\node[text=drawColor,rotate= 90.00,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at ( 12.00, 75.27) {Time per query (milliseconds)};

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 63.62, 24.00) -- (207.74, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 63.62, 24.00) -- ( 63.62, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.66, 24.00) -- (111.66, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (159.70, 24.00) -- (159.70, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 24.00) -- (207.74, 21.60);

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 63.62, 13.20) {5};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (111.66, 13.20) {10};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (159.70, 13.20) {15};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (207.74, 13.20) {20};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at (126.07,  4.80) {Pattern length};
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 57.19) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 54.01, 54.79) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 63.62, 52.59) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 73.23, 52.19) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 82.83, 48.73) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 92.44, 48.26) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (102.05, 47.17) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.66, 47.60) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (121.27, 44.19) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (130.88, 45.16) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.48, 43.01) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (150.09, 44.08) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (159.70, 42.37) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (169.31, 45.67) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (178.92, 45.67) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (188.53, 45.57) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (198.13, 45.67) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 44.52) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 49.15,120.02) -- ( 49.26,119.94);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 41.22,123.68) -- ( 47.58,123.68);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,120.50) -- ( 44.40,126.86);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 50.83,116.27) -- ( 57.19,116.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 54.01,113.09) -- ( 54.01,119.46);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 60.43,110.39) -- ( 66.80,110.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 63.62,107.20) -- ( 63.62,113.57);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 70.04,105.97) -- ( 76.41,105.97);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 73.23,102.79) -- ( 73.23,109.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 79.65, 99.67) -- ( 86.02, 99.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 82.83, 96.49) -- ( 82.83,102.85);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 89.26, 94.95) -- ( 95.62, 94.95);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 92.44, 91.77) -- ( 92.44, 98.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 98.87, 90.08) -- (105.23, 90.08);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (102.05, 86.90) -- (102.05, 93.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (108.48, 84.84) -- (114.84, 84.84);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.66, 81.66) -- (111.66, 88.02);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (118.09, 78.23) -- (124.45, 78.23);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (121.27, 75.05) -- (121.27, 81.42);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (127.69, 73.86) -- (134.06, 73.86);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (130.88, 70.68) -- (130.88, 77.04);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (137.30, 71.43) -- (143.67, 71.43);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.48, 68.25) -- (140.48, 74.61);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (146.91, 67.55) -- (153.27, 67.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (150.09, 64.37) -- (150.09, 70.74);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (156.52, 65.55) -- (162.88, 65.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (159.70, 62.37) -- (159.70, 68.74);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (166.13, 64.83) -- (172.49, 64.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (169.31, 61.64) -- (169.31, 68.01);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (175.74, 61.64) -- (182.10, 61.64);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (178.92, 58.46) -- (178.92, 64.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (185.34, 58.70) -- (191.71, 58.70);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (188.53, 55.51) -- (188.53, 61.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (194.95, 56.28) -- (201.32, 56.28);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (198.13, 53.10) -- (198.13, 59.46);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (204.56, 55.20) -- (210.92, 55.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 52.02) -- (207.74, 58.38);
\definecolor[named]{drawColor}{rgb}{1.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 92.12) --
	( 54.01, 78.51) --
	( 63.62, 71.36) --
	( 73.23, 56.03) --
	( 82.83, 48.10) --
	( 92.44, 45.37) --
	(102.05, 38.19) --
	(111.66, 36.18) --
	(121.27, 33.49) --
	(130.88, 32.93) --
	(140.48, 32.93) --
	(150.09, 32.64) --
	(159.70, 33.22) --
	(169.31, 33.76) --
	(178.92, 34.03) --
	(188.53, 34.29) --
	(198.13, 34.79) --
	(207.74, 35.03);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.80,0.80,0.80}
\definecolor[named]{fillColor}{rgb}{0.80,0.80,0.80}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round,fill=fillColor] ( 44.40,126.54) rectangle (207.74,133.75);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.90] at (126.07,127.65) {\textsc{enwiki-sml}};
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.09,114.66) -- (156.29,114.66);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.09,101.70) -- (156.29,101.70);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (148.19,114.66) circle (  2.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (145.33,101.70) -- (151.05,101.70);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (148.19, 98.84) -- (148.19,104.56);

\node[text=drawColor,anchor=base west,inner sep=0pt, outer sep=0pt, scale=  0.90] at (164.39,111.56) {GREEDY};

\node[text=drawColor,anchor=base west,inner sep=0pt, outer sep=0pt, scale=  0.90] at (164.39, 98.60) {SADA};
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) --
	(389.08, 24.00) --
	(389.08,126.54) --
	(225.74,126.54) --
	(225.74, 24.00);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.75,0.75,0.75}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) --
	(389.08, 24.00) --
	(389.08,126.54) --
	(225.74,126.54) --
	(225.74, 24.00);
\end{scope}
\begin{scope}
\path[clip] (225.74, 24.00) rectangle (389.08,126.54);
\definecolor[named]{drawColor}{rgb}{0.83,0.83,0.83}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (244.96, 24.00) -- (244.96,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (293.00, 24.00) -- (293.00,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (341.04, 24.00) -- (341.04,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 24.00) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 71.10) -- (389.08, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 98.82) -- (389.08, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,126.54) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 15.66) -- (389.08, 15.66);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) -- (389.08, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 28.88) -- (389.08, 28.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 32.34) -- (389.08, 32.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 35.03) -- (389.08, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 37.23) -- (389.08, 37.23);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 39.08) -- (389.08, 39.08);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 40.69) -- (389.08, 40.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 42.11) -- (389.08, 42.11);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 51.72) -- (389.08, 51.72);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 56.60) -- (389.08, 56.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 60.07) -- (389.08, 60.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 62.75) -- (389.08, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 64.95) -- (389.08, 64.95);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 66.80) -- (389.08, 66.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 68.41) -- (389.08, 68.41);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 69.83) -- (389.08, 69.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 71.10) -- (389.08, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 79.44) -- (389.08, 79.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 84.32) -- (389.08, 84.32);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 87.79) -- (389.08, 87.79);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 90.47) -- (389.08, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 92.67) -- (389.08, 92.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 94.52) -- (389.08, 94.52);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 96.13) -- (389.08, 96.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 97.55) -- (389.08, 97.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 98.82) -- (389.08, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,107.16) -- (389.08,107.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,112.05) -- (389.08,112.05);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,115.51) -- (389.08,115.51);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,118.20) -- (389.08,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,120.39) -- (389.08,120.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,122.25) -- (389.08,122.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,123.85) -- (389.08,123.85);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,125.27) -- (389.08,125.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,126.54) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,134.88) -- (389.08,134.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,139.77) -- (389.08,139.77);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,143.23) -- (389.08,143.23);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (244.96, 24.00) -- (389.08, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (244.96, 24.00) -- (244.96, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (293.00, 24.00) -- (293.00, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (341.04, 24.00) -- (341.04, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 24.00) -- (389.08, 21.60);

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (244.96, 13.20) {5};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (293.00, 13.20) {10};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (341.04, 13.20) {15};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (389.08, 13.20) {20};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at (307.41,  4.80) {Pattern length};
\end{scope}
\begin{scope}
\path[clip] (225.74, 24.00) rectangle (389.08,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,108.34) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (235.35,104.45) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (244.96, 99.30) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (254.57, 95.98) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (264.18, 91.33) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (273.78, 87.68) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (283.39, 83.57) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (293.00, 79.25) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (302.61, 77.31) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (312.22, 75.26) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (321.83, 71.62) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (331.43, 69.90) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (341.04, 68.04) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (350.65, 69.46) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (360.26, 68.26) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (369.87, 65.95) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (379.48, 67.55) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 67.26) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (316.85,120.31) -- (317.19,120.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (326.13,112.04) -- (327.13,111.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (309.04,124.13) -- (315.40,124.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (312.22,120.94) -- (312.22,127.31);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (318.64,116.22) -- (325.01,116.22);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (321.83,113.04) -- (321.83,119.40);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (328.25,106.89) -- (334.62,106.89);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (331.43,103.71) -- (331.43,110.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (337.86,102.22) -- (344.23,102.22);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (341.04, 99.04) -- (341.04,105.40);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (347.47,100.44) -- (353.83,100.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (350.65, 97.25) -- (350.65,103.62);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (357.08, 99.80) -- (363.44, 99.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (360.26, 96.62) -- (360.26,102.98);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (366.69, 92.68) -- (373.05, 92.68);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (369.87, 89.49) -- (369.87, 95.86);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (376.29, 94.43) -- (382.66, 94.43);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (379.48, 91.25) -- (379.48, 97.62);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (385.90, 91.75) -- (392.27, 91.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 88.56) -- (389.08, 94.93);
\definecolor[named]{drawColor}{rgb}{1.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (254.57,116.18) --
	(264.18,102.82) --
	(273.78, 98.21) --
	(283.39, 90.85) --
	(293.00, 77.41) --
	(302.61, 73.31) --
	(312.22, 66.22) --
	(321.83, 60.16) --
	(331.43, 48.96) --
	(341.04, 46.90) --
	(350.65, 46.16) --
	(360.26, 46.63) --
	(369.87, 43.26) --
	(379.48, 47.43) --
	(389.08, 45.37);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.80,0.80,0.80}
\definecolor[named]{fillColor}{rgb}{0.80,0.80,0.80}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round,fill=fillColor] (225.74,126.54) rectangle (389.08,133.75);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.90] at (307.41,127.65) {\textsc{enwiki-big}};
\end{scope}
\end{tikzpicture}
\caption{Average time for top-$10$ {\emph{frequency}} queries on the
character-based collections.
Results are omitted for pattern length $\ell$ if any single pattern
of length $\ell$ took more than $5$ seconds. The solid red line
corresponds to a baseline implementation which is explained in the text.
\label{fig-runtime}}
\end{figure}%

\begin{figure}[t]
\centering
\begin{tikzpicture}[x=1pt,y=1pt]
\definecolor[named]{fillColor}{rgb}{1.00,1.00,1.00}
\path[use as bounding box,fill=fillColor,fill opacity=0.00] (0,0) rectangle (397.48,144.54);
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) --
	(207.74, 24.00) --
	(207.74,126.54) --
	( 44.40,126.54) --
	( 44.40, 24.00);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.75,0.75,0.75}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) --
	(207.74, 24.00) --
	(207.74,126.54) --
	( 44.40,126.54) --
	( 44.40, 24.00);
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.83,0.83,0.83}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) -- ( 44.40,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 85.24, 24.00) -- ( 85.24,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (126.07, 24.00) -- (126.07,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (166.91, 24.00) -- (166.91,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 24.00) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- (207.74, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- (207.74, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 15.66) -- (207.74, 15.66);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) -- (207.74, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 28.88) -- (207.74, 28.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 32.34) -- (207.74, 32.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- (207.74, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 37.23) -- (207.74, 37.23);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 39.08) -- (207.74, 39.08);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 40.69) -- (207.74, 40.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 42.11) -- (207.74, 42.11);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- (207.74, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 51.72) -- (207.74, 51.72);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 56.60) -- (207.74, 56.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 60.07) -- (207.74, 60.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 62.75) -- (207.74, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 64.95) -- (207.74, 64.95);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 66.80) -- (207.74, 66.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 68.41) -- (207.74, 68.41);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 69.83) -- (207.74, 69.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- (207.74, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 79.44) -- (207.74, 79.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 84.32) -- (207.74, 84.32);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 87.79) -- (207.74, 87.79);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 90.47) -- (207.74, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 92.67) -- (207.74, 92.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 94.52) -- (207.74, 94.52);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 96.13) -- (207.74, 96.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 97.55) -- (207.74, 97.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- (207.74, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,107.16) -- (207.74,107.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,112.05) -- (207.74,112.05);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,115.51) -- (207.74,115.51);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,118.20) -- (207.74,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,120.39) -- (207.74,120.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,122.25) -- (207.74,122.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,123.85) -- (207.74,123.85);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,125.27) -- (207.74,125.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- (207.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,134.88) -- (207.74,134.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,139.77) -- (207.74,139.77);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,143.23) -- (207.74,143.23);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- ( 44.40,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 35.03) -- ( 42.00, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 43.38) -- ( 42.00, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 62.75) -- ( 42.00, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 71.10) -- ( 42.00, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 90.47) -- ( 42.00, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 98.82) -- ( 42.00, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,118.20) -- ( 42.00,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,126.54) -- ( 42.00,126.54);

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 32.97) {0.05};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 41.31) {0.1};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 60.69) {0.5};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 69.03) {1};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 88.41) {5};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40, 96.75) {10};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40,116.13) {50};

\node[text=drawColor,anchor=base east,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 38.40,124.47) {100};

\node[text=drawColor,rotate= 90.00,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at ( 12.00, 75.27) {Time per query (milliseconds)};

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) -- (207.74, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 24.00) -- ( 44.40, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 85.24, 24.00) -- ( 85.24, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (126.07, 24.00) -- (126.07, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (166.91, 24.00) -- (166.91, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 24.00) -- (207.74, 21.60);

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 44.40, 13.20) {2};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at ( 85.24, 13.20) {4};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (126.07, 13.20) {6};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (166.91, 13.20) {8};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (207.74, 13.20) {10};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at (126.07,  4.80) {Pattern length};
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 50.33, 46.27) -- ( 58.89, 44.98);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 70.79, 44.60) -- ( 79.26, 45.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 91.19, 46.61) -- ( 99.70, 47.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.62, 49.07) -- (120.11, 50.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (132.05, 51.19) -- (140.51, 51.94);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (152.47, 52.96) -- (160.93, 53.64);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (172.89, 54.52) -- (181.34, 55.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (193.31, 55.90) -- (201.76, 56.45);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 47.17) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 64.82, 44.08) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 85.24, 45.87) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (105.65, 48.42) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (126.07, 50.65) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (146.49, 52.48) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (166.91, 54.12) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (187.32, 55.51) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 56.84) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 48.10,104.55) -- ( 61.12, 87.89);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 67.79, 77.96) -- ( 82.26, 52.64);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 90.91, 45.47) -- ( 99.98, 42.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (111.65, 40.29) -- (120.07, 40.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (132.07, 40.25) -- (140.49, 40.51);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (152.48, 40.95) -- (160.91, 41.30);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (172.90, 41.80) -- (181.33, 42.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (193.32, 42.60) -- (201.75, 42.91);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 41.22,109.28) -- ( 47.58,109.28);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40,106.09) -- ( 44.40,112.46);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 61.64, 83.17) -- ( 68.00, 83.17);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 64.82, 79.98) -- ( 64.82, 86.35);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 82.05, 47.43) -- ( 88.42, 47.43);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 85.24, 44.25) -- ( 85.24, 50.61);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (102.47, 40.39) -- (108.84, 40.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (105.65, 37.20) -- (105.65, 43.57);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (122.89, 40.07) -- (129.25, 40.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (126.07, 36.89) -- (126.07, 43.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (143.31, 40.69) -- (149.67, 40.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (146.49, 37.51) -- (146.49, 43.87);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (163.72, 41.56) -- (170.09, 41.56);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (166.91, 38.38) -- (166.91, 44.74);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (184.14, 42.37) -- (190.51, 42.37);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (187.32, 39.19) -- (187.32, 45.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (204.56, 43.13) -- (210.92, 43.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (207.74, 39.95) -- (207.74, 46.32);
\definecolor[named]{drawColor}{rgb}{1.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] ( 44.40, 58.25) --
	( 64.82, 27.16) --
	( 85.24, 26.20) --
	(105.65, 28.88) --
	(126.07, 31.41) --
	(146.49, 33.22) --
	(166.91, 34.79) --
	(187.32, 36.18) --
	(207.74, 37.43);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.80,0.80,0.80}
\definecolor[named]{fillColor}{rgb}{0.80,0.80,0.80}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round,fill=fillColor] ( 44.40,126.54) rectangle (207.74,133.75);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.90] at (126.07,127.65) {\textsc{enwiki-sml}};
\end{scope}
\begin{scope}
\path[clip] ( 44.40, 24.00) rectangle (207.74,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.09,101.70) -- (156.29,101.70);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (140.09, 88.74) -- (156.29, 88.74);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (148.19,101.70) circle (  2.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (145.33, 88.74) -- (151.05, 88.74);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (148.19, 85.88) -- (148.19, 91.60);

\node[text=drawColor,anchor=base west,inner sep=0pt, outer sep=0pt, scale=  0.90] at (164.39, 98.60) {GREEDY};

\node[text=drawColor,anchor=base west,inner sep=0pt, outer sep=0pt, scale=  0.90] at (164.39, 85.64) {SADA};
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) --
	(389.08, 24.00) --
	(389.08,126.54) --
	(225.74,126.54) --
	(225.74, 24.00);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.75,0.75,0.75}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) --
	(389.08, 24.00) --
	(389.08,126.54) --
	(225.74,126.54) --
	(225.74, 24.00);
\end{scope}
\begin{scope}
\path[clip] (225.74, 24.00) rectangle (389.08,126.54);
\definecolor[named]{drawColor}{rgb}{0.83,0.83,0.83}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) -- (225.74,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (266.58, 24.00) -- (266.58,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (307.41, 24.00) -- (307.41,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (348.25, 24.00) -- (348.25,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 24.00) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 71.10) -- (389.08, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 98.82) -- (389.08, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,126.54) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 15.66) -- (389.08, 15.66);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) -- (389.08, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 28.88) -- (389.08, 28.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 32.34) -- (389.08, 32.34);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 35.03) -- (389.08, 35.03);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 37.23) -- (389.08, 37.23);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 39.08) -- (389.08, 39.08);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 40.69) -- (389.08, 40.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 42.11) -- (389.08, 42.11);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 43.38) -- (389.08, 43.38);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 51.72) -- (389.08, 51.72);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 56.60) -- (389.08, 56.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 60.07) -- (389.08, 60.07);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 62.75) -- (389.08, 62.75);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 64.95) -- (389.08, 64.95);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 66.80) -- (389.08, 66.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 68.41) -- (389.08, 68.41);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 69.83) -- (389.08, 69.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 71.10) -- (389.08, 71.10);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 79.44) -- (389.08, 79.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 84.32) -- (389.08, 84.32);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 87.79) -- (389.08, 87.79);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 90.47) -- (389.08, 90.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 92.67) -- (389.08, 92.67);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 94.52) -- (389.08, 94.52);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 96.13) -- (389.08, 96.13);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 97.55) -- (389.08, 97.55);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 98.82) -- (389.08, 98.82);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,107.16) -- (389.08,107.16);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,112.05) -- (389.08,112.05);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,115.51) -- (389.08,115.51);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,118.20) -- (389.08,118.20);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,120.39) -- (389.08,120.39);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,122.25) -- (389.08,122.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,123.85) -- (389.08,123.85);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,125.27) -- (389.08,125.27);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,126.54) -- (389.08,126.54);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,134.88) -- (389.08,134.88);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,139.77) -- (389.08,139.77);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,143.23) -- (389.08,143.23);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) -- (389.08, 24.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 24.00) -- (225.74, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (266.58, 24.00) -- (266.58, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (307.41, 24.00) -- (307.41, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (348.25, 24.00) -- (348.25, 21.60);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 24.00) -- (389.08, 21.60);

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (225.74, 13.20) {2};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (266.58, 13.20) {4};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (307.41, 13.20) {6};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (348.25, 13.20) {8};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.60] at (389.08, 13.20) {10};

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.80] at (307.41,  4.80) {Pattern length};
\end{scope}
\begin{scope}
\path[clip] (225.74, 24.00) rectangle (389.08,126.54);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (230.39, 87.98) -- (241.52, 78.86);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (251.56, 72.45) -- (261.18, 67.80);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (272.22, 63.14) -- (281.35, 59.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (292.97, 57.23) -- (301.44, 56.45);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (313.41, 56.19) -- (321.84, 56.59);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (333.83, 57.15) -- (342.26, 57.52);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (354.24, 58.18) -- (362.68, 58.73);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (374.66, 59.46) -- (383.09, 59.92);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74, 91.78) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (246.16, 75.06) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (266.58, 65.19) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (287.00, 57.79) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (307.41, 55.90) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (327.83, 56.88) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (348.25, 57.79) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (368.67, 59.13) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 60.25) circle (  2.25);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (291.50, 82.49) -- (302.91, 72.44);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (312.92, 66.08) -- (322.33, 62.00);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (333.51, 57.67) -- (342.57, 54.58);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (354.25, 52.66) -- (362.67, 52.69);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (374.67, 52.59) -- (383.09, 52.42);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (283.81, 86.45) -- (290.18, 86.45);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (287.00, 83.27) -- (287.00, 89.63);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (304.23, 68.47) -- (310.60, 68.47);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (307.41, 65.29) -- (307.41, 71.65);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (324.65, 59.61) -- (331.01, 59.61);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (327.83, 56.42) -- (327.83, 62.79);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (345.07, 52.65) -- (351.43, 52.65);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (348.25, 49.47) -- (348.25, 55.83);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (365.49, 52.70) -- (371.85, 52.70);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (368.67, 49.52) -- (368.67, 55.89);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (385.90, 52.31) -- (392.27, 52.31);

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (389.08, 49.13) -- (389.08, 55.49);
\definecolor[named]{drawColor}{rgb}{1.00,0.00,0.00}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round] (225.74,120.56) --
	(246.16, 76.16) --
	(266.58, 50.52) --
	(287.00, 46.06) --
	(307.41, 46.16) --
	(327.83, 45.57) --
	(348.25, 47.34) --
	(368.67, 38.37) --
	(389.08, 39.59);
\end{scope}
\begin{scope}
\path[clip] (  0.00,  0.00) rectangle (397.48,144.54);
\definecolor[named]{drawColor}{rgb}{0.80,0.80,0.80}
\definecolor[named]{fillColor}{rgb}{0.80,0.80,0.80}

\path[draw=drawColor,line width= 0.4pt,line join=round,line cap=round,fill=fillColor] (225.74,126.54) rectangle (389.08,133.75);
\definecolor[named]{drawColor}{rgb}{0.00,0.00,0.00}

\node[text=drawColor,anchor=base,inner sep=0pt, outer sep=0pt, scale=  0.90] at (307.41,127.65) {\textsc{enwiki-big}};
\end{scope}
\end{tikzpicture}
\caption{Average time for top-$10$ {\emph{frequency}} queries on the
word-based collections.
\label{fig-runtime_int}}
\end{figure}

Query times are depicted in Figures~\ref{fig-runtime}
and~\ref{fig-runtime_int}.
We make several observations.
First, the runtime of both solutions depend on the collection size,
since any given pattern occurs more often in a larger collection.
This results in larger ranges, which are especially bad for {\algname{SADA}},
since it processes all distinct documents in the range, even when
computing top-$10$ queries.
(This same behavior means that {\algname{SADA}} can compute complex
{\emph{tf-idf}} queries in very similar times.)
{\algname{GREEDY}} is also dependent on size of the $[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$ range,
requiring two orders of magnitudes more time on {{\sc enwiki-big}} than
on {{\sc enwiki-sml}}, matching the difference in their sizes.
Second, for long patterns ($>$$15$ characters) {\algname{SADA}} is now only
one order of magnitude slower than {\algname{GREEDY}}, in contrast to two
orders reported by {\citet{CUL:NAV:PUG:TUR:2010}}.
This is due to the faster extraction of inverse SA values and the
use of a $\Psi$-based {\structname{CSA}} instead of a {\structname{WT}} based one.
For word indexes {\algname{SADA}} now outperforms {\algname{GREEDY}} for long queries,
where the result range is very small.
In this cases, the pattern matching becomes the dominating cost.
In {\algname{SADA}}, we used {\sdslclass{csa\_sada}{csa_sada.hpp}}\ which implements backward search
by binary searches on $\Psi$ using $\Order{m\log n}$ time, while
{{\sdslclass{csa\_wt}{csa_wt.hpp}}} in {\algname{GREEDY}} performs $\Order{mH_0(\ensuremath{\mathcal{T}})}$ non-local rank
operations on the compressed BV.
The {\algname{GREEDY}} approach could be made significantly faster if the {{\sdslclass{rrr\_vector}{rrr_vector.hpp}}} was
replaced by an uncompressed BV, but the space would then become
much greater than {\algname{SADA}}.

We also compare our results to a simple baseline called {\algname{SORT}}.
Again, {{\sdslclass{csa\_wt}{csa_wt.hpp}}} is used as the {\structname{CSA}}, but now the document array \ensuremath{\mathcal{D}}\ is
stored as a bit-compressed vector of $n\lceil\log N\rceil$ bits.
After identifying the $[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$ interval, the entries of
$\ensuremath{\mathcal{D}}[\mbox{\emph{sp}}..\mbox{\emph{ep}}]$ are copied and sorted to generate $(d_i,\tf)$
pairs; the standard C++ partial sort is then used to retrieve the
top-$10$.
The red lines in Figures~\ref{fig-runtime} and~\ref{fig-runtime_int}
show query times.
The sequential or local processing of {\algname{SORT}} is always superior to {\algname{SADA}},
which, despite careful implementation, suffers from the non-locality
of the range minimum/maximum queries.
Moreover, {\algname{GREEDY}} only dominates {\algname{SORT}} in cases involving very
wide intervals, emphasizing one of the key messages of this article
-- that careful implementations and large test instances are required
to properly show the usefulness of advanced succinct data structures.

\section{Efficient Construction of Complex Structures}
\label{sec-constr}

Constructing {{\sc{SDSs}}} over small data sets -- up to hundreds of
megabytes -- is not a challenge from an engineering perspective,
since commodity hardware supports memory-space many times larger than
this.
However, {{\sc{SDSs}}} are explicitly intended to replace traditional data
structures in resource-constrained environments; which means they
are most applicable when the data is too large for uncompressed
structures to be used, and hence that construction is also a critical
issue.
As well, complex structures composed of multiple sub-structures often
contain dependencies between sub-structures which further complicate
the construction process.
For example, to construct a {\structname{CST}}, a {\structname{CSA}} is required; and to
construct a {\structname{CSA}} fast, usually an uncompressed {\structname{SA}} is needed.
Under memory constrains, it is not possible to hold all of this
structures in RAM concurrently.
To alleviate this problem the library combines semi-external
construction algorithms which stream data which can be processed
sequentially to and from disk.
To facilitate this, the library provides serialization and save/load
functionality for all substructures.
Finally, as already noted, the library includes memory visualization
techniques, which analyze space utilization during run-time and
construction.

To demonstrate the complexities of the construction process in more
detail, we examine the resource utilization during the construction
of word-based {\algname{SADA}}.
Figure~\ref{sada-construct} shows the resource consumption for the
{\gb{4.6}} {{\sc enwiki-big}} collection.
In total, the construction process took $5{,}250$ seconds and had a
peak requirement of {\gb{13}}.
This corresponds to a throughput of {\mb{0.88}} per second. In monetary terms,
the \algname{SADA}\ index for {{\sc enwiki-big}} can be built for less than one dollar on the Amazon
Cloud.\footnote{In November 2013 a ``High-Memory Extra Large''
instance with {\gb{17}} RAM costs USD$\$0.41$ per hour.}
The majority of the time ($65\%$) was spent constructing the {\structname{CSA}}.
First, the plain {\structname{SA}} is constructed -- phase~$1$ in
Figure~\ref{sada-construct} -- using the algorithm of
{\citet{LAR:SAD:2007}}.
The algorithm uses twice the memory space required by the resulting
bit-compressed suffix array, accounting for the peak memory usage
(\gb{13}) of the complete process.
After construction, the {\structname{SA}} is serialized to disk to construct the
Burrows-Wheeler Transform (BWT) (phase~$2$).
Only {\ensuremath{\mathcal{T}}} is kept in memory, as it is the only place where random
access is required, and the BWT sequence can be written to disk as it
is formed.
This semi-external construction process of the BWT requires $380$
seconds, or $7\%$ of the total time.
The remainder of the {\structname{CSA}} is constructed in $358$ seconds.
This includes constructing $\Psi$ mapping (shown as phase~$3$)
as well
as sampling the {\structname{SA}}.
The next major construction step, marked as phase $4$ in the figure,
constructs the $N$ individual inverse {\structname{SA}}s (\identifier{doc\_isa}).
Here for each document a
{\structname{SA}} is constructed,
inverted, bit-compressed, and added to {\identifier{doc\_isa}}.
This process requires $785$ seconds, or around $200$ microseconds per
document.
Next, phase~$5$ constructs the document array $\ensuremath{\mathcal{D}}$ by
streaming the full {\structname{SA}} from disk and performing $n$ {\method{rank}}
operations
on {\identifier{border}}.
Creating the complete array requires $271$ seconds or $160$
nanoseconds per $\ensuremath{\mathcal{D}}[i]$ value.
This includes streaming the {\structname{SA}} from disk, performing the {\method{rank}}
on {\identifier{border}} and storing the resulting $\ensuremath{\mathcal{D}}[i]$ value.
Finally, {\identifier{rminq}} (phase~$6$) and {\identifier{rmaxq}} (phase~$7$) are
created, including computing temporary $C$ and $C'$ arrays from
$\ensuremath{\mathcal{D}}$.
Creating {\identifier{rminq}} requires $360$ seconds; computing {\identifier{rmaxq}} a
further $396$ seconds.
Half of that time is spent creating $C$ and $C'$; the balance on
constructing the actual {\structname{RMQ}} structures.

\begin{figure}[t]
\centering
\tikzstyle{st_ball} = [overlay,circle,font=\footnotesize,text=white,fill=black,inner sep=0.18mm]

\begin{tikzpicture}
\node[draw=white,inner sep=.3cm] at (0cm,0cm) {};
\node[draw=white,right] (img) at (1cm,0cm) {\scalebox{0.37}{\href{http://people.eng.unimelb.edu.au/sgog/DCC2014/fig-sada-int-construction.html}{\includegraphics{fig-sada-int-construct.pdf}}}};
\foreach \x in {0,500,...,5000}{
    \pgfmathparse{0.2+(2.53*\x/1000)}\let\xpos\pgfmathresult
    \node[overlay, font=\footnotesize] at ($(img.south west)+(\xpos cm, -0.1cm)$) {%
        \pgfkeys{/pgf/number format/.cd,%
            fixed,%
            fixed zerofill,%
            precision=0,%
            set thousands separator={\mbox{,}}}%
        \pgfmathprintnumber{\x}%
    };
}
\foreach \iy in {0,2,...,14}{
    \pgfmathparse{0.2+(0.26*\iy)}\let\ypos\pgfmathresult
    \node[overlay, font=\footnotesize,left] at ($(img.south west)+(0.15 cm, \ypos cm)$) {
        \pgfmathparse{int(\iy*1000)}\let\yy\pgfmathresult
        \pgfkeys{/pgf/number format/.cd,%
            fixed,%
            fixed zerofill,%
            precision=0,%
            set thousands separator={\mbox{,}}}%
        \pgfmathprintnumber{\yy}%
    };
}
\node[font=\footnotesize,yshift=-0.5cm] at (img.south) {Elapsed time in seconds};
\node[font=\footnotesize,xshift=-1.4cm] at (img.west) {\rotatebox{90}{Memory usage in MB}};
\node[st_ball,xshift=-13.1cm,yshift=-3.2cm] at (img.north east) {1};
\node[st_ball,xshift=-7.2cm,yshift=-3.2cm] at (img.north east) {2};
\node[st_ball,xshift=-5.6cm,yshift=-3.2cm] at (img.north east) {3};
\node[st_ball,xshift=-3.0cm,yshift=-3.2cm] at (img.north east) {4};
\node[st_ball,xshift=-2.5cm,yshift=-3.2cm] at (img.north east) {5};
\node[st_ball,xshift=-1.8cm,yshift=-3.2cm] at (img.north east) {6};
\node[st_ball,xshift=-0.9cm,yshift=-3.2cm] at (img.north east) {7};
\node[overlay,font=\footnotesize,xshift=-4.3cm,left,below] (title) at (img.north east) {Selected phases};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm, xshift=0.35cm] (leg1) at (title.south west) {SA};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm] (leg2) at (leg1.south west) {BWT};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm] (leg3) at (leg2.south west) {$\Psi$};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm] (leg4) at (leg3.south west) {{\tt doc\_isa}};

\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm,xshift=2.3cm] (leg5) at (title.south west) {\ensuremath{\mathcal{D}}};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm] (leg6) at (leg5.south west) {{\tt rminq} $C$};
\node[overlay,font=\footnotesize,below,right,yshift=-0.1cm] (leg7) at (leg6.south west) {{\tt rmaxq} $C'$};

\foreach \p in {1,2,3,4,5,6,7}
    \node[st_ball,left] at (leg\p.west) {\p};

\end{tikzpicture}
\caption{A memory-time graph for
construction of {\algname{SADA}} over the word-based
sequence {{\sc enwiki-big}} (\gb{4.6}).
The {\sdslclass{memory\_monitor}{memory_management.hpp}}\ generated version is
available at
 \href{http://go.unimelb.edu.au/7a8n}{http://go.unimelb.edu.au/7a8n}.
\label{sada-construct}}
\end{figure}

Semi-external construction is an important tool to minimize
the resource consumption in each phase of the building process of
SADA.
Keeping all constructed components in memory would significantly
increase the memory overhead during the later stages of the
construction process.
Thus, careful engineering of the construction phase of each
individual component of a complex structure is important so that the
overall resource requirements of the entire construction process is
minimized.
In our case, {\algname{SADA}} is now so efficient that we can build the
structure for the word tokenized GOV2 collection, used in the TREC
Terabyte Track, on our experimental machine.

It is important to monitor the construction costs, as the
modularity of {{\sc{SDSs}}} can lead to unintended resource consumption.
For example, in an initial version of our {\algname{SADA}} implementation, the
{\structname{CSA}} was not serialized to disk, but kept in
memory.
Visualization of the overall construction cost of {\algname{SADA}} highlighted
this inefficiency and allowed it to be rectified.
Similarly, when reviewing the character-based {{\sdslclass{csa\_wt}{csa_wt.hpp}}}, it became
apparent that optimizing {\structname{WT}} construction will not significantly
improve the overall process, as that phase only accounts for around
$4\%$ of the total cost.
An automatic resource tracker ({\sdslclass{memory\_monitor}{memory_management.hpp}}) facilitates
visualizing the space and time consumption of algorithms in order to provide
such insights.

\begin{wraptable}[12]{right}{5.2cm}%
\vspace*{-5.0ex}
\centering
\begin{tabular}{@{}r@{}cr@{}cr@{}}
\toprule
Prefix && \multicolumn{3}{c@{}}{Page size} \\ \cmidrule{3-5}
(MB)  && \multicolumn{1}{c}{\kb{4}} && \multicolumn{1}{c@{}}{\gb{1}} \\ \cmidrule{1-1}\cmidrule{3-3}\cmidrule{5-5}
10     &&     2  &&      2 \\
100    &&    29  &&     25 \\
1,000  &&   379  &&    307 \\
5,000  &&  2,524 &&  1,877 \\
8,535  &&  5,282 &&  4,482 \\
\bottomrule
\end{tabular}
\vspace*{-0.5ex}
\caption{Construction times (seconds) of {{\sdslclass{csa\_wt}{csa_wt.hpp}}}
for prefixes of the character-based {{\sc enwiki-big}}
file.
\label{tbl-csa-construction}}
\end{wraptable}%

Query times for {{\sc{SDSs}}} can be markedly
improved if {\gb{1}} pages (hugepages) are used to address memory,
rather than the standard {\kb{4}} pages, since address translation
becomes a bottleneck when pages are small~\citep{gp13spe}.
The {{\sc{sdsl}}} now includes memory management facilities that allow the use
of hugepages during construction as well.
We investigate the effect of hugepages on construction time by
building {{\sdslclass{csa\_wt}{csa_wt.hpp}}}\,s of increasing size for prefixes of the character-based
{{\sc enwiki-big}} collection
(Table~\ref{tbl-csa-construction}).
For small file sizes, hugepages have a modest effect on construction
time, and the {\mb{100}} file is processed only $16\%$ faster.
As the file size increases the effect becomes more visible.
The index of {\gb{1}} prefix is constructed $24\%$ faster, and the
{\gb{5}} index can be built $35\%$ faster.
The improvement in construction time then decreases for the full
{{\sc enwiki-big}} collection, as the TLB can only maintain a certain
number of hugepage entries, after which address translation becomes
more costly again.

\section{Related Work}
\label{sec-related}

As part of their experimental work authors often make prototype
implementations of their proposed structures available.
Additionally, several experimental studies and public available libraries focusing on
{\sc{SDSs}}\ have emerged over time.
The best known is the widely used {{\sc{Pizza\&Chili}}}
corpus\footnote{\href{http://pizzachili.dcc.uchile.cl}{http://pizzachili.dcc.uchile.cl}}, which was
released alongside an extensive empirical
evaluation~{\citep{FER:GON:NAV:VEN:2008}}.
The corpus includes a collection of reference data sets, plus
implementations of several succinct text index structures accessed
via a common interface.
The {\method{libcds}} library is also popular, and provides
implementations of bitvectors and wavelet
trees~{\citep{CLA:NAV:2008}}.
It has recently been succeeded by
{\method{libcds\oldstylenums{2}}}\footnote{\href{https://github.com/fclaude/libcds2}{https://github.com/fclaude/libcds2}}.
{\citet{VIG:2008}} provides bitvector implementations
supporting {\method{rank}} and {\method{select}} in the {\method{Sux}}
library\footnote{\href{http://sux.di.unimi.it}{http://sux.di.unimi.it}}. The
Java version of \method{Sux} also implements minimal
(monotone) perfect hash functions.
Recently {\citet{GRO:OTT:2013}} presented the {\method{succinct}}
library\footnote{\href{https://github.com/ot/succinct}{https://github.com/ot/succinct}} which
consists of bitvectors, succinct tries and a {\structname{RMQ}} structure;
all structures can be memory mapped.

Compared to these other implementations, {{\sc{sdsl}}} version 2 has a
number of distinctive features:
it operates on both character and words inputs;
it is optimized for large-scale input (including support for
hugepages);
it provides coverage of a wide range of alternative structures, that
can be composed and substituted in different ways; and it offers
dynamic visualizations that allow detailed space evaluations to be
undertaken.
Finally, fully automated tests and benchmarks are also included, and
can be used by other researchers in the future to check the correctness and
performance of further alternative implementations of the various modules.

\section{Conclusion}
\label{sec-conclusion}

We have explored the benefits that flow when modular and composable
implementations of succinct data structure building blocks are
available, and have showed that efficiency at all levels of the
{{\sc{SDSs}}} hierarchy can be enhanced by careful attention to low-level
detail, and to the provision of precisely-defined interfaces.
As a part of that demonstration, we introduced the open source
{{\sc{sdsl}}} library, which contains efficient implementations of many
{{\sc{SDSs}}}.
The library is structured to facilitate flexible prototyping of new
high-level structures, and because it offers a range of options at
each level of the data structure hierarchy, allows rapid exploration
of implementation alternatives.
The library is also robust in terms of scale, handling input
sequences of arbitrary length over arbitrary alphabets.
In addition, we have demonstrated that the use of hugepages can have
a notable effect on execution times of large-scale {{\sc{SDSs}}}; and shown
that the advanced visualization features of the library provide
important insights into the time and space requirements of {{\sc{SDSs}}}.

\paragraph*{Acknowledgment.}

The authors were supported by the Australian
Research Council and by the Deutsche
Forschungsgemeinschaft.

\paragraph*{Software \& Experiments.}
The library code, test suite, benchmarks, and a tutorial, are
publicly available at {\href{https://github.com/simongog/sdsl-lite}%
 {https://github.com/simongog/sdsl-lite}}.

\begin{footnotesize}
\bibliographystyle{abbrvnat}
\bibsep 0.5mm