我目前正在研究此类问题-分类，最近邻居搜索-以获取音乐信息。

您可能对 近似最近邻 （ ANN ）算法感兴趣。这个想法是让算法允许返回足够 近的邻居
（也许不是最近的邻居）。这样可以减少复杂性。您提到了 kd-tree ；那是一个例子。但是正如您所说， kd-tree
在高维度上效果不佳。实际上， 所有 当前的索引技术（基于空间划分）都降级为对足够高的尺寸进行线性搜索[1] [2] [3]。

在最近提出的 ANN 算法中，也许最流行的是 局部敏感散列 （ Locality-Sensitive Hashing ，
LSH ），它将高维空间中的一组点映射到一组bin中，即哈希表[1] [3]。但是与传统的哈希不同，对 位置敏感的 哈希将 附近的
点放置在同一容器中。

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

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

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

Malcolm Slaney和Michael Casey在2008年为IEEE Signal Processing Magazine撰写了不错的综述[4]。

LSH 似乎已在所有地方得到应用。您可能需要尝试一下。

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

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

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

[4] Slaney，Casey，“用于查找最近邻居的局部敏感哈希”，2008年。