The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data

摘要

This paper is about metric data structures in high-dimensional or non-Euclidean space that permit cached sufficient statistics accel-erations of learning algorithms. It has recently been shown that for less than about 10 dimensions, decorating kd-trees with additional "cached sufficient statis-tics" such as first and second moments and contingency tables can provide satisfying ac-celeration for a very wide range of statistical learning tasks such as kernel regression, lo-cally weighted regression, k-means clustering, mixture modeling and Bayes Net learning.