User talk:Duyn/kd-tree Tutorial - Revision history

Duyn: Response to heap.

2010-03-17T07:12:36Z

Response to heap.

Rednaxela: Tried the d-ary heap.

2010-03-15T22:41:02Z

Tried the d-ary heap.

Rednaxela: misread

2010-03-14T15:01:55Z

misread

Duyn: Response to implicit heap.

2010-03-14T11:34:39Z

Response to implicit heap.

Rednaxela: Heap not implicit

2010-03-14T08:31:06Z

Heap not implicit

Rednaxela: quick update on some variance based split testing

2010-03-13T18:10:46Z

quick update on some variance based split testing

Duyn: Trees still in dev

2010-03-13T11:58:11Z

Trees still in dev

Duyn: Response.

2010-03-13T06:20:00Z

Response.

Rednaxela: reply

2010-03-13T02:17:12Z

Duyn: Forgot sig.

2010-03-13T02:10:52Z

Forgot sig.

← Older revision		Revision as of 07:12, 17 March 2010
Line 21:		Line 21:

	By the way, I just tried out your implicit d-ary heap with my tree. The result shows that 3-ary and 4-ary are roughly tied for speed, both notably better than 2-ary and 5-ary. Despite this, it's still just slightly slower than using my heap ([http://bitbucket.org/rednaxela/knn-benchmark/src/tip/ags/utils/dataStructures/BinaryHeap.java code link]) in my tree. --[[User:Rednaxela\|Rednaxela]] 22:41, 15 March 2010 (UTC)		By the way, I just tried out your implicit d-ary heap with my tree. The result shows that 3-ary and 4-ary are roughly tied for speed, both notably better than 2-ary and 5-ary. Despite this, it's still just slightly slower than using my heap ([http://bitbucket.org/rednaxela/knn-benchmark/src/tip/ags/utils/dataStructures/BinaryHeap.java code link]) in my tree. --[[User:Rednaxela\|Rednaxela]] 22:41, 15 March 2010 (UTC)
		+	: That fits with my experience. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7774 The Influence of Caches on the Performance of Heaps] suggests that if you take the cost of a swap operation into account, remove-min is cheapest for a 3-ary/4-ary heap. It was at that point the heap stopped being a bottleneck in my tree and so I stopped optimising it.—[[User:Duyn\|duyn]] 07:12, 17 March 2010 (UTC)

← Older revision		Revision as of 22:41, 15 March 2010
Line 19:		Line 19:
	:I am not sure I understand. The heap as presented ''does'' encode its tree structure solely in array indices. It only creates new <code>PrioNode</code>s so users can have access to priorities after a <code>poll()</code>. That step has nothing to do with the structure of the heap. The heap is implicit in that the parent/children of a node are worked out from array indices (as seen in the siftXXX methods), rather than storing explicit references in each node.—[[User:Duyn\|duyn]] 11:34, 14 March 2010 (UTC)		:I am not sure I understand. The heap as presented ''does'' encode its tree structure solely in array indices. It only creates new <code>PrioNode</code>s so users can have access to priorities after a <code>poll()</code>. That step has nothing to do with the structure of the heap. The heap is implicit in that the parent/children of a node are worked out from array indices (as seen in the siftXXX methods), rather than storing explicit references in each node.—[[User:Duyn\|duyn]] 11:34, 14 March 2010 (UTC)
	::Oh wait... Sorry, I misread the first bit of the code I was looking at, nevermind. --[[User:Rednaxela\|Rednaxela]] 15:01, 14 March 2010 (UTC)		::Oh wait... Sorry, I misread the first bit of the code I was looking at, nevermind. --[[User:Rednaxela\|Rednaxela]] 15:01, 14 March 2010 (UTC)
		+
		+	By the way, I just tried out your implicit d-ary heap with my tree. The result shows that 3-ary and 4-ary are roughly tied for speed, both notably better than 2-ary and 5-ary. Despite this, it's still just slightly slower than using my heap ([http://bitbucket.org/rednaxela/knn-benchmark/src/tip/ags/utils/dataStructures/BinaryHeap.java code link]) in my tree. --[[User:Rednaxela\|Rednaxela]] 22:41, 15 March 2010 (UTC)

← Older revision		Revision as of 15:01, 14 March 2010
Line 18:		Line 18:
	By the way, the title 'Implicit d-ary Heap' seems misleading to me. The d-ary heap you implement is not an implicit heap, an implicit heap that encodes it's tree structure solely in array indices instead of creating objects for each node. --[[User:Rednaxela\|Rednaxela]] 08:31, 14 March 2010 (UTC)		By the way, the title 'Implicit d-ary Heap' seems misleading to me. The d-ary heap you implement is not an implicit heap, an implicit heap that encodes it's tree structure solely in array indices instead of creating objects for each node. --[[User:Rednaxela\|Rednaxela]] 08:31, 14 March 2010 (UTC)
	:I am not sure I understand. The heap as presented ''does'' encode its tree structure solely in array indices. It only creates new <code>PrioNode</code>s so users can have access to priorities after a <code>poll()</code>. That step has nothing to do with the structure of the heap. The heap is implicit in that the parent/children of a node are worked out from array indices (as seen in the siftXXX methods), rather than storing explicit references in each node.—[[User:Duyn\|duyn]] 11:34, 14 March 2010 (UTC)		:I am not sure I understand. The heap as presented ''does'' encode its tree structure solely in array indices. It only creates new <code>PrioNode</code>s so users can have access to priorities after a <code>poll()</code>. That step has nothing to do with the structure of the heap. The heap is implicit in that the parent/children of a node are worked out from array indices (as seen in the siftXXX methods), rather than storing explicit references in each node.—[[User:Duyn\|duyn]] 11:34, 14 March 2010 (UTC)
		+	::Oh wait... Sorry, I misread the first bit of the code I was looking at, nevermind. --[[User:Rednaxela\|Rednaxela]] 15:01, 14 March 2010 (UTC)

← Older revision		Revision as of 11:34, 14 March 2010
Line 17:		Line 17:

	By the way, the title 'Implicit d-ary Heap' seems misleading to me. The d-ary heap you implement is not an implicit heap, an implicit heap that encodes it's tree structure solely in array indices instead of creating objects for each node. --[[User:Rednaxela\|Rednaxela]] 08:31, 14 March 2010 (UTC)		By the way, the title 'Implicit d-ary Heap' seems misleading to me. The d-ary heap you implement is not an implicit heap, an implicit heap that encodes it's tree structure solely in array indices instead of creating objects for each node. --[[User:Rednaxela\|Rednaxela]] 08:31, 14 March 2010 (UTC)
		+	:I am not sure I understand. The heap as presented ''does'' encode its tree structure solely in array indices. It only creates new <code>PrioNode</code>s so users can have access to priorities after a <code>poll()</code>. That step has nothing to do with the structure of the heap. The heap is implicit in that the parent/children of a node are worked out from array indices (as seen in the siftXXX methods), rather than storing explicit references in each node.—[[User:Duyn\|duyn]] 11:34, 14 March 2010 (UTC)

← Older revision		Revision as of 08:31, 14 March 2010
Line 15:		Line 15:
	::: Not at all.—[[User:Duyn\|duyn]] 06:20, 13 March 2010 (UTC)		::: Not at all.—[[User:Duyn\|duyn]] 06:20, 13 March 2010 (UTC)
	::: [Addendum: ] Although you may prefer to wait until activity on this tutorial dies down since all three trees are essentially in-development right now.—[[User:Duyn\|duyn]] 11:58, 13 March 2010 (UTC)		::: [Addendum: ] Although you may prefer to wait until activity on this tutorial dies down since all three trees are essentially in-development right now.—[[User:Duyn\|duyn]] 11:58, 13 March 2010 (UTC)
		+
		+	By the way, the title 'Implicit d-ary Heap' seems misleading to me. The d-ary heap you implement is not an implicit heap, an implicit heap that encodes it's tree structure solely in array indices instead of creating objects for each node. --[[User:Rednaxela\|Rednaxela]] 08:31, 14 March 2010 (UTC)

@@ Line 8: / Line 8: @@
 Nice tutorial work here! Quick question: Did you measure the effect of using the variance for splitting? I tried that before (I think last week) and didn't seem to see a performance advantage. --[[User:Rednaxela|Rednaxela]] 17:26, 12 March 2010 (UTC)
 : Not rigorously&mdash;I tried splitting half way along the widest dimension like you appear to do, but found that made search times worse.&mdash;[[User:Duyn|duyn]] 18:02, 12 March 2010 (UTC)
 Impressive speed with the final result there Duyn! I assume this is still comparing to the version of my tree in the old benchmark package? I'll have to compare it to my more up-to-date ones some time. That with the d-ary non-implicit tree also tempts me to to perhaps make a heap benchmark... :) --[[User:Rednaxela|Rednaxela]] 19:13, 12 March 2010 (UTC)

← Older revision		Revision as of 11:58, 13 March 2010
Line 13:		Line 13:
	:: Well as far as replicating, just in case you missed it, KNN.jar here has since been updated (though maybe not worth downloading yet, I messed up the inclusion of source, it's there but a bit weird). I'll update KNN.jar again both fixed and with your latest tree versions included if you don't mind. --[[User:Rednaxela\|Rednaxela]] 02:17, 13 March 2010 (UTC)		:: Well as far as replicating, just in case you missed it, KNN.jar here has since been updated (though maybe not worth downloading yet, I messed up the inclusion of source, it's there but a bit weird). I'll update KNN.jar again both fixed and with your latest tree versions included if you don't mind. --[[User:Rednaxela\|Rednaxela]] 02:17, 13 March 2010 (UTC)
	::: Not at all.—[[User:Duyn\|duyn]] 06:20, 13 March 2010 (UTC)		::: Not at all.—[[User:Duyn\|duyn]] 06:20, 13 March 2010 (UTC)
		+	::: [Addendum: ] Although you may prefer to wait until activity on this tutorial dies down since all three trees are essentially in-development right now.—[[User:Duyn\|duyn]] 11:58, 13 March 2010 (UTC)

← Older revision		Revision as of 06:20, 13 March 2010
Line 12:		Line 12:
	: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.—[[User:Duyn\|duyn]] 02:10, 13 March 2010 (UTC)		: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.—[[User:Duyn\|duyn]] 02:10, 13 March 2010 (UTC)
	:: Well as far as replicating, just in case you missed it, KNN.jar here has since been updated (though maybe not worth downloading yet, I messed up the inclusion of source, it's there but a bit weird). I'll update KNN.jar again both fixed and with your latest tree versions included if you don't mind. --[[User:Rednaxela\|Rednaxela]] 02:17, 13 March 2010 (UTC)		:: Well as far as replicating, just in case you missed it, KNN.jar here has since been updated (though maybe not worth downloading yet, I messed up the inclusion of source, it's there but a bit weird). I'll update KNN.jar again both fixed and with your latest tree versions included if you don't mind. --[[User:Rednaxela\|Rednaxela]] 02:17, 13 March 2010 (UTC)
		+	::: Not at all.—[[User:Duyn\|duyn]] 06:20, 13 March 2010 (UTC)

← Older revision		Revision as of 02:17, 13 March 2010
Line 11:		Line 11:
	Impressive speed with the final result there Duyn! I assume this is still comparing to the version of my tree in the old benchmark package? I'll have to compare it to my more up-to-date ones some time. That with the d-ary non-implicit tree also tempts me to to perhaps make a heap benchmark... :) --[[User:Rednaxela\|Rednaxela]] 19:13, 12 March 2010 (UTC)		Impressive speed with the final result there Duyn! I assume this is still comparing to the version of my tree in the old benchmark package? I'll have to compare it to my more up-to-date ones some time. That with the d-ary non-implicit tree also tempts me to to perhaps make a heap benchmark... :) --[[User:Rednaxela\|Rednaxela]] 19:13, 12 March 2010 (UTC)
	: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.—[[User:Duyn\|duyn]] 02:10, 13 March 2010 (UTC)		: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.—[[User:Duyn\|duyn]] 02:10, 13 March 2010 (UTC)
		+	:: Well as far as replicating, just in case you missed it, KNN.jar here has since been updated (though maybe not worth downloading yet, I messed up the inclusion of source, it's there but a bit weird). I'll update KNN.jar again both fixed and with your latest tree versions included if you don't mind. --[[User:Rednaxela\|Rednaxela]] 02:17, 13 March 2010 (UTC)

← Older revision		Revision as of 02:10, 13 March 2010
Line 10:		Line 10:

	Impressive speed with the final result there Duyn! I assume this is still comparing to the version of my tree in the old benchmark package? I'll have to compare it to my more up-to-date ones some time. That with the d-ary non-implicit tree also tempts me to to perhaps make a heap benchmark... :) --[[User:Rednaxela\|Rednaxela]] 19:13, 12 March 2010 (UTC)		Impressive speed with the final result there Duyn! I assume this is still comparing to the version of my tree in the old benchmark package? I'll have to compare it to my more up-to-date ones some time. That with the d-ary non-implicit tree also tempts me to to perhaps make a heap benchmark... :) --[[User:Rednaxela\|Rednaxela]] 19:13, 12 March 2010 (UTC)
−	: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.	+	: Yes, it's with the old one bundled in the package. I wanted people to be able to replicate the results.—[[User:Duyn\|duyn]] 02:10, 13 March 2010 (UTC)