K-d tree - Revision history

AndrejKP: Grammar

2022-06-16T12:30:48Z

Grammar

Jureslak at 13:27, 19 November 2018

2018-11-19T13:27:36Z

Jureslak at 13:03, 19 November 2018

2018-11-19T13:03:58Z

Jureslak at 12:58, 19 November 2018

2018-11-19T12:58:43Z

Jureslak: /* References */

2018-11-19T12:58:12Z

‎References

Jureslak at 12:57, 19 November 2018

2018-11-19T12:57:43Z

Jureslak at 12:38, 19 November 2018

2018-11-19T12:38:54Z

Jureslak at 12:38, 19 November 2018

2018-11-19T12:38:10Z

Jureslak at 12:35, 19 November 2018

2018-11-19T12:35:01Z

Jureslak at 12:32, 19 November 2018

2018-11-19T12:32:17Z

@@ Line 5: / Line 5: @@
 In order to compute nearest neighbors effectively, fast spatial search structures have been developed, such as [https://en.wikipedia.org/wiki/Octree octree], [https://en.wikipedia.org/wiki/Ball_tree ball tree], [https://en.wikipedia.org/wiki/Cover_tree cover tree] and [https://en.wikipedia.org/wiki/K-d_tree $k$-d tree]. All of these structures first take a list of $N$ points and build a search structure, enabling  subsequent queries for $n$ nearest neighbors to be answered in $O(n\log N)$ time.
-The $k$-d tree structure is describe below to give reader a basic idea of how such spatial structures store data.
+The $k$-d tree structure is described below to give the reader a basic idea of how such spatial structures store data.
 [[File:image_1avj3kcbe157a1ad610k81brmgsj9.png|800px|thumb|<caption> 2D tree example</caption>]]

@@ Line 28: / Line 28: @@
 Besides speed, which was the main factor, we also considered the number of dependencies a library has and how general it is regarding distances and data types.
-Overall, we decided to use the [https://github.com/jlblancoc/nanoflann/ nanoflann] library in [http://e6.ijs.si/medusa/ medusa].
+Overall, we decided to use the [https://github.com/jlblancoc/nanoflann/ nanoflann] library in [http://e6.ijs.si/medusa/ medusa]. Our wrappers are available
 The results and reasoning is described more accurately in the technical report [[:File:report.pdf]].

@@ Line 6: / Line 6: @@
 In order to compute nearest neighbors effectively, fast spatial search structures have been developed, such as [https://en.wikipedia.org/wiki/Octree octree], [https://en.wikipedia.org/wiki/Ball_tree ball tree], [https://en.wikipedia.org/wiki/Cover_tree cover tree] and [https://en.wikipedia.org/wiki/K-d_tree $k$-d tree]. All of these structures first take a list of $N$ points and build a search structure, enabling  subsequent queries for $n$ nearest neighbors to be answered in $O(n\log N)$ time.
 The $k$-d tree structure is describe below to give reader a basic idea of how such spatial structures store data.
 [[File:image_1avj3kcbe157a1ad610k81brmgsj9.png|800px|thumb|<caption> 2D tree example</caption>]]
@@ Line 30: / Line 29: @@
 Besides speed, which was the main factor, we also considered the number of dependencies a library has and how general it is regarding distances and data types.
 Overall, we decided to use the [https://github.com/jlblancoc/nanoflann/ nanoflann] library in [http://e6.ijs.si/medusa/ medusa].
 Let us illustrate the whole procedure with a simple example of a 2D tree for eleven nodes, with node numbers and coordinates listed in the first and the second column of Table \ref{tab:kD_nodes} and attached to the corresponding dots on the unit square in the left part of Figure \ref{fig.2D_treegraph}.
@@ Line 62: / Line 64: @@
 $(0,0)$, $(0,1)$, $(0.6,0.3)$, and $(0.76,0.8)$.
 In practical cases, the refinement of the tree stops sooner, when its leaves are represented by list of several nodes, because such a fine grained distribution of leaves as in the presented example is often not beneficial from the computational efficiency point of view.
+-->
 == References ==
 * Trobec R., Kosec G., Parallel scientific computing: theory, algorithms, and applications of mesh based and meshless methods: Springer; 2015.

@@ Line 32: / Line 32: @@
 Let us illustrate the whole procedure with a simple example of a 2D tree for eleven nodes, with node numbers and coordinates listed in the first and the second column of Table \ref{tab:kD_nodes} and attached to the corresponding dots on the unit square in the left part of Figure \ref{fig.2D_treegraph}.
@@ Line 63: / Line 62: @@
 $(0,0)$, $(0,1)$, $(0.6,0.3)$, and $(0.76,0.8)$.
 In practical cases, the refinement of the tree stops sooner, when its leaves are represented by list of several nodes, because such a fine grained distribution of leaves as in the presented example is often not beneficial from the computational efficiency point of view.
--->
 == References ==
 * Trobec R., Kosec G., Parallel scientific computing: theory, algorithms, and applications of mesh based and meshless methods: Springer; 2015.

← Older revision		Revision as of 12:58, 19 November 2018
Line 66:		Line 66:

	== References ==		== References ==
−	* Trobec R., Kosec G., Parallel scientific computing : theory, algorithms, and applications of mesh based and meshless methods: Springer; 2015.	+	* Trobec R., Kosec G., Parallel scientific computing: theory, algorithms, and applications of mesh based and meshless methods: Springer; 2015.
−	* k-d tree. (n.d.). In Wikipedia. Retrieved March 17, 2017, from https://en.wikipedia.org/wiki/K-d_tree

@@ Line 24: / Line 24: @@
 [[File:kdtree_find_support_time.png]]
-Second, we tested how the structures performed during the node generation process, as described in [[Positioning of computational nodes]] page.
+Second, we tested how the structures performed during the node generation process, as described in [[Positioning of computational nodes]] page. Results are shown in figure below.
 [[File:kdtree_pds_time.png]]
+Besides speed, which was the main factor, we also considered the number of dependencies a library has and how general it is regarding distances and data types.
+Overall, we decided to use the [https://github.com/jlblancoc/nanoflann/ nanoflann] library in [http://e6.ijs.si/medusa/ medusa].

@@ Line 20: / Line 20: @@
 * [https://github.com/jlblancoc/nanoflann/ nanoflann]
-First, we tested a typical example of finding support domains of $n$ nodes for all nodes, which includes building a tree from a set of points and finding $n$ closest nodes for each point.
+Two typical usage examples for these structures were tested. First, we tested a typical example of finding support domains of $n$ nodes for all nodes, which includes building a tree from a set of points and finding $n$ closest nodes for each point. The results are shown below.
 [[File:kdtree_find_support_time.png]]
-Nearest neighbor search is a $log n$ procedure, although in practice, especially in higher dimensions, it's closer to o(n). There is a nice description of the algorithm on [https://en.wikipedia.org/wiki/K-d_tree wikipedia] website. We tested ANN and Libssrckdtree implementations. In addition we tested also cover tree nearest neighbor search.
+Second, we tested how the structures performed during the node generation process, as described in [[Node positioning algorithms]] page.
 [[File:nearest_neighbor_search_time.jpg|800px]]

@@ Line 13: / Line 13: @@
 Often, dynamic search structures are needed as well, which support node insertion and removal. In the beginning we were using [http://www.cs.umd.edu/~mount/ANN/ ANN] and [https://www.savarese.com/software/libssrckdtree/ libssrckdtree]
-libraries for static and dynamic spatial search structures, respectively. Later, we tested four different publicly available C++ libraries:
+libraries for static and dynamic spatial search structures, respectively. Later, we tested four different publicly available C++ libraries that support at least static spatial search:
 * [http://www.cs.umd.edu/~mount/ANN/ ANN]
@@ Line 20: / Line 20: @@
 * [https://github.com/jlblancoc/nanoflann/ nanoflann]
-We tested a typical example of finding support domains of 9 nodes for all nodes, which includes building a tree from a set of points and finding $n$ closest nodes for each point.
+First, we tested a typical example of finding support domains of $n$ nodes for all nodes, which includes building a tree from a set of points and finding $n$ closest nodes for each point.
 The results are shown below.
-[[File:Tree_building_time.jpg]]
+[[File:kdtree_find_support_time.png]]
 Nearest neighbor search is a $log n$ procedure, although in practice, especially in higher dimensions, it's closer to o(n). There is a nice description of the algorithm on [https://en.wikipedia.org/wiki/K-d_tree wikipedia] website. We tested ANN and Libssrckdtree implementations. In addition we tested also cover tree nearest neighbor search.