\section{A Stream Based Approach}
Streaming algorithms provide excellent solutions to many problems where data
sets are large enough that we wish (or need) to sacrifice exactness for low
memory usage and time consumption.

\texttt{Ikonomovska et al.(2013)}\citep{ikonomovskazelke}:

"Streaming algorithms drop the demand of random access to the input. Rather, the input
is assumed to arrive in arbitrary order as an input stream. Moreover, streaming algorithms
are designed to settle for a working memory that is much smaller than the size
of the input."

To be precise, they require that the size of the working memory is sublinear in both the cardinality of the stream and the universe.
Due to this nature of streaming algorithms they are not commonly used for
problems that require analysing parts of non-constant, non-parameterized size
of the data set, for each given input. Hence an approach to
solve our problem --- sorting --- based on streaming algorithms will provide some interesting
trade-offs.

The definition of our stream, $S \in (U\times R)^{|S|}$ is the same as the
sequence described in the introduction. With this definition we get a strict
turnstile stream --- in fact the delta $r$ for \textit{every} stream element is
positive.

The simplest algorithm to solve our problem is then simply calculating the
normalized frequency vector for the stream, and sort it when queried.
However, this is not very satisfactory. The working memory is
sublinear in $|S|$, but linear in the universe size $|U|$. It
does not provide a current solution either, as we have to sort the frequency
vector when queried. On the positive side, the solution provided by the
algorithm is exact. To be precise, this algorithm would require $O(m)$ working
memory, and constant time for each stream item, $m$ being the number of distinct movies
in the stream, which we assume to be, or closely approach, $|U|$. A query would then
require $O(m \log m)$ time.

The rest of this section discusses techniques that alleviate these problems
with different trade-offs.

\subsection{Order Maintenance}
\ref{sec:ordermaint}
In the simple algorithm, results were not \textit{current}, because every query
required a sort of the frequency vector --- which is long. If we allow ourselves
to use more than constant processing time per stream element, this problem can
be solved by maintaining an \textit{always sorted} data structure with pointers
into the frequency vector, such as a search tree.
This algorithm is equivalent to maintaining an ordered set of running averages,
and is thus the same as the online-sorting approach described previously.

Knowing that for most stream items $(j,r)$, the movie represented by
$j$ will already be in the ordered set, it might be possible to achieve
insertion time linear in the number of inversions needed to reorder the set,
though it is not clear that this should improve the $\log n$ insertion time in
binary search trees.

In summary, we get $O(\log n)$ processing time for each stream element, but
queries can now be performed in $O(n)$. This a very natural change from the
simple algorithm, that really only moves the required work from the time of
querying, to the time of input.

\subsection{Approximation based on sampling}
In addition to the lack of currency, the simple algorithm requires a lot of
memory. Not surprisingly, streaming algorithms lets us buy a lower memory
requirement, at the cost of exactness.

There seem to be two obvious approaches;
normal reservoir sampling over the stream, or sampling over the
movies, deliberately making sure that all movies are represented in the sample.
The later obviously fails to improve memory consumption, and is only suggested
because taking a random sample over the stream seems dangerous, as it might well
discard movies from the stream, by not picking any of their ratings for the
sample. As it turns out, this is not a big problem.

Although a uniformly random sample of ratings is not an answer to our original
problem, it does have some nice properties.

As stated in
\sloppy{\texttt{Ikonomovska et al.(2013)}\citep{ikonomovskazelke}: 

all $|S| \choose k$ possible
samples, where $k$ is the sample size, are equally likely to be our result. It
follows directly from this that popular ratings for a movie are more likely to
occur than unpopular ones. However, the likelihood of a movie occurring in the
sample similarly correlates to how many ratings it has, not -- as we would want
-- how high it's average rating is. In other words, reservoir sampling gives us
a random set of ratings, with no guarantee that the sample contains good movies.

The common reservoir sampling algorithm described in
\texttt{Ikonomovska et al.(2013)}\citep{ikonomovskazelke}:

remembers $k$ samples $K_0..K_{k}$. After the first $k$, each
stream element \raggedright{$\alpha_i, k < i \leq |S|$}, replaces one of the
$k$ samples with probability $k/i$, choosing the sample to be replaced at
random.

The sampling approach solves our memory issues by parametrizing the memory
consumption. The algorithm uses $O(k)$ memory, independent of both $|U|$ and
$|S|$.

We can modify the reservoir sampling algorithm to keep running averages instead
of samples, modifying samples when observing a stream element that refers to a
movie already being monitored, and only replacing a sample when observing an
element that is not already being monitored (i.e. not currently in the set of
remembered movie samples). We then no longer get sampled ratings, but estimates
of the movie averages --- which is what we wanted. Maintaining running averages
can be thought of as keeping a frequency vector, and changing the stream so that
each element $(j, r)$ becomes $(j, r')$, where $r'$ is the change $r$ imposes on
the kept average for movie $j$. Despite the possibility of $r'$ being negative,
we are still in the strict turnstile model, as the average will never be
negative, regardless of what subset if $S$ we look at. Direct application of
this analogue is infeasible, as it would require $O(|U|)$ memory to keep
track off the counters necessary to calculate $r'$ from $r$. However, it would
be interesting to apply it with estimations of those counters.

The problem of missing movies persists however. If wish achieve the $O(k)$
memory bound, we can not hope to find the exact solution using sampling in this
way. However, if we limit our problem to find the top-l movies, we can.

%As described in \texttt{Ikonomovska et al.(2013)}\citep{ikonomovskazelke}: we can adjust the quality of
%the result by adjusting $k$ as following.

If we alter our running-average sampling to replace the \textit{smallest}
sample, instead picking one at random, the probability of our $k$ samples
containing the top $l<k$ movies increases. \texttt{Metwally et al. (2005)}\citep{efficientstreams}: present an
algorithm based on that idea. The algorithm mixes techniques from sampling and
estimation, to provide both top-k \textit{and} frequent-elements queries, albeit
for frequencies rather than averages.
Metwally et. al.
The \textit{space-saving} algorithm presented in \texttt{Metwally et al. (2005)}\citep{efficientstreams}: works
as follows:
To support the eviction of the smallest sample, as well as the queries on the
algorithm, the \textit{space-saving} algorithm keeps the samples $(U\times
\mathbb{N})^k$ in non-increasing order of frequency. We let $K_i$ denote the
frequency of the $i^{th}$ sample in this order, hence $K_k = \min_j\pi_2(K_j)$.
When a monitored movie is observed, it's counter is incremented. When a
non-monitored movie $j'$ is observed, the movie replaces the $k^{th}$ sample
$(j,K_k))$. Since $j'$ may at at this time have
been observed at most $K_k+1$ times, the new sample is added as $(j',K_k+1)$. This
introduces an element of estimation, trying to make up for increments lost by
previous evictions from the sample-set. For each sample, the maximum
overestimation $\varepsilon_i$ is tracked. $\varepsilon_i = K_k-1$ after the
sample is replaced (equal to $K_k$ before the sample is replaced). The algorithm
cleverly introduces error when the replacement occurs, and is hence more likely
to err on infrequent elements than on frequent ones. I.e. the ones we are least
interested in.

\texttt{Metwally et al. (2005)}\citep{efficientstreams} Proves several theorems that are important for our use
case: \textit{(Adapted to our problem definition. Numbering corresponds to that
of the paper)}
\begin{description}
\item[Metwally Lemma 1] \hfill \\
	The length $|S|$ of the stream is equal to the sum of the sample
	frequencies.
	$|S| = \sum_{i\leq k}K_i$

\item[Metwally Lemma 2] \hfill \\
	$K_k \leq \lfloor \frac{|S|}{k} \rfloor$ 

\item[Metwally Lemma 3] \hfill \\
	For any sample: $0 \leq \varepsilon_i \leq K_k$ i.e $f_i \leq f_i
	+ \varepsilon_i = K_i \leq f_i+K_k$ where $f_i$ is the actual frequency
	of the movie we estimate to have rank $i$.

\item[Metwally Theorem 1] \hfill \\
	Let $F_i$ denote the actual frequency of the movie with actual rank $i$.

	Any movie with $F_i > K_k$ must exist in the sample-set. I.e any movie
	with an actual frequency higher than the lowest estimated frequency in
	the sample, must be in the sample.

\item[Metwally Theorem 2] \hfill \\
	Whether or not the movie with actual rank $i$ occupies the $i^{th}$
	position in $K$, $K_i \geq F_i$

\end{description}

As mentioned, the \textit{space-saving} algorithm is intended for
estimating frequencies, and needs modification to work with averages. A first
thought might be to run two instances in parallel, estimating the count of
ratings and sum of ratings respectively (equivalent to frequencies in the cash
register and turnstile model respectively). This clearly does not work, as the
set of most frequently rated movies is not necessarily similar to the set of
movies with a high sum of ratings. Instead, we can adapt the algorithm to
maintain running averages instead of frequencies. This presents a problem
however. The proofs for the presented lemmas and theorems depend on the fact
fact that each replacement in the sample-set increments the counter by $1$. But
incrementing by $1$ will not provide us with running averages. Hence, keeping
running averages will break the proofs. For this approach to be valuable in our
setting, it remains to provide new error bounds, or modify the algorithm so that
the ones from \texttt{Metwally} holds.

\subsection{Approximation based on Sketching}
\label{sec:sketching}

Sketching lets us sacrifice exactness for lower memory consumption, without
having to worry about loosing entire movies from the solution. We pay for this
with an error bound that is linear in $|S|$.

The count-min sketch algorithm as described in {\texttt{Ikonomovska et al.(2013)}\citep{ikonomovskazelke}
estimates the frequency vector of the stream, using
$O(\log(1/\delta)/\varepsilon + \log n \cdot \log(1/\delta))$ working memory.
Where $\varepsilon$ determines the expected error $\varepsilon \cdot |S| /2$, of
each frequency and $\delta$ is the probability of the actual error exceeding
that bound. The error is guaranteed to be positive i.e. the algorithm cannot
underestimate the actual frequencies. A simple adaption of the algorithm to our
problem (estimating averages, not frequencies) is to run two instances of the
algorithm in parallel, estimating respectively the sum and frequency of ratings
for each movie. We denote the actual sum and frequency for a movie $j$ by $R_j$
and $F_j$, and the estimates produced by the algorithm $\bar{R_j}$ and
$\bar{F_j}$ We can then get an estimate of the average rating for a movie $j$ by
$\bar{R_j}/\bar{C_j}$.
If we use the same set of hashing functions and
vector lengths for sketching $R_j$ and $C_j$, we see that
$R_j-\bar{R_j} \le F_j-\bar{F_j}$. Hence, the resulting error is
positive. This guarantee only holds because our ratings are
defined to be positive. This also shows
$$\frac{R_j}{F_j} \le \frac{\bar{R_j}}{\bar{F_j}} \le \frac{\epsilon_r \cdot
R_j}{\epsilon_f \cdot F_j}$$
Where $\epsilon_f$ is our error bound $\varepsilon \cdot |S|/2$, and
$\epsilon_r$ is $\epsilon_f$ times the maximum rating (10, in our case).

The count-min sketch algorithm can be modified as described in section
\ref{sec:ordermaint}, to provide fast query times as well.
