KDTreeF
Jump to navigation
Jump to search
Revision as of 9 June 2012 at 05:08.
This is the thread's initial revision.
This is the thread's initial revision.
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.
