{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T01:40:10Z","timestamp":1750815610140,"version":"3.41.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319669168"},{"type":"electronic","value":"9783319669175"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66917-5_9","type":"book-chapter","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T07:14:52Z","timestamp":1503558892000},"page":"120-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sparse Prefix Sums"],"prefix":"10.1007","author":[{"given":"Michael","family":"Shekelyan","sequence":"first","affiliation":[]},{"given":"Anton","family":"Dign\u00f6s","sequence":"additional","affiliation":[]},{"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,25]]},"reference":[{"key":"9_CR1","unstructured":"Facebook Connectivity Lab, Center for International Earth Science Information Network - CIESIN - Columbia University 2016. High Resolution Settlement Layer (HRSL). Source imagery for HRSL $$\\copyright $$ 2016 DigitalGlobe. http:\/\/www.ciesin.columbia.edu\/data\/hrsl\/. Accessed 01 Mar 2017"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume":"223","author":"PK Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J., et al.: Geometric range searching and its relatives. Contemp. Math. 223, 1\u201356 (1999)","journal-title":"Contemp. Math."},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-540-30076-2_9","volume-title":"Data Warehousing and Knowledge Discovery","author":"F Bengtsson","year":"2004","unstructured":"Bengtsson, F., Chen, J.: Space-efficient range-sum queries in OLAP. In: Kambayashi, Y., Mohania, M., W\u00f6\u00df, W. (eds.) DaWaK 2004. LNCS, vol. 3181, pp. 87\u201396. Springer, Heidelberg (2004). doi:10.1007\/978-3-540-30076-2_9"},{"key":"9_CR4","unstructured":"Chan, C.Y., Ioannidis, Y.E.: Hierarchical prefix cubes for range-sum queries. In: VLDB, pp. 675\u2013686 (1999)"},{"issue":"3","key":"9_CR5","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9_CR7","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0167-9236(03)00003-4","volume":"37","author":"S Chun","year":"2004","unstructured":"Chun, S., Chung, C., Lee, S.: Space-efficient cubes for OLAP range-sum queries. Decis. Support Syst. 37(1), 83\u2013102 (2004)","journal-title":"Decis. Support Syst."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry","author":"M de Berg","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational geometry. Computational Geometry, pp. 1\u201317. Springer, Heidelberg (2000). doi:10.1007\/978-3-662-04245-8_1"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/3-540-46439-5_17","volume-title":"Advances in Database Technology \u2014 EDBT 2000","author":"S Geffner","year":"2000","unstructured":"Geffner, S., Agrawal, D., Abbadi, A.: The dynamic data cube. In: Zaniolo, C., Lockemann, P.C., Scholl, M.H., Grust, T. (eds.) EDBT 2000. LNCS, vol. 1777, pp. 237\u2013253. Springer, Heidelberg (2000). doi:10.1007\/3-540-46439-5_17"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Geffner, S., Agrawal, D., El Abbadi, A., Smith, T.R.: Relative prefix sums: an efficient approach for querying dynamic OLAP data cubes. In: ICDE, pp. 328\u2013335 (1999)","DOI":"10.1109\/ICDE.1999.754948"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Ho, C., Agrawal, R., Megiddo, N., Srikant, R.: Range queries in OLAP data cubes. In: SIGMOD Conference, pp. 73\u201388 (1997)","DOI":"10.1145\/253262.253274"},{"issue":"2","key":"9_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ipl.2004.05.008","volume":"92","author":"H Kang","year":"2004","unstructured":"Kang, H., Min, J., Chun, S., Chung, C.: A compression method for prefix-sum cubes. Inf. Process. Lett. 92(2), 99\u2013105 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0169-023X(00)00007-0","volume":"34","author":"W Liang","year":"2000","unstructured":"Liang, W., Wang, H., Orlowska, M.E.: Range queries in dynamic OLAP data cubes. Data Knowl. Eng. 34(1), 21\u201338 (2000)","journal-title":"Data Knowl. Eng."},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Riedewald, M., Agrawal, D., El Abbadi, A.: pCUBE: update-efficient online aggregation with progressive feedback and error bounds. In: SSDBM, pp. 95\u2013108 (2000)","DOI":"10.1109\/SSDM.2000.869781"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Riedewald, M., Agrawal, D., El Abbadi, A.: Dynamic multidimensional data cubes. In: Multidimensional Databases, pp. 200\u2013221 (2003)","DOI":"10.4018\/978-1-59140-053-0.ch007"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-44466-1_3","volume-title":"Data Warehousing and Knowledge Discovery","author":"M Riedewald","year":"2000","unstructured":"Riedewald, M., Agrawal, D., Abbadi, A.E., Pajarola, R.: Space-efficient data cubes for dynamic environments. In: Kambayashi, Y., Mohania, M., Tjoa, A.M. (eds.) DaWaK 2000. LNCS, vol. 1874, pp. 24\u201333. Springer, Heidelberg (2000). doi:10.1007\/3-540-44466-1_3"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S1571-0661(04)00313-5","volume":"61","author":"T Takaoka","year":"2002","unstructured":"Takaoka, T.: Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electr. Notes Theor. Comput. Sci. 61, 191\u2013200 (2002)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Viola, P.A., Jones, M.J.: Rapid object detection using a boosted cascade of simple features. In: CVPR (1), pp. 511\u2013518 (2001)","DOI":"10.1109\/CVPR.2001.990517"}],"container-title":["Lecture Notes in Computer Science","Advances in Databases and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66917-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T01:12:59Z","timestamp":1750813979000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-66917-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319669168","9783319669175"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66917-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"25 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}