SRS:SRS - 具有微小索引的高维欧几里德空间中的快速近似最近邻搜索

SRS - 具有微小索引的高维欧几里德空间中的快速近似最近邻搜索 SRS-Mem 是一个 C++ 程序，用于在主存中的高维欧几里德空间中执行近似最近邻搜索。 当前的实现改编自我们的。 主要的修改是使用内存中的多维索引（而不是论文中的 R 树），因为通常情况下我们的索引很小并且可以容纳在主内存中。 目前，该索引由于其强大的理论保证，是的修改版； 尽管如此，任何支持增量精确k NN 搜索的多维索引都可以使用！ 特征 保证成功概率 从理论上讲，即使在最坏的情况下，SRS 也能保证以用户指定的概率返回查询的c近似最近邻。 例如，许多启发式方法不会在某些硬数据集（例如，由gen_hard_data生成的数据集）上返回近邻。 SRS 算法还有其他几个独特的理论特性。 SRS的top- k版本保证以恒定概率返回c - k-近似最近邻（而以前的方法不能保证k >1），而SRS-1算法保证返回最近邻（即c