{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:09:13Z","timestamp":1761174553493},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,9,21]],"date-time":"2007-09-21T00:00:00Z","timestamp":1190332800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2007,10,12]]},"DOI":"10.1007\/s00453-007-9030-9","type":"journal-article","created":{"date-parts":[[2007,9,20]],"date-time":"2007-09-20T12:21:10Z","timestamp":1190290870000},"page":"94-108","source":"Crossref","is-referenced-by-count":7,"title":["Space Efficient Dynamic Orthogonal Range Reporting"],"prefix":"10.1007","volume":"49","author":[{"given":"Y.","family":"Nekrich","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,21]]},"reference":[{"key":"9030_CR1","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol.\u00a023, pp.\u00a01\u201356. Am. Math. Soc., Providence (1999). Available at http:\/\/citeseer.ist.psu.edu\/article\/agarwal99geometric.html"},{"key":"9030_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Arge, L., Danner, A., Holland-Minkley, B.: Cache-oblivious data structures for orthogonal range searching. In: Proc. 9th Symp. on Computational Geometry, pp.\u00a0237\u2013245 (2003)","DOI":"10.1145\/777792.777828"},{"key":"9030_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: Proc. 41st FOCS, pp.\u00a0198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"9030_CR4","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. 41st FOCS, pp.\u00a0399\u2013409 (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"key":"9030_CR5","doi-asserted-by":"crossref","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, 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"9030_CR6","doi-asserted-by":"crossref","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, 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"9030_CR7","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 search II. The arithmetic model. J. ACM 37, 439\u2013463 (1990)","journal-title":"J. ACM"},{"key":"9030_CR8","unstructured":"Chiang, J.L., Tamassia, R.: Dynamic algorithms in computational geometry. Technical Report CS-91-24, Dept. of Computer Science, Brown University (1991)"},{"key":"9030_CR9","doi-asserted-by":"crossref","unstructured":"Gabow, H., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th STOC, pp.\u00a0135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"9030_CR10","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., O\u2019Rourke, J. (ed.): Handbook of Discrete and Computational Geometry, 2nd edn. CRC Press (April 2004)","DOI":"10.1201\/9781420035315"},{"key":"9030_CR11","doi-asserted-by":"crossref","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Proc. 8th ICALP, pp.\u00a0417\u2013431 (1981)","DOI":"10.1007\/3-540-10843-2_34"},{"key":"9030_CR12","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/BF01553907","volume":"4","author":"R. Klein","year":"1989","unstructured":"Klein, R., Nurmi, O., Ottman, T., Wood, D.: A\u00a0dynamic fixed windowing problem. Algorithmica 4, 535\u2013550 (1989)","journal-title":"Algorithmica"},{"key":"9030_CR13","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: A data structure for orthogonal range queries. In: Proc. 19th FOCS, pp.\u00a028\u201334 (1978)","DOI":"10.1109\/SFCS.1978.1"},{"key":"9030_CR14","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput. 14, 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"key":"9030_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer, New York (1984)"},{"key":"9030_CR16","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica 5, 215\u2013241 (1990)","journal-title":"Algorithmica"},{"key":"9030_CR17","unstructured":"Mortensen, C.W.: Fully dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. In: Proc. of the 14th SODA, pp.\u00a0618\u2013627 (2003)"},{"key":"9030_CR18","doi-asserted-by":"crossref","first-page":"1494","DOI":"10.1137\/S0097539703436722","volume":"35","author":"C.W. Mortensen","year":"2006","unstructured":"Mortensen, C.W.: Fully dynamic orthogonal range reporting on RAM. SIAM J. Comput. 35, 1494\u20131525 (2006)","journal-title":"SIAM J. Comput."},{"key":"9030_CR19","volume-title":"Design of Dynamic Data Structures","author":"M.H. Overmars","year":"1987","unstructured":"Overmars, M.H.: Design of Dynamic Data Structures. Springer, New York (1987)"},{"key":"9030_CR20","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. J.\u00a0Comput. Syst. Sci. 18, 110\u2013127 (1979)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"6","key":"9030_CR21","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1007\/BF01759075","volume":"6","author":"M. Kreveld Van","year":"1991","unstructured":"Van Kreveld, M., Overmars, M.H.: Divided K-d trees. Algorithmica 6(6), 840\u2013858 (1991)","journal-title":"Algorithmica"},{"issue":"1","key":"9030_CR22","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1006\/inco.1994.1027","volume":"110","author":"M. Kreveld Van","year":"1994","unstructured":"Van Kreveld, M., Overmars M.H.: Concatenable structures for decomposable problems, Inf. Comput. 110(1), 130\u2013148 (1994)","journal-title":"Inf. Comput."},{"key":"9030_CR23","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"D.E. Willard","year":"1985","unstructured":"Willard, D.E.: New data structures for orthogonal range queries. SIAM J. Comput. 14, 232\u2013253 (1985)","journal-title":"SIAM J. Comput."},{"key":"9030_CR24","first-page":"846","volume":"34","author":"D.E. Willard","year":"1987","unstructured":"Willard, D.E.: Multidimensional search trees that provide new types of memory reductions. J.\u00a0ACM 34, 846\u2013858 (1987)","journal-title":"J.\u00a0ACM"},{"key":"9030_CR25","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1006\/jcss.1996.0012","volume":"52","author":"D.E. Willard","year":"1996","unstructured":"Willard, D.E.: Applications of range query theory to relational data base join and select operations. J.\u00a0Comput. Syst. Sci. 52, 157\u2013169 (1996)","journal-title":"J.\u00a0Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9030-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9030-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9030-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9030-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,21]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,10,12]]}},"alternative-id":["9030"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9030-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,21]]}}}