0.4

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

In the early days of the internet information about entertainment was gathered
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. When the internet grew to what it is now we would
think that missing an event is impossible because of the loads of information
that 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. Because the information that is bundled
ofter comes from the individual websites the information is most of the time
not complete. Individual organisations tend to think 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 in a disclaimer or another page.

Combined websites want to bundle this information, for every event they want
all the details and information for an event. This shows to be a hard task
because these websites don't have the resources and time to combine the
different sources to get a good and complete information overview of an event.
Because of this, there are not many websites that bundle entertainment
information so that the entire database is complete and consistent.
Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve this goal.

\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 about a
certain category. In the case of Hyperleap the category is entertainment
industry, entertainment industry encompasses all facets going from cinemas,
theaters, concerts, conferences and so on. The factual information includes
things such as the date, time, host or location. The subjectual information can
be reviews, previews, photos or background information.

Hyperleap manages the largest database containing \textit{infotainment} about
the entertainment industry. The database contains over $10.000$ events per week
on average and their venue database contains over $54.000$ venues delivering
the entertainment. All the subjectual information is gathered or created by
Hyperleap. All subjectual information is gathered from different sources and
quality checked and therefore very reliable. Hyperleap is the only in its kind
that has such high quality information. The \textit{infotainment} is presented
via several websites specialized per genre or category.

\section{Information flow}
As said before Hyperleap is the only in its kind with the high quality data.
This is because a lot of time and resources are spend to crosscompare, match
and check the data that enters the database. To achieve this the data is
inserted in the database in several different steps described in
Figure~\ref{informationflow}

\begin{figure}[H]
        \caption{Information flow Hyperleap database}
        \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="Crawler: Preproccessing"]
                        p2 [label="Temporum: Postproccesing"]
                        o1 [label="Database: Insertion"]
                        o2 [label="TheAgenda"]
                        o3 [label="BiosAgenda"]
                        o4 [label="..."]
                        p1, p2, o1 [width=5];
                        i0 -> p1
                        i1 -> p1
                        i2 -> p1
                        i3 -> p1
                        p1 -> p2
                        p2 -> o1
                        o1 -> o2
                        o1 -> o3
                        o1 -> o4
                }
        }
\end{figure}

\paragraph{Sources}
The information that enters the database has to be quality checked. There are
several criteria the information has to comply to before it can enter in the
database. Hyperleap wants at minimum the following fields filled before any
event can enter the database:
\begin{itemize}
        \item[What]
                The \textit{What:} field is the field that states the content, content is a
                very broad definition. In practice it can contain the concert tour, theater
                show name, movie title, festival title and many more.
        \item[Where]
                The \textit{Where:} field is the location of the event. This is ofter
                omitted because the organization 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}
The second steps is the crawling of the websites. This happens currently in a
couple of 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 processing encompasses several possible tasks.  The first
task is to check the validity of the entry. This is a very shallow test to
check if the crawler is not malfunctioning and there is no nonsense in the
data. Most of the data is not directly checked for validity, the data is
skimmed for strange things but not every datapoint is checked.  The second step
is matching the entry to several objects. For example the entry has to be
matched to a certain venue when its source is a ticket vendor who sells tickets
for multiple venues. Another example is that the event is a pop concert and is
part of a big tour. Many of these tasks are done alone by or with aid of a
computer program. Almost no data is going straight through the
\textit{Temporum} and this property makes the \textit{Temporum} a safety net
for all the incoming data.

\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}
The second step in the information flow is crawling the sources and apply the
preprocessing. This is a expensive task because it requires a programmer to be
hired because currently all crawlers are programmed for one, or a couple,
specific sources. Because a big group of sources often changes this very
expensive and has a long feedback loop. When a source changes it 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 or faulty information in the database. 
\begin{figure}[H]
        \caption{Feedback loop for malfunctioning crawlers}
        \label{feedbackloop}
        \centering
        \scalebox{0.5}{
                \digraph[]{graph112}{
                        rankdir=LR;
                        node [shape="rectangle"]
                        source [label="Source"]
                        crawler [label="Crawler"]
                        temporum [label="Temporum"]
                        user [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"]
                }
        }
\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 system that is able to crawl RSS\cite{Rss} and
Atom\cite{Atom} publishing feeds.  The interface also provides the user with
point and click interfaces to create, modify, test and remove crawlers. The
Hyperleap back end can, via this interface, generate XML feeds that contain the
crawled data. For editing the structure and contents of the program a
programmer is in theory also not necessary because all the things someone wants
to change are located in a single file that is human readable. 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}

The 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}
The first proposal described formats like HTML, fax/email, RSS, XML and some
more. Because of the 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{Normal graphs}
A graph($G$) is a mathematical structure to describe relations between nodes
with edges. A standard graph is defined as the ordered pair: $G=(V,E)$.  In
this ordered pair $V$ is the set of nodes and $E$ is set of undirected edges
where every undirected edge is a tuple of two nodes.
Figure~\ref{graphexample} is specified as: 
        $$G=(\{n1, n2, n3\}, \{(n1, n2), (n2, n3), (n2, n3)\})$$

\begin{figure}[H]
        \caption{Example Graph}
        \label{graphexample}
        \centering
        \scalebox{0.7}{
                \digraph[]{graphexample}{
                        rankdir=LR
                        n1 -> n2 [dir="none"]
                        n2 -> n3 [dir="none"]
                        n2 -> n3 [dir="none"]
                }
        }
\end{figure}

\paragraph{Directed graphs}
Directed graphs are special kind of graphs. A directed graph $G$ is also
defined by the ordered pair: $G=(V,E)$. $V$ still defines the nodes and $E$
still the edges but the inherent difference is that the edges are ordered
tuples in stead of not ordered. Adding this property gives the edges a
direction. Every edge has a specific start and end and are therefore called
directed edges. A directed graph would look the same as the graph in
Figure~\ref{graphexample} but then visualized with arrows instead of normal
lines. The arrows specifically go from one node to the other and not the other
way around. However bidirectional connection can occur. For example graph the
graph shown in Figure~\ref{dgexample} is directional with a bidirectional
connection.
$$G=(\{n1, n2\}, \{(n1, n2), (n2, n1)\}$$

\begin{figure}[H]
        \caption{Example directed graph}
        \label{dgexample}
        \centering
        \scalebox{0.7}{
                \digraph[]{dgexample}{
                        rankdir=LR
                        n1 -> n2
                        n2 -> n1
                }
        }
\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 is defined by a sequence of edges where nodes are visited more
then once. Adding the property of non-cyclicity to graphs lowers the
computational complexity of checking if a node sequence is present in the
graph to $\mathcal{O}(L)$ where $L$ is the length of the sequence.

\begin{figure}[H]
        \caption{Example DAG}
        \label{dagexample}
        \centering
        \scalebox{0.7}{
                \digraph[]{dagexample}{
                        rankdir=LR
                        n01 -> n02
                        n02 -> n03
                        n03 -> n01
                        n11 -> n12
                        n12 -> n13
                        n12 -> n14
                }
        }
\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 ordered
triple $G=(V,E,F)$.
$V$ is the same as in directed graphs. $E$ is also the same besides the fact
that the ordered pair of nodes that describes the edge it now is a triple
consisting of a start node, an end node and a label. In a standard DAWG the
label is always one character. $F$ describes the set of final nodes, final
nodes are nodes that can be the end of a sequence even if another arrow leads
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 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. 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. Because of properties of graphs a DAWG can store big sets of
words in a small amount of storage because it can re-use edges to specify
transitions. For example the graph in Figure~\ref{exampledawg} can describe a
dictionary that holds the words: \textit{abd, bad, bae}. Testing if a word is
present in the DAWG is, just as for a DAG, falls in the computational
complexity class of $\mathcal{O}(L)$ meaning that it grows linearly with the
length of the word.

\begin{figure}[H]
        \caption{Example DAWG}
        \label{exampledawg}
        \centering
        \scalebox{0.7}{
                \digraph[]{graph21}{
                        rankdir=LR;
                        n1,n2,n3,n4,n5 [shape="circle"];
                        n6 [shape="doublecircle"];
                        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"];
                }
        }
\end{figure}