SODA

I am happy to report that our SODA submission on The Geometry of Binary Search Trees was accepted.

This paper works on the old question of competitiveness in the binary search tree model (some old posts of mine: 1, 2, 3), and makes some progress that is not easy to quantify. We propose a geometric interpretation of the problem, which seems to eliminate all the messiness attached to trees, and makes previous lower bounds (the Wilber bounds) very clear. The geometric view is somehow very appealing; a referee called this "an amusing paper" (in a very positive comment), and I will happily agree to this description.

Unfortunately, our work does not lead to a new upper bound, though it leads to a reformulation of an old conjecture. Joan Lucas and Ian Munro independently introduced a natural offline greedy algorithm, which they conjectured to be an O(1) approximation. Speaking informally, the prevailing opinion seemed to be that this had to be an O(1) approximation (modulo technical details in proving it!), but the really interesting question was to show an online O(1)-competitive algorithm. Well, our work shows that this view was wrong: we can make the Lucas-Munro algorithm online, with a constant slow-down.

Thus, if the conjectures of Lucas and Munro are correct, this tree achieves dynamic optimality. This is the first proposal for dynamic optimality after the famous splay trees that started the whole field.

Our geometric view also has consequences for the lower bounds (which are crucial if we want constant approximation). The only known lower bounds were Wilber's 2 bounds from FOCS'06. Wilber's first bound was used in our O(lg lg n)-competitive algorithm. Though Wilber conjectured that his second bound is stronger, we still have no idea how the two compare.

In our framework, Wilber's bounds are special cases of a very natural class of "cut bounds," and they get very simple descriptions. Instead of comparing the two Wilber bounds, we now face a broader question of finding the best possible cut bound. We solve this by proposing a new lower bound that is shown to be an O(1)-approximation to the best cut bound. This supersedes Wilber's results, though we do not know that it is strictly stronger than Wilber's bounds.