thesis all comments processed

[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 their town 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 pretty hard for the information and you could easily miss a show just
because it didn't cross paths with you. 
Today the internet is used by almost everyone in the westen society on a daily
basis and we would think that missing an event would be impossible because of
the loads of information you receive every day. The opposite is true.

Nowadays information about entertainment is offered via two main channels on
the internet namely individual venues and combined 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. Information bundling websites often have
the individual venue website as the source for their information and therefore
the information is most of the time not complete.
Individual organisations 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.

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 also serve incomplete information.  Because of
the complexity of complete information there are not many websites trying to
bundle entertainment information into a complete and consistent databese.
Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve goal of serving
complete and consistent information.

\section{Hyperleap \& Infotainment}
Hyperleap is a 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
means a combination of factual information and subjectual information
(entertainment) within a certain category. In the case of Hyperleap the
category is the entertainment industry, entertainment industry encompasses all
facets of entertainment going from cinemas, theaters, concerts to swimming
pools, bridge matches and conferences.  Within the entertainment industry
factual information includes, but is not limited to, information such as
starting time, location, host or venue and location. Subjectual information
includes, but is not limited to, things such as reviews, previews, photos and
background information or trivia. 

Hyperleap manages the largest database containing \textit{infotainment} about
the entertainment industry. The database contains over $10.000$ categorized
events per week on average and their venue database contains over $54.000$
venues delivering the entertainment ranging from theaters and music venues to
petting zoos and fastfood restaurants. All the subjectual information is
obtained or created by Hyperleap and all factual information is gathered from
different sources and 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 is inserted in the database in several different stages
that are visualized in Figure~\ref{informationflow} as an information flow
diagram using nodes as processing or publishing steps and arrows are
information flow.

\begin{figure}[H]
        \label{informationflow}
        \centering
        \scalebox{0.7}{
                \digraph[]{graph111}{
                        rankdir=TB;
                        node [shape="rectangle",fontsize=10,nodesep=0.7,ranksep=0.75,width=1];
                        edge [weight=5.];
                        i0 [label="Website"];
                        i1 [label="Email"];
                        i2 [label="Fax"];
                        i3 [label="RSS/Atom"];
                        p1 [label="Preproccessing"];
                        p2 [label="Temporum: Postproccesing"];
                        o1 [label="Database: Insertion"];
                        o2 [label="TheAgenda"];
                        o3 [label="BiosAgenda"];
                        o4 [label="..."];
                        node [width=5]; p1 p2 o1;
                        i0 -> p1;
                        i1 -> p1;
                        i2 -> p1;
                        i3 -> p1;
                        p1 -> p2;
                        p2 -> o1;
                        o1 -> o2;
                        o1 -> o3;
                        o1 -> o4;
                }
        }
        \caption{Information flow Hyperleap database}
\end{figure}

\paragraph{Sources}
The information that enters the database has to be quality checked. There are
several criteria the information and the source have to comply to before any of
them can enter the database. For example the source has to be reliable,
consistent and free by licence whereas the event entries have to have at least
the following fields:
\begin{itemize}
        \item[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.
        \item[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 sublocations.
                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.
        \item[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.
\end{itemize}

Venues often present incomplete data entries that do not comply to the
requirements explained before.

The first step in the information flow is the source. Hyperleap processes
different sources 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 a RSS feed.

\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 entry could be for example the following text that
could originate from a flyer or social media post.

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

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. 

\paragraph{Crawler}
When the source has been determined and classified the next step is
periodically crawling the source. At the moment the crawling happens using a
couple of different methods. Some sites are very structured and a programmer
creates a program that can visit the website systematically and extract that
information.  Some other sources are very hard to programmatically crawled and
they are visited by employees. 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 different crawlers then goes to the \textit{Temporum}.

\paragraph{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 straigt
through to the database. It is first checked, matched and validated.

\paragraph{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 be hired.
Only programmers currently can create crawlers and design preprocessing jobs
because all current programs are specifically designed to do one thing, most of
the time for one source. Because a big group of sources often changes 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 contacts the programmer. The programmer then has to reprogram the specific
crawler 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. 
\begin{figure}[H]
        \label{feedbackloop}
        \centering
        \scalebox{0.5}{
                \digraph[]{graph112}{
                        rankdir=LR;
                        node [shape="rectangle"];
                        source [label="Source"];
                        crawler [label="Crawler"];
                        temporum [label="Temporum"];
                        employee [label="User"];
                        programmer [label="Programmer"];
                        database [label="Database"];
                        source -> crawler;
                        crawler -> temporum;
                        temporum -> user;
                        user -> database;
                        user -> programmer [constraint=false,style="dotted"];
                        user -> crawler [constraint=false,style="dashed"];
                        programmer -> crawler [constraint=false,style="dotted"];
                }
        }
        \caption{Feedback loop for malfunctioning crawlers}
\end{figure}

The goal of the project is 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} removing the dotted arrows by dashed arrow.

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, to create, modify, test and remove crawlers.  The
current Hyperleap backend system that handles the data can, via an interface,
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. This is because for example all visual things like buttons are
defined in a human readable text file.  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. 

\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.

\begin{listing}
        \caption{An example of a, partly truncated RSS feed of a well known dutch
        venue}
        \label{examplerss}
        \xmlcode{exrss.xml}
\end{listing}

RSS feeds are mostly used by news sites to publish their articles, the feed
then only contains the headlines and if the user that is reading the feed is
interested he can click the so called deeplink and he is then sent to the full
website containing the article. Users often use programs that bundle user
specified RSS feeds into big summary 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 usually RSS feeds are
generated by the Content Management Systems(CMS) the website runs on. With this
automatic method the RSS feeds are generated using 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.

\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.  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 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 usefull because the crawlers
then do not have to be retrained very often. Because the non inherent structure
entirely new strategies had to be applied.

\section{Directed Acyclic Graphs}
\paragraph{Directed graphs}
Directed graphs 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}
        \scalebox{0.7}{
                \digraph[]{graphexample}{
                        rankdir=LR;
                        n1->n2;
                        n2->n1;
                        n2->n3;
                        n3->n4;
                        n1->n4;
                }
        }
        \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
ontains 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
        \scalebox{0.7}{
                \digraph[]{dagexample}{
                        rankdir=LR;
                        n01 -> n02;
                        n02 -> n03;
                        n03 -> n01;
                        n11 -> n12;
                        n12 -> n13;
                        n12 -> n14;
                }
        }
        \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
        \scalebox{0.7}{
                \digraph[]{graph21}{
                        rankdir=LR;
                        node [shape="circle"]; n1 n2 n3 n4 n5;
                        n6 [shape="doublecircle"];
                        n [style=invis];
                        n -> n1;
                        n1 -> n2 [label="a"];
                        n2 -> n3 [label="b"];
                        n3 -> n6 [label="d"];
                        n1 -> n4 [label="b"];
                        n4 -> n5 [label="a"];
                        n5 -> n6 [label="d"];
                        n5 -> n6 [label="e"];
                }
        }
        \caption{Example DAWG}
\end{figure}