我刚刚完成了执行快速最近邻居搜索的kd树。我有兴趣尝试使用除欧几里得距离以外的其他距离度量标准。我对kd- tree的理解是，如果度量标准是非欧几里得，则不能保证快速的kd- tree搜索能够提供准确的搜索，这意味着如果我想尝试，可能需要实现新的数据结构和搜索算法为我的搜索列出新指标。
我有两个问题：
您链接到的Wikipedia页面上描述的最近邻居搜索过程可以肯定地推广到其他距离度量，只要您用给定度量的等效几何对象替换“超球”，并测试每个超平面与该对象的交叉点即可。
例如：如果您改用曼哈顿距离（即矢量分量中所有差的绝对值的总和），则超球面将变成（多维）菱形。（这最容易以2D形式显示-如果当前最近的邻居与查询点 p的 距离为 x ，则在另一个超平面之后的任何更近的邻居都必须与宽度和高度为2x且以 p 为中心的菱形相交） 。这可能会使超平面交叉测试更难编码或运行较慢，但是一般原理仍然适用。
