Sparse prefix sums: Constant-time range sum queries over sparse multidimensional data cubes

作者：

Highlights：

• Proof of correct update complexity for relative prefix sums.

• Reduced storage costs of sparse prefix sums for more dimensions.

• Experiments on real-world datasets up to seven dimensions.

摘要

•Proof of correct update complexity for relative prefix sums.•Reduced storage costs of sparse prefix sums for more dimensions.•Experiments on real-world datasets up to seven dimensions.

论文关键词：

论文评审过程：Received 28 February 2018, Accepted 29 June 2018, Available online 3 July 2018, Version of Record 20 March 2019.

论文官网地址：https://doi.org/10.1016/j.is.2018.06.009