# KDTree

## KDTree的问题

KDTree的方法对于低维度近邻搜索非常快, 当D增长到很大时, 效率快速变低. 因为需要构建一个非常深的树, 并且每次回溯都要回溯非常多的节点.

因为对于高维向量, 单个维度对两个向量整体的距离是影响较小的, 因此与最初搜索到的叶子节点形成的超球面, 大概率会与很多超平面有交集, 因此回溯的次数会随着维度的增加快速增加.

一般来说, 要在维度D的数据集上取得较高的搜索效率, 要求数据集中数据的数量N要满足$$N \gg 2^D$$. 或使用KDBall来代替.

## 参考资料

* [KD Tree的原理及Python实现](https://zhuanlan.zhihu.com/p/45346117)
* [k-d tree算法原理及实现](https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/sou-suo-tui-jian/tui-jian-suan-fa/ann/kdtree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.