Orchid XP v7 nous apporta ses lumieres en ce 2007/11/03 18:20:
> Warp wrote:
> 
>> http://en.wikipedia.org/wiki/R-tree
>> http://en.wikipedia.org/wiki/Kd_tree
> 
> Both of these look potentially useful quite useful. (Certainly O(log n) 
> lookup sounds much more fun than O(n) lookup!) Both articles talk about 
> finding THE nearest point, but it looks easy to modify it to find 
> several nearby points.
> 
> It seems that in both cases, ensuring the tree is nicely balanced is 
> utterly critical to best performance. Since I'm going to be adding 
> points to the tree all the time, clearly I need to think carefully about 
> this part.
> 
> Anyway, I have some stuff to play with now... thanks.
A possible way to get a, more, balanced tree is to seed it with 3 dummy values. 
One for the tree root, and 2 for the first branches, one to each "sides" of the 
initial one. The first is set to the expected average value of the possible 
points. The 2 next are chosen halfway between that value and the expected 
extreme values.
Easier done when you know that all your samples will be contained within a given 
domain, and what will be the more probable distribution.

-- 
Alain
-------------------------------------------------
Never frown, even when you are sad, because you never know who is falling in 
love with your smile.

Post a reply to this message