Talk:Kd-trie

From Wikipedia, the free encyclopedia

[edit] Nomenclature

I'm not sure what to title this article. kd-trie is my own invention, not something used in any article (that I know of). On the other hand, there doesn't appear to be a consensus in papers and books. Perhaps the this article should be merged with kd-tree after all, but the data structures seem distinctly different.

I read about kdb trees in my lectures where data objects are also stored only in the leaves. Could this be just another expression or is it another kind of kd trees?

Hi. I fully agree with you that it is important to differentiate between the two structures. However, I'd like to suggest another title. I think one characteristic of a trie is that data is located at intermediate nodes, see the trie page. Therefore, I think that actually the data structure in the current kd-tree article should be named a kd-trie. But because of so many years of calling both kd-trees, I suggest an alternative. To differentiate, I have seen the terms "point kd-tree" and "region kd-tree" used. The point kd-tree is the same as in the current kd-tree article. The current kd-trie is a special case of the region kd-tree which can hold any kind of shapes (used in ray tracing). --Kaba3 (talk) 11:20, 22 November 2007 (UTC)

I'd like expand a bit why I think the current kd-tree can be thought more correctly as a trie. The idea of a trie is to store strings (or finite sequences of any ordered set) such that symbols are shared between words with the same prefix. This delivers O(m) time complexity for insertion, deletion and searching, where m is the length of the word. Now consider the data structure in the kd-tree article. The first inserted point should be taken as an "empty word". Every point has an associated axis-aligned plane which contains it. The subsequent points will be classified by this plane as being on the "negative" or "positive" side (for any direction). Now if you insert another point, then it implicitly has an associated string with it that is given by traversal to its insertion place in the tree. If in the traversal you choose the negative sub-tree, then append "n" to the string, otherwise append "p" to the string. This way you can see that the points are associated with strings of the form "nppnpppnnnpnpnp" etc. Thus you can see that these associated strings form a trie. But they are special kinds of tries: every point is part of the set, and so every associated substring is contained in the word-set. --Kaba3 (talk) 11:58, 22 November 2007 (UTC)

One more thing now that I'm on this:) The point kd-tree term is of course ambiguous as well and I like your "kd-trie" very much. So I think a good choice would be to name the current kd-tree a kd-trie and the current kd-trie a region kd-tree. --Kaba3 (talk) 13:02, 22 November 2007 (UTC)