[bsc-thesis1415.git] / thesis2 / 1.introduction.tex

\section{Introduction}
What do people do when they want to grab a movie? Attend a concert? Find out
which theater shows play in local theater?

When the internet was in its early days and it started to be accessible to most
of the people information about entertainment was still obtained almost
exclusively from flyers, books, posters, radio/TV advertisements. People had to
look hard for information and you could easily miss a show just because you did
not cross paths with it.
Today the internet is used by almost everyone in the western society on a daily
basis and we would think that missing an event would be impossible because of
the enormous loads of information you can receive every day using the internet.
The opposite is true for information about leisure activities.

Nowadays information on the internet about entertainment is offered via two
main channels: individual venues websites and information bundling websites.

Individual venues put a lot of effort and resources in building a beautiful,
fast and most of all modern website that bundles their information with nice
graphics, animations and gimmicks. There also exist companies that bundle the
information from different websites to provide an overview. Information
bundling websites often have multiple individual venue websites as the source
for their information and therefore the information is most of the time not
complete. This is because individual venues tend to think, for example, that it
is obvious what the address of their venue is, that their ticket price is
always fixed to \EURdig$5.-$ and that you need a membership to attend the
events. Individual organizations usually put this non specific information in a
disclaimer or a separate page and information bundling website miss out on
these types of information a lot. They miss out because they can crawl these
individual events but gathering the miscellaneous information is usually done
by hand.

Combining the information from the different data source turns out to be a hard
task for such information bundling websites. It is a hard task because
information bundling websites do not have the resources and time reserved for
these tasks and therefore often serve incomplete information. Because of
the complexity of getting complete information there are not many websites
trying to bundle entertainment information into a complete and consistent
database. Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve goal
of serving complete and consistent information.

\section{Hyperleap \& Infotainment}
Hyperleap is an internet company that existed in the time that internet was not
widespread. Hyperleap, active since 1995, is specialized in producing,
publishing and maintaining \textit{infotainment}. \textit{Infotainment} is a
combination of the words \textit{information} and \textit{entertainment}. It
represents a combination of factual information and subjectual information
(entertainment) within a certain category or field. In the case of Hyperleap
the category is the leisure industry, leisure industry encompasses all facets
of entertainment going from cinemas, theaters, concerts to swimming pools,
bridge competitions and conferences. Within the entertainment industry factual
information includes, but is not limited to, information such as starting time,
location, host or venue and duration. Subjectual information includes, but is
not limited to, information such as reviews, previews, photos, background
information and trivia. 

Hyperleap manages the largest database containing \textit{infotainment} about
the leisure industry focussed on the Netherlands and surrounding regions. The
database contains over $10.000$ categorized events on average per week and
their venue database contains over $54.000$ venues delivering the leisure
activities ranging from theaters and music venues to petting zoos and fast food
restaurants. All the subjectual information is obtained or created by Hyperleap
and all factual information is gathered from different sources, quality checked
and therefore very reliable. Hyperleap is the only company in its kind that has
such high quality information. The \textit{infotainment} is presented via
several websites specialized per genre or category and some sites attract over
$500.000$ visitors per month.

\section{Information flow}
The reason why Hyperleap is the only in its kind with the high quality data is
because Hyperleap spends a lot of time and resources on quality checking, cross
comparing and consistency checking before the data enters the database. To
achieve this, the data will go through several different stages before it
enters the database. These stages are visualized in
Figure~\ref{informationflow} as an information flow diagram. In this diagram
the nodes are processing steps and the arrows denote information transfer or
flow.

\begin{figure}[H]
        \label{informationflow}
        \centering
        \includegraphics[scale=0.7]{informationflow.eps}
        \strut\\
        \strut\\
        \caption{Information flow Hyperleap database}
\end{figure}

\newpage
\subsection*{Sources}
The information that enters the database has to be quality checked and this
checking starts at the source of the data. There are several criteria the
information from the source have to comply to before it can enter the
database. The prerequisites for a source are for example the fact that the
source has to be reliable, consistent and free by licence. Event information
from a source must have at least the following fields of information.\\
\textbf{What:}\\
The \textit{What} field is the field that describes the content, content is a
very broad definition. In practice it can be describing the concert tour name,
theater show title, movie title, festival title and many more.\\
\textbf{Where:}\\
The \textit{Where} field is the location of the event. The location is often
omitted because the organization behind source presenting the information think
it is obvious. This field can also include different sub locations. For
example when a pop concert venue has their own building but in the summer they
organize a festival in some park. This data is often assumed to be trivial and
inherent but in practice this is not the case. In this example for an outsider
only the name of the park is often not enough.\\
\textbf{When:}\\
The \textit{When} field is the time and date of the event. Hyperleap wants
to have at minimum the date, start time and end time. In the field end
times are often omitted because they are not fixed or the organization
think it is obvious.\\
\strut\\
Venues often present incomplete data entries that do not comply to the
requirements explained before. Within the information flow categorizing and
grading the source is the first step. Hyperleap processes different sources and
source types and every source has different characteristics. Sources can be
modern sources like websites or social media but even today a lot of
information arrives at Hyperleap via flyers, fax or email. As sources vary in
content structure sources also vary in reliability. For example the following
entry is an example of a very well structured and probably generated, and thus
probably also reliable, event description. The entry can originate for example
from the title of an entry in a RSS feed. The example has a clear structure and
almost all information required is available directly from the entry.

\begin{flushleft}
        \texttt{2015-05-20, 18:00-23:00 - \textit{Foobar} presenting their new%
CD in combination with a show. Location: small salon.}
\end{flushleft}

An example of a terrible item could be for example the following text that
could originate from a flyer or social media post. This example lacks a
precise date, time and location and is therefore hard for people to grasp at
first, let alone for a machine. When someone wants to get the full information
he has to tap in different resources which might not always be available. 

\begin{flushleft}
        \texttt{\textit{Foobar} playing to celebrate their CD release in the%
park tomorrow evening.}
\end{flushleft}

\subsection*{Crawler}
When the source has been determined and classified the next step is
periodically crawling the source. At the moment the crawling happens using two
main methods.\\
\textbf{Manual crawling:} Manual crawling is basically letting an employee
access the source and put the information directly in the database. This often
happens with non digital sources and with very sudden events or event changes
such as surprise concerts or event cancellation.\\
\textbf{Automatic crawling:} Some sites are very structured and a programmer
can create a program that can visit the website systematically and
automatically to extract all the new information. Not all digital sources are
suitable to be crawled automatically and will still need manual crawling. The
programmed crawlers are always specifically created for one or a couple sources
and when the source changes for example structure the programmer has to adapt
the crawler which is costly. Information from the all the crawlers goes first
to the \textit{Temporum}.

\subsection*{Temporum}
The \textit{Temporum} is a big bin that contains raw data extracted from
different sources and has to be post processed to be suitable enough for the
actual database. This post-processing encompasses several possible tasks. The
first task is to check the validity of the entry. This is not done for every
entry but random samples are taken and these entries will be tested to see
if the crawler is not malfunctioning and there is no nonsense in the
data. 

The second step is matching the entry to several objects. Objects in the
broadest sense can basically be anything, in the case of a theater show
performance the matched object can be the theater show itself, describing the
show for all locations. In case of a concert it can be that the object is a
tour the band is doing. When the source is a ticket vendor the object is the
venue where the event takes place since the source itself is not a venue.
Many of these tasks are done by a human or with aid of a computer program.
The \textit{Temporum} acts as a safety net because no data is going straight
through to the database. It is first checked, matched and validated.

\subsection*{Database \& Publication}
When the data is post processed it is entered in the final database. The
database contains all the events that happened in the past and all the events
that are going to happen in the future. The database also contains information
about the venues. The database is linked to several categorical websites that
offer the information to users and accompany it with the other part of the
\textit{infotainment} namely the subjectual information that is usually
presented in the form of trivia, photos, interviews, reviews, previews and much
more.

\section{Goal \& Research question}
Crawling the sources and applying the preprocessing is the most expensive task
in the entire information flow because it requires a programmer to perform
these tasks. Programmers are needed because all the crawlers are scripts or
programs that were created specifically for a website. Changing a crawler or
preprocessing job means changing the code.
A big group of sources often changes and that makes that this task
becomes very expensive and has a long feedback loop. When a source changes the
source is first preprocessed in the old way, send to the \textit{Temporum} and
checked by a human and matched. The human then notices the error in the data
and has to contact the programmer. The programmer then has to reprogram the
specific crawler or job to the new structure. This feedback loop, shown in
Figure~\ref{feedbackloop} can take days and can be the reason for gaps and
faulty information in the database. In the figure the dotted arrows denote the
current feedback loop for crawlers.
\begin{figure}[H]
        \label{feedbackloop}
        \centering
        \includegraphics[scale=0.5]{feedbackloop.eps}
        \strut\\\strut\\
        \caption{Feedback loop for malfunctioning crawlers}
\end{figure}

The goal of this project is specifically to relieve the programmer of repairing
crawlers all the time and make the task of adapting, editing and removing
crawlers doable for someone without programming experience. In practice this
means in Figure~\ref{feedbackloop} that the project will remove the replace
part of the feedback loop that contains dotted arrows with the shorter loop
with the dashed arrows.

For this project an application has been developed that can provide an
interface to a crawler generation system that is able to crawl RSS\cite{Rss}
and Atom\cite{Atom} publishing feeds. The interface provides the user with
point and click interfaces meaning that no computer science background is
needed to use the interface and to create, modify, test and remove crawlers.
The current Hyperleap backend system that handles the data can, via an query,
generate XML feeds that contain the crawled data. The structure of the
application is very modular and generic and therefore it is easy to change
things in the program without having to know a lot about the programming
language used. To achieve this all visual things such as buttons are defined in
a human readable text files. In practice it means that one person, not by
definition a programmer, can be instructed to change the structure and this can
also greatly reduce programmer intervention time. 

The actual problem statement then becomes:
\begin{center}
        \textit{Is it possible to shorten the feedback loop for repairing and%
adding crawlers by making a system that can create, add and maintain crawlers%
for RSS feeds}
\end{center}

\section{RSS/Atom}
RSS/Atom feeds, from now on called RSS feeds, are publishing feeds in the XML
format\cite{Xml} that are used to publish events. Every event or entry consists
of several standardized fields. The main data fields are the \textit{title} and
the \textit{description} field. In these fields the raw data is stored that
describes the event. Further there are several auxiliary fields that store the
link to the full article, store the publishing data, store some media in the
form of an image or video URL and store a \textit{Globally Unique
Identifier}(GUID)\footnote{A GUID is a unique identifier that in most cases is
the permalink of the article. A permalink is a link that will point to the
article}. An example of a RSS feed can be found in Listing~\ref{examplerss},
this listing shows a partly truncated RSS feed of a well known venue in the
Netherlands. As visible in the listing the similarities with XML are very
clear. Every RSS feed contains a \texttt{channel} tag and within that tag there
is some metadata and a list op \texttt{item} tags. Every \texttt{item} tag has
a fixed number of different fields. The most important fields for RSS within
the leisure industry are the \texttt{title} and the \texttt{description} field.

\lstinputlisting[language=xml,label={examplerss},caption={An example of a,%
partly truncated RSS feed of a well known dutch venue}]{exrss.xml}

RSS feeds are mostly used by news sites to publish their articles. A RSS feed
only contains the headlines of the entries. If the user, who reads the feed, is
interested it can click the so called deeplink and will be sent to the full
website containing the full entry or article. Users often use programs that
bundle user specified RSS feeds into big combined feeds that can be used to
sift through a lot of news feeds. The RSS feed reader uses the GUID to skip
feeds that are already present in its internal database.

Generating RSS feeds by hand is a tedious task but almost all RSS feeds are
generated by a Content Management Systems(CMS) on which the website runs. With
this automatic method the RSS feeds are generated for the content published
on the website. Because the process is automatic the RSS feeds are generally
very structured and consistent in its structure. In the entertainment industry
venues often use a CMS for their website to allow users with no programming or
website background be able to post news items and event information and thus
should often have RSS feeds.

\section{Why RSS?}
\label{sec:whyrss}
We described a lot of different source formats like HTML, fax/email, RSS and
XML. Because of the limited scope of the project and the time planned for it
we had to remove some of the input formats because they all require different
techniques and approaches to tackle. For example when the input source is in
HTML format, most probably a website, then there can be a great deal of
information extraction be automated using the structural information which is a
characteristic for HTML. For fax/email however there is almost no structural
information and most of the automation techniques require natural language
processing. We chose RSS feeds because RSS feeds lack inherent structural
information but are still very structured. This structure is because, as said
above, the RSS feeds are generated and therefore almost always look the same.
Also, in RSS feeds most venues use particular structural identifiers that are
characters. They separate fields with vertical bars, commas, whitespace and
more non text characters. These field separators and keywords can be hard for
a computer to detect but people are very good in detecting these. With one look
they can identify the characters and keywords and build a pattern in their
head. Another reason we chose RSS is their temporal consistency, RSS feeds are
almost always generated and because of that the structure of the entries is
very unlikely to change. Basically the RSS feeds only change structure when
the CMS that generates it changes the generation algorithm. This property is
useful because the crawlers then do not have to be retrained very often.
To detect the structures we propose a technique using subword matching using
graphs.

\section{Directed Acyclic Graphs}
\paragraph{Directed graphs}
Directed graphs(DG) are a mathematical structure that can describe relations
between nodes. A directed graph $G$ is be defined as the tuple $(V,E)$ where
$V$ is a set of named nodes and $E$ is the set of edges defined by $E\subseteq
V\times V$. An edge $e\in E$ can be seen as $(v1, v2)$ where $v1,v2\in V$ and
can be interpreted as in a figure as an arrow between node $v1$ and node $v2$.
Multiple connections between two nodes are possible. For example the graph
visualized in Figure~\ref{graphexample} can be mathematically described as:
$$G=(\{n1, n2, n3, n4\}, \{(n1, n2), (n2, n1), (n2, n3), (n3, n4), (n1, n4)\}$$

\begin{figure}[H]
        \label{graphexample}
        \centering
        \includegraphics[scale=0.7]{graphexample.eps}
        \strut\\\strut\\
        \caption{Example DG}
\end{figure}

\paragraph{Directed acyclic graphs}
Directed Acyclic Graphs(DAGs) are a special kind of directed graphs. DAGs
are also defined as $G=(V,E)$ but with a restriction on $E$. Namely that cycles
are not allowed. Figure~\ref{dagexample} shows two graphs. The bottom graph
contains a cycle and the right graph does not. Only the top graph is a valid
DAG. A cycle can be defined as follows:

Say $e\in E$ can be seen as $(v_1,v_2)\in E$ or $v_1\rightarrow v2$ then
$v_1\xrightarrow{+}v_2$ is defined as $v_1\rightarrow \ldots
\rightarrow v_2$ meaning that there is a path with a length bigger then $1$
between $v_1$ and $v_2$. In a non cyclic graph the following holds $\nexists
v1: v1\xrightarrow{+}v1$. In words this means that a node can not be reached
again traveling the graph. Adding the property of non cyclicity to graphs
lowers the computational complexity of path existence in the graph to
$\mathcal{O}(L)$ where $L$ is the length of the path.

\begin{figure}[H]
        \label{dagexample}
        \centering
        \includegraphics[scale=0.7]{dagexample.eps}
        \strut\\\strut\\
        \caption{Example DAG}
\end{figure}

\paragraph{Directed Acyclic Word Graphs}
The type of graph used in the project is a special kind of DAG called Directed
Acyclic Word Graphs(DAWGs). A DAWG can be defined by the tuple $G=(V,v_0,E,F)$.
$V$ is the same as in directed graphs, namely the set of nodes. $E$ is the set
of edges described by $E\subseteq V\times V\times L$ where $L\in A$ where $A$
is the alphabet used as node labels. In words this means that an edge is a
labeled arrow between two nodes and for example the edge $(v_1, v_2, a)$ can be
visualized as: $v_1\xrightarrow{a}v_2$. In a standard DAWG the alphabet $A$
contains all the characters used in natural language but in theory the alphabet
$A$ can contain anything. $F$ describes the set of final nodes, final nodes are
nodes that can be the end of a sequence even if there is an arrow leading out.
In the example graph in Figure~\ref{exampledawg} the final nodes are visualized
with a double circle as node shape. In this example it is purely cosmetic
because $n6$ is a final node anyways because there are no arrows leading out.
But this does not need to be the case, for example in $G=(\{n1, n2, n3\},
\{(n1, n2), (n2, n3)\}, \{n2, n3\})$ there is a distinct use for the final node
marking. Graph $G$ accepts the words \textit{a,ab} and to simplify the graph
node $n2$ and $n3$ are final. Finally $v_0$ describes the initial node, this is
visualized in figures as an incoming arrow. Because of the property of labeled
edges, data can be stored in a DAWG. When traversing a DAWG and saving all the
edgelabels one can construct words. Using graph minimalization big sets of
words can be stored using a small amouth of storage because edges can be
re-used to specify transitions. For example the graph in
Figure~\ref{exampledawg} can describe the language $L$ where all words $w$ that
are accepted $w\in\{abd, bad, bae\}$. Testing if a word is present in the DAWG
is the same technique as testing if a node path is present in a normal DAG and
therefore also falls in the computational complexity class of $\mathcal{O}(L)$.
This means that it grows linearly with the length of the word.

\begin{figure}[H]
        \label{exampledawg}
        \centering
        \includegraphics[scale=0.7]{dawgexample.eps}
        \strut\\\strut\\
        \caption{Example DAWG}
\end{figure}