vantate point tree

vp tree 是一颗二叉树,他和kd tree有着一定的相似度,

树上信息

每一颗子树都要维护一个点集,对于每个节点,我们都维护一个距离d,然后将到该节点的距离小于d的点放到左儿子,其他的放到右儿子中。

vantate point

vantate point的选取是一个比较麻烦的事情,我们仔细想想都知道,这个点的选取肯定会影响算法,有一种处理办法是随机选取,这显然不是我们想要的。我们其实可以这样来处理,

Our algorithm constructs a set of vantage point candidates by random sampling,and then evaluates each of them.Evaluation is accomplished by extracting another sample,from which the median of $\prod_p(S)$,and a corresponding moment are estimated.Finally,based on these statistical images,the candidate with the largest moment is chosen.

这里的$\prod_p(S)$指的就是在该度量空间中点p和点s的距离,作者选取的statistical images是方差,我们可以从伪码中看出。

建树

和kd树一样,建树的过程是一致的,我们选出vantate point,然后递归左右建树

搜索

搜索的话,也是一样的,用结果剪枝即可

修改

这样的树不存在单旋这种方式,我们只能用替罪羊树套vantate point tree来实现

参考资料

Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces Peter N.Yianilos*

请我喝[茶]~( ̄▽ ̄)~*

fightinggg 微信支付

微信支付

fightinggg 支付宝

支付宝

fightinggg 贝宝

贝宝