<p>Suppose we have a string stream over alphabet <span class="math-container">$[n]$</span>. At each step, we would like to compute a sketch of the last <span class="math-container">$k$</span> elements, such that from the sketch we can approximate their relative order. For simplicity, we can assume that the previous <span class="math-container">$k$</span> elements are unique. Moreover, we want the time complexity of the sketch to logarithmically depend on <span class="math-container">$n$</span> and sublinearly on <span class="math-container">$k$</span>. (with linear dependency on <span class="math-container">$k$</span> means we can just compute and store the ranks) </p>

<p>More formally, let <span class="math-container">$s_1, s_2, ...$</span> be the stream of integers <span class="math-container">$s_i\in[n]$</span>. At time step <span class="math-container">$t$</span> we want to sketch order statistics of <span class="math-container">$S_t:=[s_{t-k+1},...,s_{t-1},s_{t}]$</span>. Because the elmenets are unique we can uniquely view them through their rank <span class="math-container">$[r_1,...r_k]$</span> such that <span class="math-container">$r_i\in[k]$</span> is the rank of element <span class="math-container">$s_i$</span> in <span class="math-container">$S_t$</span>. Now let <span class="math-container">$\tilde{S}$</span> be the sketch of <span class="math-container">$S$</span> which we use to recover approximate rank vector <span class="math-container">$[\tilde{r}_1,...\tilde{r}_k]$</span>. Let <span class="math-container">$\sum_{r_i&lt;r_j} 1_{\{\tilde{r}_i&gt;\tilde{r}_j\}}$</span> be the error function, which counts pairs that their order is reversed. There are other ways to measure sketching error, namely <span class="math-container">$\sum_i |r_i-\tilde{r}_i|$</span>. As long as an error function captures how close two rank vectors are it is acceptable. </p>

<p>What is the lowest sketching error (average or worst case) we can achieve while maintaining complexity constraints on <span class="math-container">$n$</span> and <span class="math-container">$k$</span>? Ideally, the method would demonstrate a trade-off between the error and dependency on <span class="math-container">$k$</span>. 
Is there any link between this problem and <a href="https://ac.els-cdn.com/S0022000097915452/1-s2.0-S0022000097915452-main.pdf?_tid=4e8c843a-9e30-45ed-92ec-bb335ed1e5db&amp;acdnat=1550159642_8d9bd21e0df7e5493b2003ce1955c10e" rel="nofollow noreferrer">frequency moment sketching</a>? </p>

CC BY-SA 4.0
2019-02-14T21:02:10.607Z
Do you have any space requirements?  When you say "the time complexity", do you mean the time to process the entire stream of k elements, or the time per element?
D.W.
CC BY-SA 4.0
2019-02-18T13:22:16.857Z
@D.W. perhaps I should have clarified that. There is no space requirement for the program  to run (how much space it needs to compute the sketch) but the sketch itself should also satisfy the same requirements. Example: we sort the last k-elements and store $\sum_{i<j} 1_{r_i<_j}$, which only needs $2\log n$ bits. But sorting requires $n$ additional space. This would be a valid sketch since the stored quantity is a polylog function fo $k$ and $n$.
AmeerJ
CC BY-SA 4.0
2019-02-18T20:10:01.747Z
Can I call your attention again to my question about time complexity?  When you say "time complexity" in the first paragraph, do you mean the time per element, or the time to process all elements?  Neither one makes sense.  There are $k$ elements, so the total time to process all elements must be at least $k$; it can't be sublinear in $k$, so I presume you must not mean the time to process all elements.  However, if you mean the time spent per element, it seems trivial to achieve that running time: sorting all $k$ elements can be done with $O(\log k)$ time per element.  So what do you mean?
D.W.
CC BY-SA 4.0
2019-02-19T21:34:09.940Z
@D.W. Ah, I see where the confusion comes from.  The time complexity I was referring to is for processing every element of the stream that comes in. Suppose we just want to know the sum of previous $k$ elements and store them in $P$. Then we only need to do the update $P \leftarrow P + s_t - s_{t-k}$ which only requires $O(1)$ operations. You can also view it as an amortized cost for each update. Now my question is if a relatively cheap update and sketch are possible for the order of the last $k$ elements.
AmeerJ
CC BY-SA 4.0
2019-02-19T22:25:46.523Z
Can you please edit the question to state these aspects of the problem statement more clearly, so that people don't need to read the comments to understand your question?  Also, as I mentioned before, if you mean $o(k)$ (amortized) time per element, there is a natural solution listed in my last comment; is there some problem with that solution?  Or had you just not considered that possibility?
D.W.
<data-streams>
Sketching order statistics of a stream
AmeerJ
# Sketching order statistics of a stream

(Asked by: username_0 on 2019-02-14)

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\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](https://ac.els-cdn.com/S0022000097915452/1-s2.0-S0022000097915452-main.pdf?_tid=4e8c843a-9e30-45ed-92ec-bb335ed1e5db&acdnat=1550159642_8d9bd21e0df7e5493b2003ce1955c10e)?

**Tags:** data-streams
> **Comments:**
> **username_1**: Do you have any space requirements?  When you say "the time complexity", do you mean the time to process the entire stream of k elements, or the time per element?  
> **username_0**: @D.W. perhaps I should have clarified that. There is no space requirement for the program  to run (how much space it needs to compute the sketch) but the sketch itself should also satisfy the same requirements. Example: we sort the last k-elements and store $\sum_{i<j} 1_{r_i<_j}$, which only needs $2\log n$ bits. But sorting requires $n$ additional space. This would be a valid sketch since the stored quantity is a polylog function fo $k$ and $n$.  
> **username_1**: Can I call your attention again to my question about time complexity?  When you say "time complexity" in the first paragraph, do you mean the time per element, or the time to process all elements?  Neither one makes sense.  There are $k$ elements, so the total time to process all elements must be at least $k$; it can't be sublinear in $k$, so I presume you must not mean the time to process all elements.  However, if you mean the time spent per element, it seems trivial to achieve that running time: sorting all $k$ elements can be done with $O(\log k)$ time per element.  So what do you mean?  
> **username_0**: @D.W. Ah, I see where the confusion comes from.  The time complexity I was referring to is for processing every element of the stream that comes in. Suppose we just want to know the sum of previous $k$ elements and store them in $P$. Then we only need to do the update $P \leftarrow P + s_t - s_{t-k}$ which only requires $O(1)$ operations. You can also view it as an amortized cost for each update. Now my question is if a relatively cheap update and sketch are possible for the order of the last $k$ elements.  
> **username_1**: Can you please edit the question to state these aspects of the problem statement more clearly, so that people don't need to read the comments to understand your question?  Also, as I mentioned before, if you mean $o(k)$ (amortized) time per element, there is a natural solution listed in my last comment; is there some problem with that solution?  Or had you just not considered that possibility?  

---

## 0 answers

