# vantate point tree

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

## 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.

## 参考资料

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