# Space-Efficient Online Computation of Quantile Summaries Lemma 3

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.