Talk:Kd-tree

From Wikipedia, the free encyclopedia

Contents 1 Contradiction in text? 2 Picture Included 3 Python? 4 Content 5 Search complexity? 6 Adding elements? 7 Nearest neighbour 8 Missing title in title bar

[edit] Contradiction in text?

Doesn't the statement "In addition, every node of a kd-tree, from the root to the leaves, stores a point" contradict the end of the first paragraph "kd-tries are a variant that store data only in leaf nodes" ? I'd change it, but I know almost nothing about the topic. Also, while you are at it, "point is infite" should be "point is infinite." Nice article. It helped me a lot.

[edit] Picture Included

The picture included really isn't the best choice for demonstrating a kd-tree to someone who isn't familiar with it. has a much better picture, for instance

The problem I have with the picture (we're talking about the pic at the top, yes?) is that the vertices of the splitting planes appear, visually speaking, to be tree nodes, when in fact that is not correct. And the tree nodes themselves are not represented. wwheeler 18 January 2007

Go for it. I made the existing one but agree that it's not too explanatory. Btyner 05:17, 20 November 2005 (UTC)

I also made an SVG version of this new one, but for some reason, commons didn't recognize it as such. Btyner 22:21, 21 February 2006 (UTC)

Also, some psuedo code for construction, insertion, deletion, nearest neighbor, etc. would be very useful. --Numsgil 13:07, 13 October 2005 (UTC)

[edit] Python?

Does the Python version of the pseudocode really add anything? It seems like it is basically a restatement of the pseudocode with a slightly different (less clear) syntax. Do we really need both? Neilc 22:37, 15 April 2006 (UTC)

I personally found it useful to have an executable version to try things out on and improve my understanding. That's also why I wrote the code that produced that 2D results picture. Granted, this page may not be the best place for an implementation, though I don't know a better place for such a tiny snippet. KiwiSunset 04:51, 19 April 2006 (UTC)

[edit] Content

Ok, so I can understand that balancing a kd tree takes care, but how do I actually do it? This article really needs someone with that knowledge to add that information in. ACiD2

I've been working on tracking down the existing work done by Overmars on this topic, which is very similar to AVL trees. I might end up just re-deriving it, getting some review, and giving the citation as the source of the idea. If anyone has access to the pertinent journal article, it would be very helpful. There was also a technical report published. M. H. Overmars and J. van Leeuwen, Dynamic multi-dimensional data structures based on quad- and k-d trees, Acta Informatica 17, 3(1982), 267-285.

[edit] Search complexity?

The articles contains no information about the complexity of searching a kd-tree for an exact nearest neighbor?

The algorithm analyzed in the following paper is fairly generic (it uses region queries), but does apply to kd-trees. I don't believe there's an existing article about the algorithm itself, but it would be nice to have one. Cleary, J. G. 1979. Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space. ACM Trans. Math. Softw. 5, 2 (Jun. 1979), 183-192. DOI= http://doi.acm.org/10.1145/355826.355832

[edit] Adding elements?

Doesnt adding elements in the method described lead to an unbalanced tree? If this is so then i think it should be made explicitly clear, and a rebalancing algorithm (or a way to preserve balance) should be given User A1 07:21, 1 December 2006 (UTC)

kd-Tree is a static data structure, so yeah adding an element will introduce disorder. Rebalancing it is perhaps outside the realms of the basic description. IlyaTheMuromets 22:45, 8 Jan 2007 (EST)

[edit] Nearest neighbour

Hello,

I added the NN algorithm, but i have hidden it in comments as it was a little off the cuff. Feel free to fix it, i will go over it again later.

Thanks User A1 12:54, 2 December 2006 (UTC)

[edit] Missing title in title bar

The title of this article does not seem to be showing up in my browser title bar. Is this just me, and if not any suggested soultions?

MadScientistVX 05:09, 23 February 2007 (UTC)

Odd. I second that, firefox 1.5.0.7 linux x86, despite the presence of <title>Kd-tree - Wikipedia, the free encyclopedia</title> User A1 15:23, 23 February 2007 (UTC)