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.


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.