User:Duyn/kd-tree Tutorial - Revision history

Skilgannon: /* Searching */ Update method call for searchTree to include max distance, get rid of (unnecessary) spaghetti code

2012-01-27T14:43:15Z

Searching: Update method call for searchTree to include max distance, get rid of (unnecessary) spaghetti code

Skilgannon: /* Searching a Tree */ Should be MUCH faster... no need to expand all nodes then remove them later...

2012-01-27T14:40:29Z

Searching a Tree: Should be MUCH faster... no need to expand all nodes then remove them later...

Duyn: /* Full Benchmark Results */ Pointer to source and data files.

2010-03-13T13:41:12Z

Full Benchmark Results: Pointer to source and data files.

Duyn: /* Evaluation_3 */ Updated benchmark.

2010-03-13T13:35:34Z

Evaluation_3: Updated benchmark.

Duyn: /* Changes to our Tree */ Updated changes to new opt-tree.

2010-03-13T13:30:06Z

Changes to our Tree: Updated changes to new opt-tree.

Duyn: /* Evaluation_2 */ Updated results with new benchmark.

2010-03-13T13:27:51Z

Evaluation_2: Updated results with new benchmark.

Duyn: /* Evaluation */ Updated results with new benchmark.

2010-03-13T13:23:29Z

Evaluation: Updated results with new benchmark.

Duyn: /* Full source code */ New section above: full benchmark results

2010-03-13T13:17:35Z

Full source code: New section above: full benchmark results

Duyn: /* Optimisations to the Tree */ Switched back to PriorityQueue for optimised tree.

2010-03-13T13:14:09Z

Optimisations to the Tree: Switched back to PriorityQueue for optimised tree.

Show changes

Duyn: WIP warning

2010-03-13T06:28:50Z

WIP warning

@@ Line 654: / Line 654: @@
     if (tree.contentMin != null)
       stack.addLast(new SearchStackEntry<X>(false, tree));
- TREE_WALK:
     while (!stack.isEmpty()) {
       final SearchStackEntry<X> entry = stack.removeLast();
@@ Line 663: / Line 663: @@
           cur.contentMin, cur.contentMax);
         if (d > state.results.lastKey())
-          continue TREE_WALK;
+          continue;
+      }
       if (cur.isTree()) {
-        searchTree(query, cur, stack);
+        searchTree(query, cur, stack, state.results.peek().priority);
       } else {
         searchLeaf(query, cur, state);

@@ Line 681: / Line 681: @@
   private static <X extends Exemplar> void
   searchTree(double[] query, OptKdTree<X> tree,
-    Deque<SearchStackEntry<X>> stack)
+    Deque<SearchStackEntry<X>> stack, double maxPriority)
+  {
     OptKdTree<X> nearTree = tree.left, farTree = tree.right;
@@ Line 696: / Line 696: @@
     // first. This is likely to constrict our max distance
     // sooner, resulting in less visited nodes
-    if (!farEmpty) {
+    if (!farEmpty && minDistanceSqFrom(query,farTree.contentMin,farTree.contentMax) < maxPriority) {
       stack.addLast(new SearchStackEntry<X>(true, farTree));
+    }
-    if (!nearEmpty) {
+    if (!nearEmpty && minDistanceSqFrom(query,nearTree.contentMin,nearTree.contentMax) < maxPriority) {
       stack.addLast(new SearchStackEntry<X>(true, nearTree));
+    }

@@ Line 1,133: / Line 1,133: @@
 ==Full Benchmark Results==
-Below are the full benchmark results quoted throughout this page. It puts the performance of our trees in context compared to other ''k''d-trees available on this wiki.
+Below are the full benchmark results quoted throughout this page. It puts the performance of our trees in context compared to other ''k''d-trees available on this wiki. The benchmark ([[k-NN algorithm benchmark]]) was run with the [http://homepages.ucalgary.ca/~agschult/robocode/gun-data-Diamond-vs-jk.mini.CunobelinDC%200.3.csv.gz Diamond vs CunobelinDC gun data].
   K-NEAREST NEIGHBOURS ALGORITHMS BENCHMARK
   -----------------------------------------
@@ Line 1,146: / Line 1,145: @@
   Running tests...test 1/30
-  [snip]
+  [...]
    COMPLETED.

@@ Line 1,043: / Line 1,043: @@
 ===Evaluation===
-Our improved heap approximately doubles the performance of our algorithm. We now have a tree that is comparable to the fastest trees around this wiki.
+Our improved heap squeezes a bit more performance (~10%) out of our tree:
-  K-NEAREST NEIGHBOURS ALGORITHMS BENCHMARK
+  RESULT << k-nearest neighbours search with Voidious' Linear search >>
-  -----------------------------------------
+  : Average searching time       = 0.5740 miliseconds
-  Reading data from gun-data-Diamond-vs-jk.mini.CunobelinDC 0.3.csv.gz
+  : Average worst searching time = 2.3482 miliseconds
-  Read 25621 saves and 10300 searches.
+ : Average adding time          = 0.4528 microseconds
-  Running 30 repetition(s) for k-nearest neighbours searching:
+  [...]
-  Running tests... COMPLETED.
+  RESULT << k-nearest neighbours search with Rednaxela's kd-tree (2nd gen) >>
-  RESULT << k-nearest neighbours search with Rednaxela's Bucket kd-tree >>
+  [...]
   RESULT << k-nearest neighbours search with duyn's basic kd-tree >>
-  : Average searching time       = 0.405 miliseconds
+  : Average searching time       = 0.3939 miliseconds
-  : Average worst searching time = 5.343 miliseconds
+  : Average worst searching time = 11.5167 miliseconds
-  : Average adding time          = 0.68 microseconds
+  : Average adding time          = 0.5165 microseconds
-  : Accuracy                     = 100%
+  : Accuracy                     = 100.0%
   RESULT << k-nearest neighbours search with duyn's optimised kd-tree >>
-  : Average searching time       = 0.094 miliseconds
+  : Average searching time       = 0.0536 miliseconds
-  : Average worst searching time = 7.744 miliseconds
+  : Average worst searching time = 1.6742 miliseconds
-  : Average adding time          = 2.49 microseconds
+  : Average adding time          = 2.9380 microseconds
-  : Accuracy                     = 100%
+  : Accuracy                     = 100.0%
   RESULT << k-nearest neighbours search with duyn's fast kd-tree >>
-  : Average searching time       = 0.047 miliseconds
+  : Average searching time       = 0.0479 miliseconds
-  : Average worst searching time = 13.176 miliseconds
+  : Average worst searching time = 25.0995 miliseconds
-  : Average adding time          = 2.21 microseconds
+  : Average adding time          = 2.1288 microseconds
-  : Accuracy                     = 100%
+  : Accuracy                     = 100.0%
   BEST RESULT:
-   - #1 duyn's fast kd-tree [0.0467]
+   - #1 Rednaxela's kd-tree (2nd gen) [0.0378]
-   - #2 Rednaxela's Bucket kd-tree [0.0549]
+ [...]
-   - #3 duyn's optimised kd-tree [0.0936]
+   - #3 duyn's fast kd-tree [0.0479]
-   - #4 duyn's basic kd-tree [0.405]
+   - #4 duyn's optimised kd-tree [0.0536]
+ [...]
- Benchmark running time: 208.13 seconds
+   - #8 duyn's basic kd-tree [0.3939]
 Our client code has barely changed:

@@ Line 1,002: / Line 1,002: @@
+  }
-* Our searchLeaf() method is greatly simplified by not having to do special processing for duplicate distances:
+* Our searchLeaf() method no longer needs to explicitly poll the top since our heap will just replace it if it has no space:
   private static <X extends Exemplar> void
@@ Line 1,016: / Line 1,016: @@
+      }
+    }
+  }

@@ Line 733: / Line 733: @@
 ===Evaluation===
-[upcoming]
+From the same benchmark run, our optimised tree obtains the following results:
-This is promising. We are finally in the same league as other ''k''d-tree implementations on this wiki. Because our search() method flattens the TreeMap, our client code is almost the same:
+This is promising. We are a whole order of magnitude faster and finally in the same league as other ''k''d-tree implementations on this wiki. We have not changed our API, so the following shim is only for completeness:
 * DuynOptKNNSearch.java
@@ Line 757: / Line 795: @@
     @Override
-    public KNNPoint[] getNearestNeighbors(final double[] location, final int size) {
+    public KNNPoint[]
       final List<KNNPoint> justPoints = new LinkedList<KNNPoint>();
       for(PrioNode<StringExemplar> sr : tree.search(location, size)) {

@@ Line 1,179: / Line 1,179: @@
+  }
-==Full source code==
+==Full Benchmark Results==
 The full source code for all three trees presented in this tutorial can be downloaded together: [[File:duyn_tutorial_kd_trees.jar]]. The code is available under the [[RWPCL]].

← Older revision		Revision as of 06:28, 13 March 2010
Line 1:		Line 1:
		+	[Work-in-Progress]
		+
	This page will walk you through the implementation of a ''k''d-tree. We start with a basic tree and progressively add levels of optimisation. Writing a fully optimised ''k''d-tree is an advanced task, but starting with the basics helps. There are already other ''k''d-trees on this wiki, see some of the others for ideas.		This page will walk you through the implementation of a ''k''d-tree. We start with a basic tree and progressively add levels of optimisation. Writing a fully optimised ''k''d-tree is an advanced task, but starting with the basics helps. There are already other ''k''d-trees on this wiki, see some of the others for ideas.