rsk8332
March 31st, 2008, 01:09 AM
In my program, I pick a pivot p from a database S of strings, compute the median r of the distances of the string objects to p and then divide the objects into roughly equal-sized subsets S1 and S2 as follows:
S1={o ε S \{p}|d(p,o)<r} and
S2={o ε S \ {p}|d(p,o)>=r}
where d(p,o) is the distance of the database object o to pivot p.Thus, the objects in S1 are inside the ball of radius r around p, while the objects in S2 are outside this ball. Applying this rule recursively leads to a binary tree,where a pivot object is stored in each internal node, with the left and right subtrees corresponding to the subsets inside and outside the corresponding ball,respectively.
Given my problem, how can I call the function recursively to create the desired binary tree ?I would welcome somebody to outline the steps in the algorithm.
Any help much appreciated.
S1={o ε S \{p}|d(p,o)<r} and
S2={o ε S \ {p}|d(p,o)>=r}
where d(p,o) is the distance of the database object o to pivot p.Thus, the objects in S1 are inside the ball of radius r around p, while the objects in S2 are outside this ball. Applying this rule recursively leads to a binary tree,where a pivot object is stored in each internal node, with the left and right subtrees corresponding to the subsets inside and outside the corresponding ball,respectively.
Given my problem, how can I call the function recursively to create the desired binary tree ?I would welcome somebody to outline the steps in the algorithm.
Any help much appreciated.