2
$\begingroup$

I am reading the paper Space-Efficient Online Computation of Quantile Summaries and get really stuck trying to understand Lemma 3 onwards.

I am sorry it sounds like a lot of questions - this just outline my confusion throughout the proof - you don't have to answer these, an explanation of how the proof actually work would suffice. Even a good link to someone else who explained the proof would work too.

  • Lemma 3 starts with $ m_{min} = \frac{\cdots}{2\epsilon} $, but since $ m_{min} $ is a time and must be an integer, maybe the authors mean the floor or the ceiling?

  • In the definition of $ V_j $, the author defined it as the "rightmost" node. But in the definition of the tree in section 2.1, we only mentioned parent child relationship?

  • In what sense the $ \frac{2\epsilon}{3} $ observations arrived after $ m_{min} $ uniquely maps to the $ (V_i, V_j) $ pair? Isn't $ V_j $ uniquely defined by $ V_i $?

  • Even when we have a 1:1 map between this set of observations maps to the pairs, how does that follow we have $ \frac{3}{2\epsilon} $ parents?

  • Since I don't know what is rightmost, I assumed that $ V_j $ is the child of $ V_i $ with largest $ j $. Now if $ V_k $ exists, it's band must be less than that of $ V_i $ (or else it would be the parent of $ V_j $), but then it must be a descendant of $ V_i $, meaning $ V_j $ is not the rightmost, this is just contradictory, meaning rightmost doesn't mean the one with largest $ j $.

  • At the bottom of the left column, the author mentioned "The observations counted above by $ (V_j, V_i) $ ... What exactly do we mean by a pair counting some observations?

This is a paper written in 2001, presumably a lot of other people also read it. With some search, I found Steven Engelhardt's blog mentioned that the paper is inaccurate and somehow we need to subtract 1 with $ \Delta_i $, so maybe there is a list of errata somewhere? I couldn't find it.

I attempted to think through myself, and I tried to look for explanations. Unfortunately, it is very hard for me to find explanation of the proof, most authors (e.g. here and there) just choose to skip it.

I will also email the authors about this.

Sharing some of my reading notes here, hope it helps.

$\endgroup$

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.