cashmere

在线空间搜索树

开发中。文档可能不完整，可能存在错误。

动机

存在许多库实现了k维空间划分树；底层算法相对简单且应用广泛。然而，由于各种原因，在其他常见数据结构中通常被认为理所当然的一些特性却很少见到

• 可变性：许多k-d树实现选择一次性构建、多次查询的设计。初始化后，结构中删除或添加数据通常是不可能的。
• 平衡性：在实现了可变性的结构中，平衡保证通常不存在。可能需要提供外部边界，超出该边界，树要么严重不平衡，要么不接受数据。数据中的高密度区域可能不可避免地具有更大的树深度，并且数据首先以任何方式病理排序插入的树可能会退化到二次性能。
• 其他约束
  • 大多数实现接受有限数量的数据类型，并在有限数量的维度中运行。
  • 许多（如果不是大多数）允许修改的实现需要知道插入的值和相关的数据来更改它，强制在某些用例中需要一个次要的数据结构。
  • 即使是世界级的k-d树实现也可能受到看似奇特的限制，例如无法处理单个轴对齐平面上共存太多的项。

这是作者试图解决所有这些问题以及更多问题的尝试。

目标

• 在线可变性：高效且易于修改值。结构应在每次修改之间立即可用于搜索。
• 性能保证：以任何顺序增量插入数据应相对较快，并且不会导致搜索性能下降。不需要在事先知道包含数据的边界框，并且任何值组合或重复都不会导致崩溃或不可用/无效的结构。结构也不应受大小限制：理想情况下，应该很少需要调整性能的旋钮，并且它们不应该与最大容量进行权衡。
• 速度：理想情况下，此处所述的数据结构在搜索性能方面应与世界级搜索树相媲美，即使在增量构建的情况下。在突变期间的维护成本与搜索性能之间的权衡应该是可定制的。截至本文撰写时，总体性能约为最佳竞争者（kiddo）在合理非病态基准下的50%，混合突变和最近邻搜索以及数据分布良好。即将发布的修订和重写可能会显著缩小这一差距。
• 灵活性
  • 接受类型 -- 此处所述的结构操作的是特性，而不是特定的预定义数值类型。任何自定义类型都可以，包括具有异构类型轴的类型。目前，所需的特性已为所有原始类型、str、std::time类型、其数组、其引用以及最多6维度的异构元组定义。实现任何尚未工作的值类型应几乎微不足道。
  • 能力 -- 此处所述的结构可以用统计信息进行参数化，这些是可以自定义的结构，可以聚合树中每个部分找到的值（例如边界框），从而增强可以有效地搜索的项目类型以及它们可以搜索的方式。这与灵活的访问者模式查询API相结合，几乎可以执行任何类型的查询：精确最近搜索、容忍误差的最近和k-最近搜索、半径或区域内的搜索、碰撞和重叠搜索：将提供基本实现（待定），如果不存在，则可以创建。

非目标

• 快速序列化/反序列化： kiddo + rkyv似乎已经占据了这一领域。查询冷内存映射文件是一种优化目标，与高性能可变性不同，并且目前这不是优先事项，也不清楚是否可以同时做得很好。
• 内存效率：虽然这些结构可以相当高效，并且将在物品被删除时释放内存，但它确实使用与存储的项数成比例的堆分配，并且在这些项之间保持指针。
• 突破性的算法界限： 平衡 k-d树通常已知修改的成本为O(log^2 n)。性能不同的替代方案设计得很奇怪，权衡得也很奇怪（参见“分割k-d树”，查询可能成本为O(sqrt n)）。或者，它们只是以理想分布的输入来表述其性能特征——诚然，这通常是情况。这个crate使用了一种scapegoat平衡的变体来对抗最坏情况的不平衡（因此得名！）这也意味着性能保证是摊销的，因此虽然通过平衡避免了退化情况，但可能没有理想的延迟界限（因为重新平衡可能偶尔很昂贵，包括完整重建）。
• 针对每种类型的理想向量化：至少到目前为止，我们将尽力以诱人的方式排列数据，然后依赖编译器来完成剩余的工作。
• 无需LTO即可实现出色性能：别忘了打开thin-LTO！