c++ - 用于密集数据集 4D vector 快速范围搜索的数据结构

Question

我有数百万个与任意值关联的非结构化 3D vector - 构成一组 4D vector 。为了更容易理解:我有与数十万个 3D vector 相关联的 unixtime 戳记。而且我有很多时间戳，构成了一个非常大的数据集；超过 3000 万个 vector 。

我需要搜索特定时间戳的特定数据集。

假设我有以下数据:

对于时间戳1407633943:

• (0, 24, 58, 1407633943)

• (9, 2, 59, 1407633943)

  ...

对于时间戳1407729456:

• (40, 1, 33, 1407729456)

• (3, 5, 7, 1407729456)

  ...

等等等等

我希望按照以下方式进行非常快速的查询:

查询示例 1:

给我之间的 vector :

X > 4 && X < 9 && Y > -29 && Y < 100 && Z > 0.58 && Z < 0.99

给我这些 vector 的列表，这样我就可以找到时间戳。

查询示例 2:

给我之间的 vector :

X > 4 && X < 9 && Y > -29 && Y < 100 && Z > 0.58 && Z < 0.99 && W(时间戳)= 1407729456

到目前为止，我已经使用 SQLite 完成任务，但即使在列索引之后，每个查询也需要 500 毫秒到 7 秒。我正在寻找每个查询解决方案 50 毫秒到 200 毫秒之间的某个时间。

我可以使用什么样的结构或技术来加快查询速度？

谢谢。

Answer 1

kd-trees 在这里很有用。 kd 树中的范围搜索是一个众所周知的问题。当然，一个查询的时间复杂度取决于输出大小(在最坏的情况下，如果所有 vector 都适合，则将遍历所有树)。但它的平均运行速度非常快。