final

[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?

In the early days of the internet, access to the web was not available for most
of the people. Information about leisure activities was almost exclusively
obtained from flyers, posters and other written media and radio/TV
advertisements. People had to put effort in searching for information and it
was easy to miss a show just because you did not cross paths with it. Today the
internet is used on a daily basis by almost everyone in the western society and
one would think that missing an event would be impossible because of the
enormous loads of information you can receive every day using the internet.
For leisure activities the opposite is true, complete and reliable information
about events is still hard to find.

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 other gimmicks. Information bundling websites are run
by companies that try to provide an overview of multiple venues. Information
bundling websites often have individual venue websites as their source for
information. Individual venues assume, 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. Because of the less structured way of providing information the
information bundling websites have a hard time finding complete information.
The event data can be crawled using automated crawlers but the miscellaneous
information usually has to be crawled by hand.

Combining the information from the different data source turns out to be a
complicated task for information bundling websites. The task is difficult
because the companies behind these 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 companies trying to bundle entertainment
information into a complete and consistent database and website.
Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve the goal of
serving complete and consistent information and offers it via various
information bundling websites.
\newpage
\section{Hyperleap \& Infotainment}
Hyperleap is an internet company that was founded 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, the \textit{information} part,
and non factual information or subjectual information, the
\textit{entertainment} part, within a certain category or field. In the case of
Hyperleap the category is the leisure industry, leisure industry encompasses
all facets of entertainment ranging from cinemas, theaters, concerts to
swimming pools, bridge competitions and conferences. Within the entertainment
industry factual information includes, but is not limited to, starting time,
location, host or venue and duration.  Subjectual information includes, but is
not limited to, reviews, previews, photos, background information and trivia.

Hyperleap says to manage 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 each month.

\section{Information flow}
Hyperleap can keep up the high quality data by investing a lot of time and
resources in quality checking, cross comparing and consistency checking. By
doing so the chances of incomplete or wrong data are much lower.
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]
        \centering
        \includegraphics[width=\linewidth]{informationflow.pdf}
        \caption{Information flow Hyperleap database\label{informationflow}}
\end{figure}

\subsection{Sources}
A source is a service, location or medium in which information about events is
stored or published. A source can have different source shapes such as HTML,
email, flyer, RSS and so on. All information gathered from a source has to be
quality checked before it is even considered for automated crawling. There are
several criteria to which the source has to comply before an automated crawler
can be made. 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 \textit{What, Where} and \textit{When}
information.

The \textit{What} information is the information that describes the content,
content is a very broad definition but in practice it can be describing the
concert tour name, theater show title, movie title, festival title and many
more.

The \textit{Where} information is the location of the event. The location is
often omitted because the organization presenting the information thinks it is
obvious. This information 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.

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 for
example 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 source types 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 low quality 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}

Information with such a low quality is often not suitable for automated
crawling. In Figure~\ref{informationflow} this manual route is shown by the
arrow going straight from the source to the database. Non digital source types
or very sudden changes such as surprise concerts or cancellations are also
manually crawled.

\subsection{Crawler}
When the source has been determined and classified the next step is
periodically crawling the source using an automated crawler. As said before
sources have to be structured and reliable, when this is the case a programmer
will create a program that will visit the website systematically and
automatically to extract all the new information. The programmed crawlers are
usually specifically created for one or more sources and when the source
changes, the programmer has to adapt the crawler. Such a change is usually a
change in structure. Since writing and adapting requires a programmer the
process is costly. Automatically crawled information is not inserted into the
database directly because the information is not reliable enough. In case of a
change in the source malformed data can pass through. As a safety net and final
check the information first goes to the \textit{Temporum} before it will be
entered in the database.

\subsection{Temporum}
The \textit{Temporum} is a big bin that contains raw data extracted from
different sources using automated crawlers. Some of the information in the
\textit{Temporum} might not be suitable for the final database and therefore
has to be post processed. The post-processing encompasses several different
steps.

The first step is to check the validity of the event entries from a certain
source. Validity checking is useful to detect outdated automated crawlers
before the data can leak into the database. Crawlers become outdated when a
source changes and the crawler can not crawl the website using the original
method. Validity checking happens at random on certain event entries.

An event entry usually contains one occurrence of an event. In a lot of cases
there is parent information that the event entry is part of. For example in the
case of a concert tour the parent information is the concert tour and the event
entry is a certain performance. The second step in post processing is matching
the event entries to possible parent information. This parent information can
be a venue, a tour, a showing, a tournament and much more.

Both of the post processing tasks are done by people with the aid of automated
functionality. Within the two post processing steps malformed data can be
spotted very fast and the \textit{Temporum} thus acts as a safety net to keep
the probability of malformed data leaking into the database as low as possible.

\subsection{Database \& Publication}
Postprocessed data that leaves the \textit{Temporum} will enter the final
database. This database contains all the information about all the events that
happened in the past and the events that will happen in the future. The
database also contains the parent information such as information about venues.
Several categorical websites use the database to offer the information to users
and accompany it with the second part of \textit{infotainment} namely the
subjectual information. The \textit{entertainment} part will usually be
presented in the form of trivia, photos, interviews, reviews, previews and much
more.

\section{Goal \& Research question}
Maintaining the automated crawlers and the infrastructure that provides the
\textit{Temporum} and its matching aid automation are the parts within the
data flow that require the most amount of resources. Both of these parts require
a programmer to execute and therefore are costly. In the case of the automated
crawlers it requires a programmer because the crawlers are scripts or programs
are specifically designed for a particular website. Changing such a script or
program requires knowledge about the source, the programming framework and
about the \textit{Temporum}. In practice both of the tasks mean changing code.

A large group of sources often change in structure. Because of such changes
the task of reprogramming crawlers has to be repeated a lot. The detection of
malfunctioning crawlers happens in the \textit{Temporum} and not in an earlier
stage. Late detection elongates the feedback loop because there is not always a
tight communication between the programmers and the \textit{Temporum} workers.
In the case of a malfunction the source is first crawled. Most likely the
malformed data will get processed and will produce rubbish that is sent to the
\textit{Temporum}. Within the \textit{Temporum} after a while the error is
detected and the programmers have to be contacted. Finally the crawler will be
adapted to the new structure and will produce good data again. This feedback
loop, shown in Figure~\ref{feedbackloop}, can take days and can be the reason
for gaps and faulty information in the database. The figure shows information
flow with arrows. The solid and dotted lines form the current feedback loop.
\begin{figure}[H]
        \centering
        \includegraphics[width=0.8\linewidth]{feedbackloop.pdf}
        \caption{Feedback loop for malfunctioning crawlers\label{feedbackloop}}
\end{figure}

The specific goal of this project is to relieve the programmer of spending a
lot of time repairing
crawlers and make the task of adapting, editing and removing
crawlers feasible for someone without programming experience. In practice this
means shortening the feedback loop. The shorter feedback loop is also shown in
Figure~\ref{feedbackloop}. The dashed line shows the shorter feedback loop that
relieves the programmer.

For this project a system has been developed that provides 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 query XML feeds
that contain the crawled data.

The actual research question can then be formulated as:
\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. Such feeds
publish their data in a restricted XML format\cite{Xml} consisting of entries.
Every entry usually represents an event and consists of standardized data
fields. The data fields we are interested in are the \textit{title} and the
\textit{description} fields. Those fields store the raw data which describes
the event. Besides the fields we are interested in there are there are several
auxiliary fields that for example store the link to the full article, store the
publishing data, store some media in the form of an image or video URL or 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. Every RSS feed contains a \texttt{channel}
field and within that field there is some metadata and a list op \texttt{item}
fields. Every \texttt{item} field 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 unique 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}
There are lots 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 and possibly OCR. 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 underlying structures a
technique is used that exploits subword matching with graphs.

\section{Directed Acyclic Graphs}
\paragraph{Directed graphs}
Directed graphs(DG) are mathematical structures 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$ is defined as $(v1, v2)$ where $v1,v2\in V$ and is
show in the figure as an arrow between node $v1$ and node $v2$. Multiple
connections between two nodes are possible if the directions differ. 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]
        \centering
        \includegraphics[scale=0.7]{graphexample.pdf}
        \caption{Example DG\label{graphexample}}
\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:

If $e\in E$ is defined as $(v_1,v_n)\in E$ or $v_1\rightarrow v_n$ then
$v_1\xrightarrow{+}v_n$ which means $v_1\rightarrow v_2 \rightarrow \ldots
\rightarrow v_{n-1} \rightarrow v_n$ meaning that there is a connection with a
length larger then $1$ between $v_1$ and $v_2$.  In a non cyclic graph the
following holds $\nexists v\in V: v\xrightarrow{+}v$. 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]
        \centering
        \includegraphics[scale=0.7]{dagexample.pdf}
        \caption{Example DAG\label{dagexample}}
\end{figure}

\newpage
\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. The only final node is the example is $n_6$, marked with a
double circle. $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 edge labels one can
construct words. Using graph minimisation big sets of words can be stored using
a small amount 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]
        \centering
        \includegraphics[scale=0.7]{dawgexample.pdf}
        \caption{Example DAWG\label{exampledawg}}
\end{figure}

\section{Structure}
The following chapters will describe the system that has been created and the
used methods. Chapter~2 shows the requirements design for the program followed
in Chapter~3 by the underlying methods used for the actual matching. Finally
Chapter~4 concludes with the results, discussion and future research.