我有数百万个与任意值关联的非结构化3D向量-构成一组4D向量。为了使它更容易理解:我有与成千上万的3D向量关联的unixtime标记。而且我有很多时间戳,它们构成了非常大的数据集。超过3000万个向量。
我需要搜索特定时间戳的特定数据集。
所以可以说我有以下数据:
对于时间戳1407633943:
(0、24、58、1407633943)
(9,2,59,1407633943)
...
对于时间戳1407729456:
(40,1,33,1407729456)
(3,5,7,1407729456)
...
等
我希望按照以下方式进行快速查询:
查询示例1:
给我之间的向量:
X> 4 && X -29 && Y 0.58 && Z
给我这些矢量的清单,以便找到时间戳记。
查询示例2:
给我之间的向量:
X> 4 && X -29 && Y 0.58 && Z
到目前为止,我已经使用SQLite来完成任务,但是即使在对列进行索引之后,该操作也需要500毫秒-每个查询7 s。我正在寻找每个查询解决方案50ms-200ms之间的某个地方。
我可以使用哪种结构或技术来加快查询速度?
谢谢。
最佳答案
kd-trees在这里可能会有所帮助。在kd树中进行范围搜索是一个众所周知的问题。当然,一个查询的时间复杂度取决于输出大小(在最坏的情况下,如果所有向量都适合,则将遍历所有树)。但平均而言,它可以非常快地运行。