2020
Journal article
Open Access
Practical trade-offs for the prefix-sum problem
Pibiri G. E., Venturini R.
efficiency FOS: Computer and information sciences Computer Science - Data Structures and Algorithms performance evaluation Software prefix-sum SIMD Data Structures and Algorithms (cs.DS)
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.
Source: Software, practice & experience (Print) (2020). doi:10.1002/spe.2918
Publisher: Wiley Interscience,, Chichester , Regno Unito
[1] Jon Louis Bentley. 1977. Solutions to KleeâĂŹs rectangle problems. Unpublished manuscript (1977), 282-300.
[2] Jon Louis Bentley and Derick Wood. 1980. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. 7 (1980), 571-577.
[3] Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, and Søren Vind. 2018. Dynamic relative compression, dynamic partial sums, and substring concatenation. Algorithmica 80, 11 (2018), 3207-3224.
[4] Philip Bille, Anders Roy Christiansen, Nicola Prezza, and Frederik Rye Skjoldjensen. 2017. Succinct partial sums and fenwick trees. In International Symposium on String Processing and Information Retrieval. Springer, 91-96.
[5] Guy E. Blelloch. 1990. Prefix Sums and Their Applications. Synthesis of Parallel Algorithms (1990).
[6] Timothy M. Chan and Mihai Pătraşcu. 2010. Counting inversions, ofline orthogonal range counting, and related problems. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms . SIAM, 161-173.
[7] Intel Corporation. [last accessed June 2020]. The Intel Intrinsics Guide, https://software.intel.com/sites/landingpage/ IntrinsicsGuide/.
[8] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer.
[9] Paul F. Dietz. 1989. Optimal algorithms for list indexing and subset rank. In Workshop on Algorithms and Data Structures. Springer, 39-46.
[10] Peter M. Fenwick. 1994. A new data structure for cumulative frequency tables. Software: Practice and experience 24, 3 (1994), 327-336.
[11] Michael L. Fredman and Michael E. Saks. 1989. The Cell Probe Complexity of Dynamic Data Structures. In Proceedings of the 21-st Annual Symposium on Theory of Computing (STOC). 345-354.
[12] Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth. 2017. Handbook of discrete and computational geometry. CRC press. https://www.csun.edu/~ctoth/Handbook/HDCG3.html
[13] Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. 1997. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data mining and knowledge discovery 1, 1 (1997), 29-53.
[14] Haripriyan Hampapuram and Michael L. Fredman. 1998. Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM J. Comput. 28, 1 (1998), 1-9.
[15] Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung. 2011. Succinct data structures for searchable partial sums with optimal worst-case performance. Theoretical computer science 412, 39 (2011), 5176-5186.
[16] Paul-Virak Khuong and Pat Morin. 2017. Array layouts for comparison-based searching. Journal of Experimental Algorithmics (JEA) 22 (2017), 1-39.
[17] Stefano Marchini and Sebastiano Vigna. 2019. Compact Fenwick trees for dynamic ranking and selection. CoRR abs/1904.12370 (2019). arXiv:1904.12370 http://arxiv.org/abs/1904.12370
[18] Mihai Pătraşcu and Erik D. Demaine. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 4 (2006), 932-963.
[19] Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. 2001. Succinct dynamic data structures. In Workshop on Algorithms and Data Structures. Springer, 426-437.
[20] B. Ya Ryabko. 1992. A fast on-line adaptive code. IEEE transactions on information theory 38, 4 (1992), 1400-1404.
[21] Andrew C. Yao. 1985. On the complexity of maintaining partial sums. SIAM J. Comput. 14, 2 (1985), 277-288.
[2] Jon Louis Bentley and Derick Wood. 1980. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. 7 (1980), 571-577.
[3] Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, and Søren Vind. 2018. Dynamic relative compression, dynamic partial sums, and substring concatenation. Algorithmica 80, 11 (2018), 3207-3224.
[4] Philip Bille, Anders Roy Christiansen, Nicola Prezza, and Frederik Rye Skjoldjensen. 2017. Succinct partial sums and fenwick trees. In International Symposium on String Processing and Information Retrieval. Springer, 91-96.
[5] Guy E. Blelloch. 1990. Prefix Sums and Their Applications. Synthesis of Parallel Algorithms (1990).
[6] Timothy M. Chan and Mihai Pătraşcu. 2010. Counting inversions, ofline orthogonal range counting, and related problems. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms . SIAM, 161-173.
[7] Intel Corporation. [last accessed June 2020]. The Intel Intrinsics Guide, https://software.intel.com/sites/landingpage/ IntrinsicsGuide/.
[8] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. 2008. Computational geometry: algorithms and applications, 3rd Edition. Springer.
[9] Paul F. Dietz. 1989. Optimal algorithms for list indexing and subset rank. In Workshop on Algorithms and Data Structures. Springer, 39-46.
[10] Peter M. Fenwick. 1994. A new data structure for cumulative frequency tables. Software: Practice and experience 24, 3 (1994), 327-336.
[11] Michael L. Fredman and Michael E. Saks. 1989. The Cell Probe Complexity of Dynamic Data Structures. In Proceedings of the 21-st Annual Symposium on Theory of Computing (STOC). 345-354.
[12] Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth. 2017. Handbook of discrete and computational geometry. CRC press. https://www.csun.edu/~ctoth/Handbook/HDCG3.html
[13] Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. 1997. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data mining and knowledge discovery 1, 1 (1997), 29-53.
[14] Haripriyan Hampapuram and Michael L. Fredman. 1998. Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM J. Comput. 28, 1 (1998), 1-9.
[15] Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung. 2011. Succinct data structures for searchable partial sums with optimal worst-case performance. Theoretical computer science 412, 39 (2011), 5176-5186.
[16] Paul-Virak Khuong and Pat Morin. 2017. Array layouts for comparison-based searching. Journal of Experimental Algorithmics (JEA) 22 (2017), 1-39.
[17] Stefano Marchini and Sebastiano Vigna. 2019. Compact Fenwick trees for dynamic ranking and selection. CoRR abs/1904.12370 (2019). arXiv:1904.12370 http://arxiv.org/abs/1904.12370
[18] Mihai Pătraşcu and Erik D. Demaine. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 4 (2006), 932-963.
[19] Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. 2001. Succinct dynamic data structures. In Workshop on Algorithms and Data Structures. Springer, 426-437.
[20] B. Ya Ryabko. 1992. A fast on-line adaptive code. IEEE transactions on information theory 38, 4 (1992), 1400-1404.
[21] Andrew C. Yao. 1985. On the complexity of maintaining partial sums. SIAM J. Comput. 14, 2 (1985), 277-288.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:435491,
title = {Practical trade-offs for the prefix-sum problem},
author = {Pibiri G. E. and Venturini R.},
publisher = {Wiley Interscience,, Chichester , Regno Unito},
doi = {10.1002/spe.2918 and 10.48550/arxiv.2006.14552},
journal = {Software, practice \& experience (Print)},
year = {2020}
}CNR authorsLaboratories
0000-0003-0724-7092
