有关搜索算法和数据结构的理论问题

Question

我有一个名为 M 的 N 维特征列表。我想在该列表中找到与查询特征 F 相匹配的特征。比较我的特征不是基于流行的指标（L1、L2 等）：例如，我的 A 和 B 之间的特征距离是将 A 与 B 的循环移位版本进行比较的结果。

我花了一些时间阅读有关搜索算法的内容，我得出的结论是，就我而言，不可能使用 KD 树。也许基于树的搜索不适合这里（？）。

我可以使用什么样的搜索算法来加快上述搜索速度？

快速搜索算法仅适用于流行的距离度量吗？

Answer 1

对于将直方图特征与循环移位进行比较的具体问题，您是对的，传统的基于树的方法（如 KD 树或球树）不适合。这些方法依赖于距离度量，其中距离函数很简单，并且不涉及诸如循环移位之类的转换。

1. 将循环移位问题转化为卷积问题。您可以使用快速傅立叶变换 (FFT) 高效地执行循环卷积。计算两个直方图的 FFT，执行 FFT 的逐元素乘法，然后应用逆 FFT。结果将是一个数组，其中峰值对应于最佳循环移位。
2. 不要将一个特征与另一个特征的所有可能的循环移位进行比较，而是生成该特征的“循环扩展”版本。
3. 使用散列技术根据每个特征的循环移位为每个特征创建索引。
4. 可以使用支持自定义距离函数的局部敏感哈希 (LSH) 或 ANN 库等技术。

使用基于 FFT 的循环卷积可能是最有效的方法。它将问题转换为更易于管理的形式并利用快速算法。