Sparse prefix sums: Constanttime range sum queries over sparse multidimensional data cubes
Prefix sums are a powerful technique to answer rangesum queries over multidimensional arrays in O(1) time by looking up a constant number of values in an array of size O(N), where N is the number of cells in the multidimensional array. However, the technique suffers from O(N) update and storage costs. Relative prefix sums address the high update costs by partitioning the array into blocks, thereby breaking the dependency between cells. In this paper, we present sparse prefix sums that exploit data sparsity to reduce the high storage costs of relative prefix sums. By building upon relative prefix sums, sparse prefix sums achieve the same update complexity as relative prefix sums. The authors of relative prefix sums erroneously claimed that the update complexity is O(N) for any number of dimensions. We show that this claim holds only for two dimensions, whereas the correct complexity for an arbitrary number of d dimensions is O(N [Formula presented] ). To reduce the storage costs, the sparse prefix sums technique exploits sparsity in the data and avoids to materialize prefix sums for empty rows and columns in the data grid; instead, lookup tables are used to preserve constant query time. Sparse prefix sums are the first approach to achieve O(1) query time with sublinear storage costs for rangesum queries over sparse lowdimensional arrays. A thorough experimental evaluation shows that the approach works very well in practice. On the tested realworld data sets the storage costs are reduced by an order of magnitude with only a small overhead in query time, thus preserving microsecondfast query answering.
URI
http://dx.doi.org/10.1016/j.is.2018.06.009https://www.sciencedirect.com/science/article/pii/S0306437918301017?via=ihub
http://hdl.handle.net/10863/10206
Collections
Related items
Showing items related by title, author, creator and subject.

Variable block algebraic recursive multilevel solver (VBARMS) for sparse linear systems
Carpentieri B; Liao J; Sosonkina M (Bader M [and others], 2014)We present and discuss the parallel implementation of a multielimination incomplete LU factorization method for solving sparse linear systems. The proposed solver exploits any available block structure during the ... 
VBARMS: A variable block algebraic recursive multilevel solver for sparse linear systems
Carpentieri B; Liao J; Sosonkina M (2014)Sparse matrices arising from the solution of systems of partial differential equations often exhibit a perfect block structure, meaning that the nonzero blocks in the sparsity pattern are fully dense (and typically small), ... 
Sparse Prefix Sums
Shekelyan M; Dignös A; Gamper J (Springer, 2017)The prefix sum approach is a powerful technique to answer rangesum queries over multidimensional arrays in constant time by requiring only a few lookups in an array of precomputed prefix sums. In this paper, we propose ...