我目前正在研究此类问题——分类、最近邻搜索——用于音乐信息检索。

您可能对 近似最近邻 ( ANN ) 算法感兴趣。这个想法是您允许算法返回足够 近的邻居
（可能不是最近的邻居）；这样做可以降低复杂性。你提到了 kd-tree ；这是一个例子。但正如你所说， kd-tree
在高维上效果不佳。事实上， 所有 当前的索引技术（基于空间分区）都退化为对足够高维度的线性搜索[1][2][3]。

在最近提出的 ANN 算法中，也许最流行的是 局部敏感散列 ( LSH )，它将高维空间中的一组点映射到一组 bin 中，即散列表
[1][3]。但与传统散列不同， 位置敏感 散列将 附近 的点放入同一个 bin。

LSH
有一些巨大的优势。首先，它很简单。您只需计算数据库中所有点的哈希值，然后从中创建一个哈希表。要查询，只需计算查询点的哈希，然后从哈希表中检索同一 bin
中的所有点。

其次，有一个严格的理论支持它的表现。可以看出，查询时间在数据库大小上是次 线性 的，即比线性搜索快。快多少取决于我们可以容忍多少近似值。

最后， LSH 与 的任何 Lp 范数兼容0 < p <= 2。因此，要回答您的第一个问题，您可以将 LSH
与欧几里德距离度量一起使用，或者您可以将其与曼哈顿 (L1) 距离度量一起使用。汉明距离和余弦相似度也有变体。

Malcolm Slaney 和 Michael Casey 在 2008 年为 IEEE 信号处理杂志撰写了一篇不错的概述 [4]。

LSH 似乎无处不在。你可能想试一试。

[1] Datar、Indyk、Immorlica、Mirrokni，“基于 p 稳定分布的局部敏感散列方案”，2004 年。

[2] Weber, Schek, Blott，“高维空间中相似性搜索方法的定量分析和性能研究”，1998 年。

[3] Gionis, Indyk, Motwani，“通过散列进行高维相似性搜索”，1999 年。

[4] 斯莱尼，凯西，“用于查找最近邻居的局部敏感散列”，2008 年。