Re:Ask HN: Fast sampling and update of weighted items? (data...
by nkurz on Wednesday March 25, 2009 @05:48PM
(#532488)
I don't think I'm quite understanding your algorithm. When you say "choose left or right", do you mean to choose randomly between the branches with probability equal to the ratio of the weights of the trees? So that each sample requires log(n) random numbers before you reach a leaf? Or do you mean something else?
[ Parent
| on HN ]
Re:Ask HN: Fast sampling and update of weighted items? (data...
by bravura on Wednesday March 25, 2009 @06:08PM
(#532514)
You know the sum of the weights.
Sample a random number between 0 and sum.
Then, use this value to guide your search in the tree.
For example, if the left branch has weight 30 and the right branch has weight 50, the total weight is 80.
If I pick 40, then I am going down the right branch.
At the next child, if the left branch has weight 12 and the right branch has weight 38, the left branch spans 30-42 and the right branch spans 42-80. So you follow the left branch, because you want 40.
Re:Ask HN: Fast sampling and update of weighted items? (data...
by praptak on Wednesday March 25, 2009 @06:10PM
(#532521)
Basically, yes - branches are chosen with probabilities proportional to their weights, but you can achieve that with just one random float.
Just pick a random x from [0, sum of weights in the tree], then find a node n, such that sum of weights S to the left of n is no more than x and S+weight(n)>=x.