KDTreeF

K-NEAREST NEIGHBOURS ALGORITHMS BENCHMARK
-----------------------------------------
Reading data from gun-data-Diamond-vs-jk.mini.CunobelinDC 0.3.csv.gz
Read 25621 saves and 10300 searches.

Running 20 repetition(s) for k-nearest neighbours searching:
:: 13 dimension(s); 10 neighbour(s)

RESULT << k-nearest neighbours search with Chase-san's kd-tree (KDTreeC) >>
: Average searching time       = 0.0776 miliseconds
: Average worst searching time = 11.1474 miliseconds
: Average adding time          = 1.5965 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Chase-san's kd-tree (KDTreeF) >>
: Average searching time       = 0.0259 miliseconds
: Average worst searching time = 1.0691 miliseconds
: Average adding time          = 1.5182 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's basic kd-tree >>
: Average searching time       = 0.2016 miliseconds
: Average worst searching time = 10.4197 miliseconds
: Average adding time          = 0.8725 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's fast kd-tree >>
: Average searching time       = 0.0245 miliseconds
: Average worst searching time = 10.5265 miliseconds
: Average adding time          = 3.4632 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's optimised kd-tree >>
: Average searching time       = 0.0264 miliseconds
: Average worst searching time = 13.8944 miliseconds
: Average adding time          = 3.4938 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Voidious' Linear search >>
: Average searching time       = 0.4874 miliseconds
: Average worst searching time = 14.7098 miliseconds
: Average adding time          = 1.0922 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Nat's Bucket PR k-d tree >>
: Average searching time       = 0.2280 miliseconds
: Average worst searching time = 188.3711 miliseconds
: Average adding time          = 27.4455 microseconds
: Accuracy                     = 27.12%

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (2nd gen) >>
: Average searching time       = 0.0183 miliseconds
: Average worst searching time = 1.8054 miliseconds
: Average adding time          = 1.8136 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (3rd gen, iterated) >>
: Average searching time       = 0.0183 miliseconds
: Average worst searching time = 11.8064 miliseconds
: Average adding time          = 1.9969 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (3rd gen) >>
: Average searching time       = 0.0155 miliseconds
: Average worst searching time = 2.7069 miliseconds
: Average adding time          = 2.4344 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Simonton's Bucket PR k-d tree >>
: Average searching time       = 0.1336 miliseconds
: Average worst searching time = 12.6894 miliseconds
: Average adding time          = 4.1237 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Voidious' Bucket PR k-d tree >>
: Average searching time       = 0.1115 miliseconds
: Average worst searching time = 8.2543 miliseconds
: Average adding time          = 2.2128 microseconds
: Accuracy                     = 100.0%


BEST RESULT: 
 - #1 Rednaxela's kd-tree (3rd gen) [0.0155]
 - #2 Rednaxela's kd-tree (2nd gen) [0.0183]
 - #3 Rednaxela's kd-tree (3rd gen, iterated) [0.0183]
 - #4 duyn's fast kd-tree [0.0245]
 - #5 Chase-san's kd-tree (KDTreeF) [0.0259]
 - #6 duyn's optimised kd-tree [0.0264]
 - #7 Chase-san's kd-tree (KDTreeC) [0.0776]
 - #8 Voidious' Bucket PR k-d tree [0.1115]
 - #9 Simonton's Bucket PR k-d tree [0.1336]
 - #10 duyn's basic kd-tree [0.2016]
 - #11 Nat's Bucket PR k-d tree [0.2280]
 - #12 Voidious' Linear search [0.4874]

Benchmark running time: 450.15 seconds

Really managed to hammer down the worst average time. As well as 1/3rd the best time. Still not really on par with Rednaxela's tree though.

But on the inverse you have a smaller data set earlier on. So it might balance out to a point. But I do intend to work on that a bit. I actually originally tuned with a random data set.

Also the current tree is based off C but I removed the Item class and altered the return to use a heap. Though I was considering having it interface with SortedMap and just returning that interface. So that I could avoid the issue of defining an external class.

I am mulling around how to redesign my tree so that it works better with the JIT, and so I create/destroy fewer objects (which should save some time).