everything till graphs

[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]
        \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="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;
                }
        }
\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]
        \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"];
                        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"];
                }
        }
\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}
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;
                        node [shape="circle"]; n1 n2 n3 n4 n5;
                        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}