<commit_before>\documentclass[a4paper, titlepage]{report}

\usepackage[utf8]{inputenc}
\usepackage{courier} % Required for the courier font
\usepackage[bookmarks]{hyperref}
\usepackage{amsfonts}

%redefine percentage sign to be a little smaller
\let\oldpct\%
\renewcommand{\%}{\scalebox{.9}{\oldpct}}
\begin{document}

\title{SAD2 exam report}
\author{
	<NAME>
	\\\texttt{<EMAIL>}
	\and
	<NAME>
	\\\texttt{<EMAIL>}
}

\maketitle

%\tableofcontents
\section*{Introduction}
Ranking has become an increasingly important problem, with ever-growing datasets
both in the industry and in academia. In the 21. century gathering large data
sets is no longer considered novel. More and more people are getting access to
the internet and more content like films, music is created and evaluated by
them.
Ranking provides what might be the simplest type of recommendation system:
recommend the items that score best on a global total ranking, independently of
the recipient of the recommendation.

In this project, we analyze different approaches to keeping a ranked data set,
while receiving live updates to the data. We choose algorithms to analyze based
on factors like: time and space requirements, and the quality of the solutions
in case of approximation algorithms.

\section*{Ordering movie ratings in a dynamic setting}
To motivate our approach, we present our project through the following concrete
problem: An \texttt{IMDB} like service maintains a list of movies, and lets
users rank movies on some scale (say $\left[1,10\right]\cap \mathbb{N}$). We
want to provide the set of movies, sorted by user-supplied ratings. It is likely
that ratings of individual movies will span a large portion of the valid range, with
some movies getting a few maximum ratings, but a low overall score. It is
therefore necessary to use an aggregate for the ranking, such as the average
user-rating for each movie. For simplicity, we assume that ratings cannot be
changed or deleted, only added. This makes it possible to maintain running
averages, as
opposed to the full set of ratings, without integrity loss

If ratings are added frequently, we can consider the input --- the set of
$(user, rating, movie)$ triplets --- to be \textit{dynamic}. The input is dynamic
in the sense that the \textit{true} global ranking may change over time, with
every added user-supplied rating.
In a static setting, where the global rank does not evolve over time, there are
simple algorithms that solve our problem. E.g. sorting the full data set would
do.
In a dynamic setting, were the data evolves over time,
those algorithms would need to be re-run to maintain current solutions (as the
underlying input changes, so does the global ranking, and hence the correct
solution). Hence, there may be better algorithms that maintain and evolve the
solution according to the input.

We will start by analyzing the most direct approach of maintaining a binary
tree of the movies, updating it with each rating in the input.
We will then explore different algorithms in light of the trade-offs between
memory consumption, correctness, and currency. In particular it should be
possible to achieve a memory bound lower than $m$ by sacrificing correctness,
achieve both by sacrificing currency, i.e. allowing the output to become
somewhat outdated as the underlying data set evolves. We note that in our
\texttt{IMDB} like scenario, the running time of getting a total ordering is
irrelevant. The running time per rating is all that matters, though they will
often be closely related.

Following is a list of techniques that we deemed promising at the project
outset, and hence wished explore the effectiveness of with respect to our
problem:

\begin{description}
	\item[Parallelization] The use of parallelized sorting algorithms, such
		as parallelized merge- or radix- sort. Parallization in algorithms is very
		natural for sorting/selection. But it is still very overlooked. It might be
		a challening to see the real impact of this - because we are affecting the
		overall time consmuption by using it. Moreover usally we are adding more<commit_msg>draft of basic approach<commit_after>\documentclass[a4paper, titlepage]{report}

\usepackage[utf8]{inputenc}
\usepackage{courier} % Required for the courier font
\usepackage[bookmarks]{hyperref}
\usepackage{amsfonts}

%redefine percentage sign to be a little smaller
\let\oldpct\%
\renewcommand{\%}{\scalebox{.9}{\oldpct}}
\begin{document}

\title{SAD2 exam report}
\author{
	<NAME>
	\\\texttt{<EMAIL>}
	\and
	<NAME>
	\\\texttt{<EMAIL>}
}

\maketitle

%\tableofcontents
\section*{Introduction}
Ranking has become an increasingly important problem, with ever-growing datasets
both in the industry and in academia. In the 21. century gathering large data
sets is no longer considered novel. More and more people are getting access to
the internet and more content like films, music is created and evaluated by
them.
Ranking provides what might be the simplest type of recommendation system:
recommend the items that score best on a global total ranking, independently of
the recipient of the recommendation.

In this project, we analyze different approaches to keeping a ranked data set,
while receiving live updates to the data. We choose algorithms to analyze based
on factors like: time and space requirements, and the quality of the solutions
in case of approximation algorithms.

\section*{Ordering movie ratings in a dynamic setting}
To motivate our approach, we present our project through the following concrete
problem: An \texttt{IMDB} like service maintains a list of movies, and lets
users rank movies on some scale (say $\left[1,10\right]\cap \mathbb{N}$). We
want to provide the set of movies, sorted by user-supplied ratings. It is likely
that ratings of individual movies will span a large portion of the valid range, with
some movies getting a few maximum ratings, but a low overall score. It is
therefore necessary to use an aggregate for the ranking, such as the average
user-rating for each movie. For simplicity, we assume that ratings cannot be
changed or deleted, only added. This makes it possible to maintain running
averages, as
opposed to the full set of ratings, without integrity loss

If ratings are added frequently, we can consider the input --- the set of
$(user, rating, movie)$ triplets --- to be \textit{dynamic}. The input is dynamic
in the sense that the \textit{true} global ranking may change over time, with
every added user-supplied rating.
In a static setting, where the global rank does not evolve over time, there are
simple algorithms that solve our problem. E.g. sorting the full data set would
do.
In a dynamic setting, were the data evolves over time,
those algorithms would need to be re-run to maintain current solutions (as the
underlying input changes, so does the global ranking, and hence the correct
solution). Hence, there may be better algorithms that maintain and evolve the
solution according to the input.

We will start by analyzing the most direct approach of maintaining a binary
tree of the movies, updating it with each rating in the input.
We will then explore different algorithms in light of the trade-offs between
memory consumption, correctness, and currency. In particular it should be
possible to achieve a memory bound lower than $m$ by sacrificing correctness,
achieve both by sacrificing currency, i.e. allowing the output to become
somewhat outdated as the underlying data set evolves. We note that in our
\texttt{IMDB} like scenario, the running time of getting a total ordering is
irrelevant. The running time per rating is all that matters, though they will
often be closely related.

Following is a list of techniques that we deemed promising at the project
outset, and hence wished explore the effectiveness of with respect to our
problem:

\section*{General approach}
One of the basic and also efficient concepts is using a data structure which
will provide mechanism for extracting interesting data efficiently. 
Natural choice is a heap, more precisely Min-Max Heap. 
It is provides properties of regular heap like a: 
- O(n) built time,
- O(log(n)) for insertion and deletion

But even more important are properties carried by Min-Max variation. Which are 
guaranteeing us a constant time for Min and Max operations.
The Top/Low(k) finding operation can be performed in O(k*log(k)) time.

Using this approach requires to store all input elements. It takes o(n) for 
large sets. 


\begin{description}
	\item[Parallelization] The use of parallelized sorting algorithms, such
		as parallelized merge- or radix- sort. Parallization in algorithms is very
		natural for sorting/selection. But it is still very overlooked. It might be
		a challening to see the real impact of this - because we are affecting the
		overall time consmuption by using it. Moreover usally we are adding more
{'fraction_non_alphanumeric': 0.05116069416272256, 'fraction_numerical': 0.002028397565922921, 'mean_word_length': 4.645674300254453, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2671039', 'n_tokens_mistral': 2228, 'n_tokens_neox': 2131, 'n_words': 1321}