{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:20Z","timestamp":1759637660709,"version":"3.32.0"},"publisher-location":"Boston, MA","reference-count":29,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387346335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-0-387-34735-6_12","type":"book-chapter","created":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T18:32:32Z","timestamp":1166121152000},"page":"103-114","source":"Crossref","is-referenced-by-count":4,"title":["An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Brodnik","sequence":"first","affiliation":[]},{"given":"Johan","family":"Karlsson","sequence":"additional","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Nilsson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"G. M. Adelson-Velskii and E. M. Landis. An algorithm for the organization of information. In Soviet Math. Doclady 3, pages 1259\u20131263, 1962."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal and Ashok K. Chandra. Virtual memory algoithms (preliminary version). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 173\u2013185. ACM Press, May 2\u20134 1988.","DOI":"10.1145\/62212.62227"},{"issue":"1","key":"12_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"P. Beame and F. E. Fich. Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences, 65(1):38\u201372, 2002.","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Fredrik Bengtsson and Jingsen Chen. Space-efficient range-sum queries in OLAP. In Yahiko Kambayashi, Mukesh Mohania, and Wolfram W\u00f6\u00df, editors, Data Ware-housing and Knowledge Discovery: 6th International Conference DaWaK, volume 3181 of Lecture Notes in Computer Science, pages 87\u201396. Springer, September 2004.","DOI":"10.1007\/978-3-540-30076-2_9"},{"key":"12_CR5","volume-title":"PhD thesis","author":"A. Brodnik","year":"1995","unstructured":"Andrej Brodnik. Searching in Constant Time and Minimum Space (Minin\u00c6 Res Magni Momenti Sunt). PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1995. (Also published as technical report CS-95-41.)."},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.jss.2004.09.002","volume":"78","author":"A. Brodnik","year":"2005","unstructured":"Andrej Brodnik, Svante Carlsson, Michael L. Fredman, Johan Karlsson, and J. Ian Munro. Worst case constant time priority queue. Journal of System and Software, 78(3):249\u2013256, December 2005.","journal-title":"Journal of System and Software"},{"key":"12_CR7","unstructured":"Andrej Brodnik and John Iaeono. Dynamic predecessor queries. Unpublished manuscript, 2006."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Arash Farzan and J. Ian Munro. Succinct representation of finite abelian groups. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, Lecture Notes in Computer Science. Springer, 2006. To appear.","DOI":"10.1145\/1145768.1145788"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"M. L. Fredman","year":"1982","unstructured":"Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. Journal of the ACM, 29(1):250\u2013260, January 1982.","journal-title":"Journal of the ACM"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 345\u2013354. ACM Press, May 14\u201317 1989.","DOI":"10.1145\/73007.73040"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Matteo Prigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-oblivious algorithms. In IEEE, editor, 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 285\u2013297. IEEE Computer Society, IEEE Computer Society, October 17\u201319 1999.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Steven P. Geffner, Divyakant Agrawal, Amr El Abbadi, and T. Smith. Relatve prefix sums: An efficient approach for querying dynamic OLAP data cubes. In Proceedings of the 15th International Conference on Data Engineering, pages 328\u2013335, 1999.","DOI":"10.1109\/ICDE.1999.754948"},{"key":"12_CR13","unstructured":"Steven P. Ceffner, Mirek Riedewald, Divyakant Agrawal, and Amr El Abbadi. Data cubes in dynamic environments. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, pages 31\u201340, 1999."},{"issue":"1","key":"12_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539795291598","volume":"28","author":"H. Harnpapuram","year":"1998","unstructured":"Haripriyan Harnpapuram and Michael L. Fredman. Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM Journal on Computing, 28(1):1\u20139, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"C. Ho, R. Agrawal, N. Megiddo, and R. Srikant. Range queries in OLAP data cubes. In Proceedings ACM SIGMOD International Conference on Management of Data, pages 73\u201388, 1997.","DOI":"10.1145\/253262.253274"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung. Succinct data structure for searchable partial sums. In Toshihide Ibaraki, Naoki Katoh, and Hirotaka Ono, editors, Algorithms and Computation\u2014ISAAC 2003, 14th International Symposium, volume 2906 of Lecture Notes in Computer Science, pages 505\u2013516. Springer, December 2003.","DOI":"10.1007\/978-3-540-24587-2_52"},{"key":"12_CR17","series-title":"volume A: Algorithms and Complexity","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"Richard M. Karp and Vijaya Ramachandran. Parallel algorithms for sharedmemeory machines. In van Leeuwen [28]. chapter 17, pages 869\u2013941."},{"key":"12_CR18","unstructured":"Roni Leben, Marijan Mileti\u0107, Marjan \u0160pegel, Andrej Trost, Andrej Brodnik, and Johan Karlsson. Design of high performance memory module on PC100. In Proceedings Electrotechnical and Computer Science Conference, pages 75\u201378, Slovenia, 1999."},{"issue":"24","key":"12_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.jda.2004.08.009","volume":"3","author":"K. Lemstr\u00f6m","year":"2005","unstructured":"Kjell Lemstr\u00f6m, Gonzalo Navarro, and Yoan Pinzon. Practical algorithms for transposition-invariant string-matching. Journal of Discrete Algorithms, 3(24): 267\u2013292, 2005.","journal-title":"Journal of Discrete Algorithms"},{"key":"12_CR20","unstructured":"Anany Levitin. Introduction to The Design & Analysis of Algorithms. Pearson Education Inc., Addison-Wesley, 2003."},{"key":"12_CR21","volume-title":"Lic. thesis","author":"A. Nilsson","year":"2004","unstructured":"Andreas Nilsson. Data Structures for Bandwidth Reservation and Quiality of Service on the Internet. Lic. thesis, Department of Computer Science and Electrical Engineering, Lule\u00e5 University of Technology, Lule\u00e5, Sweden, April 2004."},{"key":"12_CR22","unstructured":"W. Paul and J. Simon. Decision trees and random access machines. In Proc. Int\u2019l. Symp. on Logic and Algorithmic, pages 331\u2013340, Zurich, 1980."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct dynamic data structure. In Algorithms and Data Structures, 7th International Workshop, volume 2125 of Lecture Notes in Computer Science, pages 426\u2013437. Springer, 8\u201310 August 2001.","DOI":"10.1007\/3-540-44634-6_39"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Mirek Riedewald, Divyakant Agrawal, and Amr El Abbadi. Flexible data cubes for online aggregation. In Database Theory\u2014ICDT 2001, 8th International Conference, London, UK, January 4\u20136, 2001, Proceedings, volume 1973 of Lecture Notes in Computer Science, pages 159\u2013173, 2001.","DOI":"10.1007\/3-540-44503-X_11"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Mirek Riedewald, Divyakant Agrawal, Amr El Abbadi, and Renato Pajarola. Space-efficient data cubes for dynamic environments. In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWak), pages 24\u201333, 2000.","DOI":"10.1007\/3-540-44466-1_3"},{"key":"12_CR26","series-title":"volume A: Algorithms and Complexity","first-page":"943","volume-title":"Handbook of Theoretical Computer Science","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant. General purpose parallel architectures. In van Leeuwen [28]. chapter 18, pages 943\u2013971."},{"key":"12_CR27","series-title":"volume A: Algorithms and Complexity","first-page":"3","volume-title":"Handbook of Theoretical Computer Science","author":"P. Erode Boas van","year":"1990","unstructured":"Peter van Erode Boas. Machine models and simulations. In van Leeuwen [28]. chapter 1, pages 3\u201366."},{"key":"12_CR28","series-title":"volume A: Algorithms and Complexity","volume-title":"Handbook of Theoretical Computer Science","author":"J. Leeuwen van","year":"1990","unstructured":"Jan van Leeuwen, editor. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. Elsevier\/MIT Press, Amsterdam, 1990."},{"issue":"2","key":"12_CR29","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A. C. Yao","year":"1985","unstructured":"Andrew C. Yao. On the complexity of maintaining partial sums. SIAM Journal on Computing, 14(2):277\u2013288, May 1985.","journal-title":"SIAM Journal on Computing"}],"container-title":["IFIP International Federation for Information Processing","Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-34735-6_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T10:22:38Z","timestamp":1736677358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-34735-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387346335"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-34735-6_12","relation":{},"subject":[]}}