{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T10:01:25Z","timestamp":1649066485108},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T00:00:00Z","timestamp":1491177600000},"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":["Algorithmica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00453-017-0307-3","type":"journal-article","created":{"date-parts":[[2017,4,3]],"date-time":"2017-04-03T12:27:37Z","timestamp":1491222457000},"page":"1315-1329","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Semi-Group Range Sum Revisited: Query-Space Lower Bound Tightened"],"prefix":"10.1007","volume":"80","author":[{"given":"Xiaocheng","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuigeng","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,3]]},"reference":[{"key":"307_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answeringon-line product queries. Technical Report TR 71\/87, Tel-AvivUniversity (1987)"},{"issue":"4","key":"307_CR2","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1007\/s00454-012-9412-x","volume":"47","author":"S Arya","year":"2012","unstructured":"Arya, S., Mount, D.M., Xia, J.: Tight lower bounds for halfspace range searching. Discrete Comput. Geom. 47(4), 711\u2013730 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"307_CR3","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00454-012-9410-z","volume":"47","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: Optimal partition trees. Discrete Comput. Geom. 47(4), 661\u2013690 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"307_CR4","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching II. The arithmetic model. JACM 37(3), 439\u2013463 (1990)","journal-title":"JACM"},{"issue":"4","key":"307_CR5","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1145\/322276.322281","volume":"28","author":"ML Fredman","year":"1981","unstructured":"Fredman, M.L.: A lower bound on the complexity of orthogonal range queries. JACM 28(4), 696\u2013705 (1981)","journal-title":"JACM"},{"issue":"1","key":"307_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539795291598","volume":"28","author":"H Hampapuram","year":"1998","unstructured":"Hampapuram, H., Fredman, M.L.: Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM J. Comput. 28(1), 1\u20139 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"307_CR7","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/120865240","volume":"43","author":"KG Larsen","year":"2014","unstructured":"Larsen, K.G.: On range searching in the group model and combinatorial discrepancy. SIAM J. Comput. 43(2), 673\u2013686 (2014)","journal-title":"SIAM J. Comput."},{"key":"307_CR8","doi-asserted-by":"crossref","unstructured":"Larsen, K.G.: The cell probe complexity of dynamic range counting. In: Proceedings of ACM Symposium on Theory of Computing, pp. 85\u201394 (2012)","DOI":"10.1145\/2213977.2213987"},{"key":"307_CR9","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J Matousek","year":"1993","unstructured":"Matousek, J.: Range searching with efficient hiearchical cutting. Discrete Comput. Geom. 10, 157\u2013182 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"307_CR10","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Lower bounds for 2-dimensional range counting. In: Proceedings of ACM Symposium on Theory of Computing, pp. 40\u201346 (2007)","DOI":"10.1145\/1250790.1250797"},{"key":"307_CR11","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: Proceedings of ACM Symposium on Theory of Computing, pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0307-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0307-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0307-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T19:54:52Z","timestamp":1519761292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0307-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,3]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["307"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0307-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,3]]}}}