Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For simplicity, we can assume that the previous $k$ elements are unique. Moreover, we want the time complexity of the sketch to logarithmically depend on $n$ and sublinearly on $k$. (with linear dependency on $k$ means we can just compute and store the ranks)
More formally, let $s_1, s_2, ...$ be the stream of integers $s_i\in[n]$. At time step $t$ we want to sketch order statistics of $S_t:=[s_{t-k+1},...,s_{t-1},s_{t}]$. Because the elmenets are unique we can uniquely view them through their rank $[r_1,...r_k]$ such that $r_i\in[k]$ is the rank of element $s_i$ in $S_t$. Now let $\tilde{S}$ be the sketch of $S$ which we use to recover approximate rank vector $[\tilde{r}_1,...\tilde{r}_k]$. Let $\sum_{r_i<r_j} 1_{\{\tilde{r}_i>\tilde{r}_j\}}$ be the error function, which counts pairs that their order is reversed. There are other ways to measure sketching error, namely $\sum_i |r_i-\tilde{r}_i|$. As long as an error function captures how close two rank vectors are it is acceptable.
What is the lowest sketching error (average or worst case) we can achieve while maintaining complexity constraints on $n$ and $k$? Ideally, the method would demonstrate a trade-off between the error and dependency on $k$. Is there any link between this problem and frequency moment sketching?
