我可以使用任意度量来搜索kd树吗?

如果您用给定度量的等效几何对象替换“超球体”,并测试每个超平面是否与此对象交叉,那么链接到的维基百科页面上描述的最近邻搜索过程当然可以概括为其他距离度量。

示例:如果您使用曼哈顿距离(即矢量分量中所有差异的绝对值之和),您的超球体将成为(多维)菱形。(这在2d中最容易可视化——如果你当前最近的邻居在远处 X 从查询点 磷 ,则不同超平面后面的任何近邻必须与宽度和高度为2x且位于中心的菱形相交。 磷 )。这可能会使超平面交叉测试更难编码或运行更慢,但一般原则仍然适用。

我不认为你和欧几里得距离有联系——正如J_Random_Hacker所说,你可能可以使用曼哈顿距离——但我很确定你和可以用笛卡尔坐标表示的几何体有联系。例如,您不能使用kd树来索引度量空间。