Talk:Kd-tree

Bucket PR k-d tree

I think you all know about Bucket PR k-d tree (aka Simonton's tree), right? I'll get directly to my point.

The Bucket PR k-d tree (I'll refer as just a tree from now on) is a binary tree split by the median of the bound, right? I wonder if I make it m-ary tree, let say, Ternary or Quaternary tree instead of just binary? Will it better? » Nat | Talk » 09:12, 15 August 2009 (UTC)

Note, it doesn't by definition have to be split by the median, though the median is usually considered the best place. As far as your second question... it may be better, or it may not. I'm pretty sure it will depend heavily on the implementation details and the data set in question. --Rednaxela 14:51, 15 August 2009 (UTC)

In a binary tree you do 1 comparison to narrow it down to 1/2 the tree (if it's well balanced). In a 3-ary you do (on average) 1.5 comparisons to narrow it to 1/3. 4-ary 2 comparisons for 1/4 of the tree. 1*1/2 = 1.5*1/3 = 2*1/4. They're all theoretically the same. --Simonton 15:33, 15 August 2009 (UTC)

• Also note that with a 4-ary tree it's best to do a binary search at each node, which is pretty much the same thing as going back to a binary tree, except you'd be doing two comparisons for the same dimension instead of stepping to the next. --Simonton 15:36, 15 August 2009 (UTC)

(Edit conflict) It could be faster splitting 4-ways, sure, but my gut says not by very much. I'd probably recommend doing the normal 2-way (binary) one first, since it will be much simpler to develop and to debug, and then you can try to modify it to do 4-way. You'll need the 2-way version, anyway, in order to compare the speeds. Good luck. --Voidious 15:38, 15 August 2009 (UTC)

It seems that Ternary tree is the fastest of binary, ternary and quaternary. But I've some question, does the Kd-Tree output the same as linear (brute-force) search. Some of my test state that:

Starting Bucket PR k-d tree performance test...
Generating points...
Data generated.
Performing linear search...
Linear search complete; time = 0.003425156
Performing binary k-d tree search...
Binary tree search complete; time = 0.001995574
: accuracy = 0.4666666666666667
Performing ternary k-d tree search...
Ternary tree search complete; time = 2.91098E-4
: accuracy = 1.0
Performing quaternary k-d tree search...
Quaternary tree search complete; time = 3.22178E-4
: accuracy = 1.0

Data completely random. Accuracy calculate by number of result that is same as linear / cluster size. This test with a hundred data points and cluster size of 15. If I increase the data points to 26,000 then the accuracy drop to zero. Is this my tree problem or it is known problem with Kd-Tree? » Nat | Talk » 16:34, 15 August 2009 (UTC)

The kd-tree should definitely give the same results as a brute force search, so you must still have some bugs to work out. --Voidious 16:38, 15 August 2009 (UTC)

I wonder, is this Java's fault or my fault?

[0.649597542620717]
[0.649597542620717, 0.58290399982384]
[0.649597542620717, 0.58290399982384, 0.6393374687582193]
[0.649597542620717, 0.58290399982384, 0.6393374687582193, 0.5750290359605631]
[0.649597542620717, 0.58290399982384, 0.6393374687582193, 0.5750290359605631, 0.5724357947736444]
[0.649597542620717, 0.58290399982384, 0.6393374687582193, 0.5750290359605631, 0.5724357947736444, 0.2802621327822646]
[0.649597542620717, 0.58290399982384, 0.6393374687582193, 0.5750290359605631, 0.5724357947736444, 0.2802621327822646, 0.32353374890908837]
[0.702680085788956, 0.649597542620717, 0.6393374687582193, 0.58290399982384, 0.5724357947736444, 0.2802621327822646, 0.32353374890908837, 0.5750290359605631]
[0.702680085788956, 0.649597542620717, 0.6393374687582193, 0.6340371899722649, 0.5724357947736444, 0.2802621327822646, 0.32353374890908837, 0.5750290359605631, 0.58290399982384]
[0.702680085788956, 0.649597542620717, 0.6393374687582193, 0.6340371899722649, 0.646974720589997, 0.2802621327822646, 0.32353374890908837, 0.5750290359605631, 0.58290399982384, 0.5724357947736444]
[0.702680085788956, 0.649597542620717, 0.6393374687582193, 0.6340371899722649, 0.646974720589997, 0.2802621327822646, 0.32353374890908837, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459]
[0.7501432229056623, 0.649597542620717, 0.702680085788956, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.32353374890908837, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646]
[0.7501432229056623, 0.649597542620717, 0.702680085788956, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.32353374890908837, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.584615057797992]
[0.7501432229056623, 0.649597542620717, 0.702680085788956, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.5473273365712176, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.584615057797992, 0.32353374890908837]
[0.7501432229056623, 0.649597542620717, 0.7469223019892466, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.702680085788956, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.584615057797992, 0.32353374890908837, 0.5473273365712176]
[0.7501432229056623, 0.649597542620717, 0.7469223019892466, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.702680085788956, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.584615057797992, 0.32353374890908837, 0.5473273365712176]
[0.7469223019892466, 0.649597542620717, 0.702680085788956, 0.6340371899722649, 0.646974720589997, 0.6393374687582193, 0.5473273365712176, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.584615057797992, 0.32353374890908837, 0.4905223706647891]
[0.702680085788956, 0.649597542620717, 0.6393374687582193, 0.6340371899722649, 0.646974720589997, 0.584615057797992, 0.5473273365712176, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.6245525501315459, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.394947949397338]
[0.649597542620717, 0.646974720589997, 0.6393374687582193, 0.6340371899722649, 0.6245525501315459, 0.584615057797992, 0.5473273365712176, 0.5750290359605631, 0.58290399982384, 0.5724357947736444, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.47171213043152505]
[0.646974720589997, 0.6340371899722649, 0.6393374687582193, 0.58290399982384, 0.6245525501315459, 0.584615057797992, 0.5723736982234742, 0.5750290359605631, 0.47171213043152505, 0.5724357947736444, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.5473273365712176]
[0.6393374687582193, 0.6340371899722649, 0.584615057797992, 0.58290399982384, 0.6245525501315459, 0.5473273365712176, 0.5723736982234742, 0.5750290359605631, 0.47171213043152505, 0.5724357947736444, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.34506726588367553]
[0.6340371899722649, 0.6245525501315459, 0.584615057797992, 0.58290399982384, 0.5724357947736444, 0.5473273365712176, 0.5723736982234742, 0.5750290359605631, 0.47171213043152505, 0.34506726588367553, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.42934211482232326]
[0.6245525501315459, 0.58290399982384, 0.584615057797992, 0.5750290359605631, 0.5724357947736444, 0.5473273365712176, 0.5723736982234742, 0.42934211482232326, 0.47171213043152505, 0.34506726588367553, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.32353374890908837, 0.2134301740182818]
[0.5916976239916629, 0.58290399982384, 0.584615057797992, 0.5750290359605631, 0.5724357947736444, 0.5473273365712176, 0.5723736982234742, 0.42934211482232326, 0.47171213043152505, 0.34506726588367553, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.2134301740182818, 0.32353374890908837]
[0.584615057797992, 0.58290399982384, 0.5723736982234742, 0.5750290359605631, 0.5724357947736444, 0.5473273365712176, 0.32353374890908837, 0.42934211482232326, 0.47171213043152505, 0.34506726588367553, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.2134301740182818, 0.1465933120512868]
[0.58290399982384, 0.5750290359605631, 0.5723736982234742, 0.47171213043152505, 0.5724357947736444, 0.5473273365712176, 0.45197990894102086, 0.42934211482232326, 0.1465933120512868, 0.34506726588367553, 0.394947949397338, 0.2802621327822646, 0.4905223706647891, 0.2134301740182818, 0.32353374890908837]
[0.5750290359605631, 0.5724357947736444, 0.5723736982234742, 0.47171213043152505, 0.394947949397338, 0.5473273365712176, 0.45197990894102086, 0.42934211482232326, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.4905223706647891, 0.2134301740182818, 0.38020460318854615]
[0.5724357947736444, 0.47171213043152505, 0.5723736982234742, 0.42934211482232326, 0.394947949397338, 0.5473273365712176, 0.48555921817209335, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.4905223706647891, 0.2134301740182818, 0.45197990894102086]
[0.5723736982234742, 0.47171213043152505, 0.5473273365712176, 0.42934211482232326, 0.394947949397338, 0.4905223706647891, 0.48555921817209335, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.45197990894102086, 0.2134301740182818, 0.1149322950795779]
[0.5473273365712176, 0.47171213043152505, 0.4905223706647891, 0.42934211482232326, 0.394947949397338, 0.45197990894102086, 0.48555921817209335, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.1149322950795779, 0.2134301740182818, 0.34518844946880145]
[0.4905223706647891, 0.47171213043152505, 0.48555921817209335, 0.42934211482232326, 0.394947949397338, 0.45197990894102086, 0.4621126390235479, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.1149322950795779, 0.2134301740182818, 0.34518844946880145]
[0.48555921817209335, 0.47171213043152505, 0.47250074389363855, 0.42934211482232326, 0.394947949397338, 0.45197990894102086, 0.4621126390235479, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.1149322950795779, 0.2134301740182818, 0.34518844946880145]
[0.47250074389363855, 0.47171213043152505, 0.4621126390235479, 0.42934211482232326, 0.394947949397338, 0.45197990894102086, 0.34518844946880145, 0.38020460318854615, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.1149322950795779, 0.2134301740182818, 0.0954118001486222]
[0.47171213043152505, 0.42934211482232326, 0.4621126390235479, 0.38020460318854615, 0.394947949397338, 0.45197990894102086, 0.34518844946880145, 0.0954118001486222, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2802621327822646, 0.1149322950795779, 0.2134301740182818, 0.2586121183671883]
[0.4621126390235479, 0.42934211482232326, 0.45197990894102086, 0.38020460318854615, 0.394947949397338, 0.2802621327822646, 0.34518844946880145, 0.0954118001486222, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2586121183671883, 0.1149322950795779, 0.2134301740182818, 0.3448660120172713]
[0.45197990894102086, 0.42934211482232326, 0.44454448779822575, 0.38020460318854615, 0.394947949397338, 0.2802621327822646, 0.34518844946880145, 0.0954118001486222, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2586121183671883, 0.1149322950795779, 0.2134301740182818, 0.3448660120172713]
[0.44454448779822575, 0.42934211482232326, 0.34518844946880145, 0.38020460318854615, 0.394947949397338, 0.2802621327822646, 0.3448660120172713, 0.0954118001486222, 0.1465933120512868, 0.34506726588367553, 0.32353374890908837, 0.2586121183671883, 0.1149322950795779, 0.2134301740182818, 0.1913029805276719]
[0.42934211482232326, 0.394947949397338, 0.41996755464478697, 0.38020460318854615, 0.34506726588367553, 0.2802621327822646, 0.34518844946880145, 0.0954118001486222, 0.1465933120512868, 0.1913029805276719, 0.32353374890908837, 0.2586121183671883, 0.1149322950795779, 0.2134301740182818, 0.3448660120172713]

That's suppose to be PriorityQueue, but ... you see. My code is at Help:Help/Nat/Kd-Tree » Nat | Talk » 17:13, 15 August 2009 (UTC)

what does bucket size do

It's the maximum size of the leaf in the tree. Seriously, you're trying to run before you can walk. You need to brush up on your Java and comp-sci theory before you start messing around with Kd-Trees. If you want more info though, this describes some of the features in the tree pretty well [1]

How does that pdf kd-tree compare.

No idea. Probably about the same. Why are you so interested in Kd-Trees?

Could a kd-tree be made less than one thousand bytes?

I'm not sure, if you leave out the complicated stuff it loses its speed. Perhaps with the help of built-in structures like Java's PriorityQueue it might be possible. Impress us!

I'd say... possibly, but there's no reason to. An efficiently implemented linear search will waste much less of the limited codesize, and ought to be fast enough, espescially given that the number of search dimensions that make sense to put in a Minibot is small. The first nearest-n-neighbor search bots didn't use kd-trees and worked just fine.

On the other hand... if you're wanting to do it for it's own sake, it would be real neat to see just how small it could get! :)

I will be rather busy over the next fortnight, but after that I could give it a try.

Do you, Rednaxela, know of any efficient, low-codesize linear search algorithms with multiple choice?

I ran across this while doing my KD-Tree research http://www.michaelpollmeier.com/selecting-top-k-items-from-a-list-efficiently-in-java-groovy/ It looks like once you calculate your distances to everything (two for loops) it's just about 4 lines of code.

The trick with the performance of linear search is what method you use to keep track of the "N closest points so far". The methods in that article have a problem, because they're storing every point in the list in the PriorityQueue, sorted list or whatever other structure. That is inefficient. It's far better to store the only "N closest points so far". You can do this using PriorityQueue by removing the highest distance point from the queue whenever the queue's length is greater than N.

The optimal solution for speed of a linear search is to use a bounded-size heap to store the "N closest points so far" because you waste the fewest operations on points which are not within the N closest. PriorityQueue is implemented using a heap like this, however PriorityQueue is inefficient in practice due to Comparator/Comparable OOP stuff.

Personally I'd probably try making the smallest custom implementation of a heap that I could. Alternatively, you could use use Collections.sort() or PriorityQueue, however that adds it's own codesize because you have to have some wrapper object around points which implements Comparable/Comparator, and I fear that wrapper may add more codesize than tiny specialized implementation of a heap would.