1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Feb 14 '19 at 21:02
  • $\begingroup$ @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$. $\endgroup$ – AmeerJ Feb 18 '19 at 13:22
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 18 '19 at 20:10
  • $\begingroup$ @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. $\endgroup$ – AmeerJ Feb 19 '19 at 21:34
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 19 '19 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.