Talk:Tango tree

Cleanup needed

This article is a mess. Its spelling is inconsistent, its formulas are broken and it does not explains what the competitiveness in the first sentence means. Qwertyus (talk) 17:31, 8 February 2011 (UTC)

I had a go. There's nothing wrong with the big O formulas being in plain text - that allows linking the first use of O to the big O notation article, which seems to be the way it's usually done, and having massive florid maths letters all over the place isn't really necessary for something so simple. Somebody who understands Big O (and tango trees) should check statements like "O(lg n)(lg n)(lg n) " are actually true. The hit-and-miss spelling makes me worry about the facts. I didn't change "competitiveness" because I don't know what it's specifically talking about, either. Search time? Insertion time? Some kind of averaging?  Card Zero  (talk) 13:40, 27 February 2011 (UTC)

Since the paper presenting this is called "Dynamic Optimality, Almost", and it addresses the "Dynamic Optimality Conjecture", it's worth looking at that: http://en.wikipedia.org/wiki/Splay_tree#Dynamic_optimality_conjecture

On citeseer, citations to the 2004 Tango paper is listed as "7 citations, 1 self". Clicking through only yields 2 actual papers with citations to it, so I don't think this data structure has enough significance to be worth the extensive description of the detailed algorithm.

On O(log log n) claims: From the dynamic optimality conjecture page, we see the conjecture is that if certain classes of search trees take A(S) operations/time to perform n operations S, then the splay tree is theorized to be O(n+A(S)), that is no more than O(n) "worse". In other words, the splay tree is "competitive" with that class of search trees. In one of the articles citing the Tango tree, I find this definition: "[OPTm(X) is the time taken by a tree built knowing in advance what the sequence of operations is going to be.] An online algorithm is dynamically optimal if it executes X in time O(OPTm(X)). More generally, we say that an algorithm A is f(n)-competitive if its access cost Am(X) does not exceed f(n)OPTm(X)." So, here is a definition of competitive that must be close to the one being described on this page: O(log log N)-competitive appears to mean (in some sense) "no worse than O(log log N * OPTm(X))".

However, there is absolutely no way that this data structure is anything faster than O(log n) for random searches; this is trivially provable for any comparison-based tree algorithm. They are presumably only more optimal when e.g. the distribution of searches is significantly biased. 50.47.39.246 (talk) 18:48, 14 October 2011 (UTC)

Yes this article is completely incomprehensible. It feels like what the original paper would be in presubmission phase. None of the synthesizing work has been done, and quite frankly, I'm not sure it deserves such extensive coverage. --82.238.18.163 (talk) 22:05, 5 April 2012 (UTC)