User talk:Rednaxela/kD-Tree - Revision history

Rednaxela: /* Translating... reimplementing... etc */ clarify detail

2011-04-18T12:34:06Z

Translating... reimplementing... etc: clarify detail

Rednaxela: /* Translating... reimplementing... etc */ note a little detail

2011-04-18T12:26:39Z

Translating... reimplementing... etc: note a little detail

Rednaxela: /* Translating... reimplementing... etc */ reply

2011-04-18T12:24:42Z

Translating... reimplementing... etc: reply

Skilgannon: /* Translating... reimplementing... etc */ One more requirement... maybe...

2011-04-18T06:25:21Z

Translating... reimplementing... etc: One more requirement... maybe...

Rednaxela: /* Translating... reimplementing... etc */ interesting.... some thoughts

2011-04-16T04:20:50Z

Translating... reimplementing... etc: interesting.... some thoughts

Skilgannon: /* Translating... reimplementing... etc */ new section

2011-04-15T18:08:06Z

Translating... reimplementing... etc: new section

RednaxelaBot: Using .

2010-07-01T08:43:10Z

Using <syntaxhighlight>.

Rednaxela: reply

2010-04-17T14:56:57Z

Nat: license for 3rd-gen tree?

2010-04-17T13:38:47Z

license for 3rd-gen tree?

Navajo: reply to the relply

2010-04-13T03:12:47Z

reply to the relply

@@ Line 339: / Line 339: @@
 # Consider a tree that explicitly tracks the bounding boxes of nodes, and uses them instead of split value during the search (mine does this for performance enhancement reasons). Place the lines/objects in the tree based on their center point (doesn't have to be their center necessarily, but seems like as good a choice as any). Then expand the tracked bounding boxes based on the bounding box of the line/object. This means your nodes will have overlapping bounding boxes, but it'll still work really.
 # or, alternatively, place an entry for the object/line in every node that "fits". If a line spans over a split, insert a copy on each side. If you are tracking bounding boxes, crop them at the split so that they won't overlap. This approach leads do much duplication and more memory use, but may have better performance during the search due to the lack of overlapping nodes. On the other hand, this approach also requires extra handling to make sure you don't get duplicates in your search results.
-Actually, those two approaches are inspired by what I've seen of [[wikipedia:R-Tree|R-Tree]] variants. It's common to use them for storing non-point objects for spatial search. The [[wikipedia:R+ Tree|R+ Tree]] essentially takes the duplication approach I mentioned, and other variants of the R-Tree take the approach of putting just into the one node that fits best. As a note to compare, the kd-tree is to the plain binary search tree, as the r-tree is to the b-tree. If your lines start introducing overlap in your nodes particularly often, I'd really take a good look into r-tree variants because the literature for them is done with overlap in mind (since r-trees inherently tend to have nodes with overlap anyway). --[[User:Rednaxela|Rednaxela]] 12:24, 18 April 2011 (UTC)
+Actually, those two approaches are inspired by what I've seen of [[wikipedia:R-Tree|R-Tree]] variants. It's common to use them for storing non-point objects for spatial search. R-Trees inherently have overlap, and the [[wikipedia:R+ Tree|r+ tree]] essentially takes the duplication approach I mentioned to deal with it, whereas other variants of the r-tree take the approach of putting just into the one node that "fits best". As a note to compare, the kd-tree is to the plain binary search tree, as the r-tree is to the b-tree. If your lines start introducing overlap in your nodes particularly often, I'd really take a good look into r-tree variants because the literature for them is done with overlap in mind (since r-trees inherently tend to have nodes with overlap anyway). --[[User:Rednaxela|Rednaxela]] 12:24, 18 April 2011 (UTC)

@@ Line 338: / Line 338: @@
 Well, one doesn't need to use a whole bunch of points to do lines. There are two main ways that come to mind to mind to deal with non-point objects (lines, or anything else really):
 # Consider a tree that explicitly tracks the bounding boxes of nodes, and uses them instead of split value during the search (mine does this for performance enhancement reasons). Place the lines/objects in the tree based on their center point (doesn't have to be their center necessarily, but seems like as good a choice as any). Then expand the tracked bounding boxes based on the bounding box of the line/object. This means your nodes will have overlapping bounding boxes, but it'll still work really.
-# or, alternatively, place an entry for the object/line in every node that "fits". If a line spans over a split, insert a copy on each side. This approach leads do much duplication and more memory use, but may have better performance during the search due to the lack of overlapping nodes. On the other hand, this approach also requires extra handling to make sure you don't get duplicates in your search results.
+# or, alternatively, place an entry for the object/line in every node that "fits". If a line spans over a split, insert a copy on each side. If you are tracking bounding boxes, crop them at the split so that they won't overlap. This approach leads do much duplication and more memory use, but may have better performance during the search due to the lack of overlapping nodes. On the other hand, this approach also requires extra handling to make sure you don't get duplicates in your search results.
 Actually, those two approaches are inspired by what I've seen of [[wikipedia:R-Tree|R-Tree]] variants. It's common to use them for storing non-point objects for spatial search. The [[wikipedia:R+ Tree|R+ Tree]] essentially takes the duplication approach I mentioned, and other variants of the R-Tree take the approach of putting just into the one node that fits best. As a note to compare, the kd-tree is to the plain binary search tree, as the r-tree is to the b-tree. If your lines start introducing overlap in your nodes particularly often, I'd really take a good look into r-tree variants because the literature for them is done with overlap in mind (since r-trees inherently tend to have nodes with overlap anyway). --[[User:Rednaxela|Rednaxela]] 12:24, 18 April 2011 (UTC)

← Older revision		Revision as of 12:24, 18 April 2011
Line 335:		Line 335:

	That's pretty much it exactly =) I'm estimating my initial 'warm up' scan will add around 1.4 million points, so a naive approach isn't really an option =). One other thing I was thinking about would be if I had a line, rather than a point, how I would store that in a Kd-tree? Put in a whole bunch of points to make up the locus? Reason being, I have several options to store where has known walls and where is known open space. One of them was using lines which essentially trace out my lasers fired from my range finder, with one end marked as 'solid' and the rest marked as 'open space'. As such, when I test a new point cloud in a certain position to see how well it fits, if the line (rather than just the endpoint) is in the top N closest to a point in the cloud it needs to be returned as well. Thanks for all your help =) --[[User:Skilgannon\|Skilgannon]] 06:25, 18 April 2011 (UTC)		That's pretty much it exactly =) I'm estimating my initial 'warm up' scan will add around 1.4 million points, so a naive approach isn't really an option =). One other thing I was thinking about would be if I had a line, rather than a point, how I would store that in a Kd-tree? Put in a whole bunch of points to make up the locus? Reason being, I have several options to store where has known walls and where is known open space. One of them was using lines which essentially trace out my lasers fired from my range finder, with one end marked as 'solid' and the rest marked as 'open space'. As such, when I test a new point cloud in a certain position to see how well it fits, if the line (rather than just the endpoint) is in the top N closest to a point in the cloud it needs to be returned as well. Thanks for all your help =) --[[User:Skilgannon\|Skilgannon]] 06:25, 18 April 2011 (UTC)
		+
		+	Well, one doesn't need to use a whole bunch of points to do lines. There are two main ways that come to mind to mind to deal with non-point objects (lines, or anything else really):
		+	# Consider a tree that explicitly tracks the bounding boxes of nodes, and uses them instead of split value during the search (mine does this for performance enhancement reasons). Place the lines/objects in the tree based on their center point (doesn't have to be their center necessarily, but seems like as good a choice as any). Then expand the tracked bounding boxes based on the bounding box of the line/object. This means your nodes will have overlapping bounding boxes, but it'll still work really.
		+	# or, alternatively, place an entry for the object/line in every node that "fits". If a line spans over a split, insert a copy on each side. This approach leads do much duplication and more memory use, but may have better performance during the search due to the lack of overlapping nodes. On the other hand, this approach also requires extra handling to make sure you don't get duplicates in your search results.
		+	Actually, those two approaches are inspired by what I've seen of [[wikipedia:R-Tree\|R-Tree]] variants. It's common to use them for storing non-point objects for spatial search. The [[wikipedia:R+ Tree\|R+ Tree]] essentially takes the duplication approach I mentioned, and other variants of the R-Tree take the approach of putting just into the one node that fits best. As a note to compare, the kd-tree is to the plain binary search tree, as the r-tree is to the b-tree. If your lines start introducing overlap in your nodes particularly often, I'd really take a good look into r-tree variants because the literature for them is done with overlap in mind (since r-trees inherently tend to have nodes with overlap anyway). --[[User:Rednaxela\|Rednaxela]] 12:24, 18 April 2011 (UTC)

← Older revision		Revision as of 06:25, 18 April 2011
Line 333:		Line 333:

	Does that help? :) --[[User:Rednaxela\|Rednaxela]] 04:20, 16 April 2011 (UTC)		Does that help? :) --[[User:Rednaxela\|Rednaxela]] 04:20, 16 April 2011 (UTC)
		+
		+	That's pretty much it exactly =) I'm estimating my initial 'warm up' scan will add around 1.4 million points, so a naive approach isn't really an option =). One other thing I was thinking about would be if I had a line, rather than a point, how I would store that in a Kd-tree? Put in a whole bunch of points to make up the locus? Reason being, I have several options to store where has known walls and where is known open space. One of them was using lines which essentially trace out my lasers fired from my range finder, with one end marked as 'solid' and the rest marked as 'open space'. As such, when I test a new point cloud in a certain position to see how well it fits, if the line (rather than just the endpoint) is in the top N closest to a point in the cloud it needs to be returned as well. Thanks for all your help =) --[[User:Skilgannon\|Skilgannon]] 06:25, 18 April 2011 (UTC)

← Older revision		Revision as of 04:20, 16 April 2011
Line 319:		Line 319:

	In June/July I'm going to be starting my thesis, a Simultaneous Localisation And Mapping algorithm, and in order to run at a half decent speed I'm probably going to need to need some form of 3D tree to project and compare different robot poses with the current scan readings of the environment. Anyway, being in an academic environment, Matlab (embedded in Labview) is the preferred language that I would implement my algorithm in. I'm not sure if you've worked with it, but it has very fast array operations despite the actual code itself being quite slow. I was wondering what changes you would make to the general design of your Kd-tree if array operations (eg. <code>y = sin(x)</code> where y and x are arrays) yielded a speedup of 50x or so versus accessing each component individually in a sort of <code>for x_i in x: y_i = sin(x_i)</code> situation. Any major re-factoring? I'm going to need some sort of KNN implementation along with a cutoff threshold. Any thoughts or insights would be appreciated before I commit myself too deeply along one implementation =) Thanks --[[User:Skilgannon\|Skilgannon]] 18:08, 15 April 2011 (UTC)		In June/July I'm going to be starting my thesis, a Simultaneous Localisation And Mapping algorithm, and in order to run at a half decent speed I'm probably going to need to need some form of 3D tree to project and compare different robot poses with the current scan readings of the environment. Anyway, being in an academic environment, Matlab (embedded in Labview) is the preferred language that I would implement my algorithm in. I'm not sure if you've worked with it, but it has very fast array operations despite the actual code itself being quite slow. I was wondering what changes you would make to the general design of your Kd-tree if array operations (eg. <code>y = sin(x)</code> where y and x are arrays) yielded a speedup of 50x or so versus accessing each component individually in a sort of <code>for x_i in x: y_i = sin(x_i)</code> situation. Any major re-factoring? I'm going to need some sort of KNN implementation along with a cutoff threshold. Any thoughts or insights would be appreciated before I commit myself too deeply along one implementation =) Thanks --[[User:Skilgannon\|Skilgannon]] 18:08, 15 April 2011 (UTC)
		+
		+	Hmm... interesting question... I've worked with Matlab some, but have not yet had reason to use it very much, so it's not a language I'm particularly fluent in yet. As far as optimizing for that criteria...
		+	# The simplest place to start would be translating simple things that iterate over axis, into array operations. It should be trivial to do so for the distance calculation and selection of which axis to split on. Then other things like loops over the entries in buckets could be turned into array operations.
		+	# Probably the biggest factor in all of this is bucket size. With array operations being tremendously superior to normal ones, it would certainly be the case that much larger bucket sizes would be more optimal for a matlab implementation. Maybe 10x bucket size? It would really take some playing around to find what works best.
		+	# Does matlab have native implementations of heaps? Size-limited heaps are rather good for the task of incrementally creating a list of "top n values", which I take advantage of in my tree implementation in a few places. An implementation of a heap in matlab code would not be worth it however. If there is a native heap implementation use it, otherwise it'll probably be faster to stick other sorted list strategies.
		+	# In my code I have a good number of "fail fast" checks that I've experimentally found to improve performance. In Java/C/etc, they're well worth it because often one can quickly rule out a condition before doing a slower check such as one that requires a distance calculation. In Matlab many of these "fail fast" checks will probably have more cost than a distance calculation, so wouldn't be worth it.
		+	# Pay close attention to general matlab performance advice like [http://blogs.mathworks.com/loren/2008/06/25/speeding-up-matlab-applications/ here]
		+	# Perhaps consider some other approaches like various variants of the [http://en.wikipedia.org/wiki/R-tree R-Tree]? I don't see the bucket kd-tree used too often in literature, but yet I could never get my r-tree variant attempts to perform anywhere as near as well as the bucket kd-tree approach. Nevertheless, I think such approaches definitely warrant further investigation.
		+
		+	Do keep in mind that the gains you'd see from a tree compared to the naive approach will be much smaller in a matlab implementation than a C or Java implementation, since the naive approach is simple and well suited to vectorization. It could be the case that a tree won't be worth it at all in Matlab, unless the size of the dataset if particularly huge.
		+
		+	If the performance of an optimized tree is really needed, I believe one can usually link C/C++ code to matlab code. Could this be considered as an option? I've seen such [http://info.ee.surrey.ac.uk/Personal/Z.Kalal/tld.html some things] in academic context which are primarily written in matlab but use C/C++ code in some performance critical spots. I seems to me that a search tree really is the perfect sort of thing to put in C/C++ code, because it's design doesn't affect the output of the algorithm, just the speed. In fact, when the tree is not the focus of a thesis, I might argue that keeping the search tree in C makes it's application more clear, because someone looking at how the tree is applied may not necessarily be concerned with the nitty-gritty of the n-nearest-neighbors search beyond knowing "and here it does a fast n-nearest-neighbors search" since it's output will be the same whether it's naive or fast. That's just my judgement though, I'm sure many might disagree with me, haha.
		+
		+	Does that help? :) --[[User:Rednaxela\|Rednaxela]] 04:20, 16 April 2011 (UTC)

← Older revision		Revision as of 18:08, 15 April 2011
Line 315:		Line 315:

	Hmm yeah, I forgot to deal with that. Sure, that same zlib license works. --[[User:Rednaxela\|Rednaxela]] 14:56, 17 April 2010 (UTC)		Hmm yeah, I forgot to deal with that. Sure, that same zlib license works. --[[User:Rednaxela\|Rednaxela]] 14:56, 17 April 2010 (UTC)
		+
		+	== Translating... reimplementing... etc ==
		+
		+	In June/July I'm going to be starting my thesis, a Simultaneous Localisation And Mapping algorithm, and in order to run at a half decent speed I'm probably going to need to need some form of 3D tree to project and compare different robot poses with the current scan readings of the environment. Anyway, being in an academic environment, Matlab (embedded in Labview) is the preferred language that I would implement my algorithm in. I'm not sure if you've worked with it, but it has very fast array operations despite the actual code itself being quite slow. I was wondering what changes you would make to the general design of your Kd-tree if array operations (eg. <code>y = sin(x)</code> where y and x are arrays) yielded a speedup of 50x or so versus accessing each component individually in a sort of <code>for x_i in x: y_i = sin(x_i)</code> situation. Any major re-factoring? I'm going to need some sort of KNN implementation along with a cutoff threshold. Any thoughts or insights would be appreciated before I commit myself too deeply along one implementation =) Thanks --[[User:Skilgannon\|Skilgannon]] 18:08, 15 April 2011 (UTC)

@@ Line 78: / Line 78: @@
 I'm not sure where in this page I should post this since there are so many topics here, but anyway, while trying to improve Gibbs I found two situations in which your tree throws exceptions. First is when searching for 0 neighbors. This one I easily solved by adding a simple <code>if(count < 1) return new ArrayList<Entry<T>>(0);</code> at the beginning of the nearestNeighbor method. The second problem is when you limit the tree size to something smaller than bucketSize. When the method removeOld() is called it throws a NullPointerEception when checking the condition of the following loop
-<code><pre>
+<code><syntaxhighlight>
 do {
      cursor.locationCount--;
      cursor = cursor.parent;
 } while (cursor.parent != null);
-</pre></code>
+</syntaxhighlight></code>
 which is easily solved by changing it to
-<code><pre>
+<code><syntaxhighlight>
 while (cursor != null){
      cursor.locationCount--;
      cursor = cursor.parent;
+}
-</pre></code>
+</syntaxhighlight></code>
 I know these problems are quite specific and easy to solve, but I just felt like I should report them. Also, if it is not much of a trouble, could you please add an option to remove the closest scan instead of the oldest? --[[User:Navajo|Navajo]] 01:15, 13 April 2010 (UTC)

@@ Line 96: / Line 96: @@
 I'm planning to test the impact of removing the closest instead of the oldest scan, but I can add this feature to the tree myself if it is too much of a trouble to you. --[[User:Navajo|Navajo]] 03:12, 13 April 2010 (UTC)
 == Warning! Rounding Errors! ==
@@ Line 313: / Line 309: @@
 :: In Java 6, @Override applies to interfaces as well. I've noticed Eclipse has bugs with this however and doesn't support it even when using Java 6. Anything except Eclipse likes it. Might change it I suppose though... --[[User:Rednaxela|Rednaxela]] 16:12, 20 March 2010 (UTC)

← Older revision		Revision as of 13:38, 17 April 2010
Line 96:		Line 96:

	I'm planning to test the impact of removing the closest instead of the oldest scan, but I can add this feature to the tree myself if it is too much of a trouble to you. --[[User:Navajo\|Navajo]] 03:12, 13 April 2010 (UTC)		I'm planning to test the impact of removing the closest instead of the oldest scan, but I can add this feature to the tree myself if it is too much of a trouble to you. --[[User:Navajo\|Navajo]] 03:12, 13 April 2010 (UTC)
		+
		+	----
		+
		+	Is you 3rd gen kd-tree found in the mercurial repo licensed under the same zlip license? I found no license notice in your third gen kd-tree source code. --[[User:Nat\|<span style="color:#099;">Nat</span>]] [[User talk:Nat\|<span style="color:#0a5;">Pavasant</span>]] 13:38, 17 April 2010 (UTC)

	== Warning! Rounding Errors! ==		== Warning! Rounding Errors! ==

← Older revision		Revision as of 03:12, 13 April 2010
Line 94:		Line 94:

	Well, the version currently posted on this page I kind of consider deprecated in favor of my [http://bitbucket.org/rednaxela/knn-benchmark/src/tip/ags/utils/dataStructures/trees/thirdGenKD/ new version]. The new version is slightly faster, is more flexibly coded, happens to behave right for the zero-sized search, and adds an additional feature of providing an iterator for allowing incremental search (but still best to specify an explicit max search size for performance reasons). On the other hand, the new tree doesn't yet have this support for removing old/close data. I could add this to it shortly if there is demand though. Would you want to use that Navajo? :) --[[User:Rednaxela\|Rednaxela]] 01:59, 13 April 2010 (UTC)		Well, the version currently posted on this page I kind of consider deprecated in favor of my [http://bitbucket.org/rednaxela/knn-benchmark/src/tip/ags/utils/dataStructures/trees/thirdGenKD/ new version]. The new version is slightly faster, is more flexibly coded, happens to behave right for the zero-sized search, and adds an additional feature of providing an iterator for allowing incremental search (but still best to specify an explicit max search size for performance reasons). On the other hand, the new tree doesn't yet have this support for removing old/close data. I could add this to it shortly if there is demand though. Would you want to use that Navajo? :) --[[User:Rednaxela\|Rednaxela]] 01:59, 13 April 2010 (UTC)
		+
		+	I'm planning to test the impact of removing the closest instead of the oldest scan, but I can add this feature to the tree myself if it is too much of a trouble to you. --[[User:Navajo\|Navajo]] 03:12, 13 April 2010 (UTC)

	== Warning! Rounding Errors! ==		== Warning! Rounding Errors! ==