reqs update

[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{fig:1.1.1}

\begin{figure}[H]
        \caption{Information flow Hyperleap database}
        \label{fig:1.1.1}
        \centering
        \scalebox{0.7}{
                \digraph[]{graph111}{
                        rankdir=TB;
                        node [shape="rectangle",fontsize=10,nodesep=0.5,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 post 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.

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{fig:1.2.1} 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{fig:1.1.2}
        \centering
        \scalebox{0.8}{
                \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{fig:1.1.2} 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\footnote{\url{http://rssboard.org/rss-specification}} and
Atom\footnote{\url{http://tools.ietf.org/html/rfc5023}} 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\footnote{\url{http://www.w3.org/TR/REC-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).

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/Atom}
\label{sec:whyrss}
Information from venues comes in various different format with for each format
several positive and negative points. For this project we chose to focus on
RSS feeds. RSS feeds are, as explained earlier, very structured and consistent
in their structure. The structure basically only changes if the CMS changes or
upgrades. Because of this patterns don't have to be retrained a lot.

In comparison to websites RSS feeds don't have a structural dimension in
the data, all the information in an entry is basically two fields of plain
text. Therefore an entirely new strategy has to be applied to train the
patterns.

\section{Scientific relevance and similar research}
Currently the techniques for conversion from non structured data to structured
data are static and mainly only usable by computer science experts. There is a
great need of data mining in non structured data because the data within
companies and on the internet is piling up and are usually left to catch dust.

The project is a followup project of the past project done by Roelofs et
al.\cite{Roelofs2008} and \cite{Roelofs2009}. Roelofs et al. described
techniques on recognizing patterns in website data and published about an
adapted levenstein distance algorithm to recognize data in isolated text. These
techniques of recognizing data in text can still be used to interpret the
isolated extracted parts from this project.

\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{fig:graphexample} is specified as: 
        $$G=({n1, n2, n3}, {(n1, n2), (n2, n3), (n2, n3)})$$

\begin{figure}[H]
        \caption{Example Graph}
        \label{fig:graphexample}
        \centering
        \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{fig:graphexample} but then the normal edges would be replaced by
directional arrows that specifically go from one node to the other.

\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{fig:dagexample} shows two graphs. The left graph
contains a cycle and the right graph does not. Only the right 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{fig:dagexample}
        \centering
        \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 pair
$G=(V,E)$ and is the same as a directed graph except for the edges. An edge in
a DAWG is instead of a tuple a triple and consist of a starting point, an end
point and a label. 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{fig:2.1.1} 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{fig:2.1.1}
        \centering
        \digraph[]{graph21}{
                rankdir=LR;
                1,2,3,4,5 [shape="circle"];
                6 [shape="doublecircle"];
                1 -> 2 [label="a"];
                2 -> 3 [label="b"];
                3 -> 6 [label="d"];
                1 -> 4 [label="b"];
                4 -> 5 [label="a"];
                5 -> 6 [label="a"];
                5 -> 6 [label="e"];
        }
\end{figure}