邻近点的覆盖树

我们提出了一种树数据结构，适用于在一般n点度量空间中快速执行最近邻操作（数据集包含n个点）。该数据结构需要O(n)的空间量，不管度量的结构如何，但保持了导航网络的所有性能特性（Krauthgamer & Lee, 2004b）。如果点集具有有界扩展常数c，该常数是内在维度的度量，如(Karger & Ruhl, 2002)中定义，覆盖树数据结构可以在O(c^6 n log n)的时间内构建。此外，最近邻查询只需要对n的对数时间，特别是O(c^12 log n)的时间。我们的实验结果显示，在自然机器学习数据集上，与暴力搜索相比，速度提升从一个数量级到多个数量级不等。