{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:48:19Z","timestamp":1793850499872,"version":"4.6.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,2,23]],"date-time":"2011-02-23T00:00:00Z","timestamp":1298419200000},"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":[[2012,8]]},"DOI":"10.1007\/s00453-011-9499-0","type":"journal-article","created":{"date-parts":[[2011,2,22]],"date-time":"2011-02-22T17:22:03Z","timestamp":1298395323000},"page":"815-830","source":"Crossref","is-referenced-by-count":35,"title":["On Space Efficient Two Dimensional Range Minimum Data Structures"],"prefix":"10.1007","volume":"63","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,2,23]]},"reference":[{"issue":"1","key":"9499_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M.I. Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J.\u00a0Discrete Algorithms 2(1), 53\u201386 (2004)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9499_CR2","first-page":"253","volume-title":"Proc. 5th Annual ACM Symposium on Theory of Computing","author":"A. Aho","year":"1973","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: On finding lowest common ancestors in trees. In: Proc. 5th Annual ACM Symposium on Theory of Computing, pp. 253\u2013265. ACM, New York (1973)"},{"key":"9499_CR3","first-page":"258","volume-title":"Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"S. Alstrup","year":"2002","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 258\u2013264. ACM, New York (2002)"},{"key":"9499_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Proc. 18th Annual Symposium on Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Proc. 18th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4580, pp. 286\u2013294. Springer, Berlin (2007)"},{"key":"9499_CR5","first-page":"150","volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M.J. Atallah","year":"2010","unstructured":"Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150\u2013160. SIAM, Philadelphia (2010)"},{"key":"9499_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"Proc. 4th Latin American Theoretical Informatics Symposium","author":"M. Bender","year":"2000","unstructured":"Bender, M., Farach-Colton, M.: The LCA problem revisited. In: Proc. 4th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer, Berlin (2000)"},{"issue":"2","key":"9499_CR7","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"issue":"5","key":"9499_CR8","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Inf. Process. Lett. 8(5), 244\u2013251 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9499_CR9","first-page":"309","volume-title":"Proc. 21st Annual ACM Symposium on Theory of Computing","author":"O. Berkman","year":"1989","unstructured":"Berkman, O., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 309\u2013319. ACM, New York (1989)"},{"key":"9499_CR10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/73833.73848","volume-title":"Proc. 5th Annual Symposium on Computational Geometry","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proc. 5th Annual Symposium on Computational Geometry, pp. 131\u2013139. ACM, New York (1989)"},{"key":"9499_CR11","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/s11786-007-0024-4","volume":"1","author":"G. Chen","year":"2008","unstructured":"Chen, G., Puglisi, S.J., Smyth, W.F.: Lempel-Ziv factorization using less time and space. Math. Comput. Sci. 1, 605\u2013623 (2008)","journal-title":"Math. Comput. Sci."},{"key":"9499_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Proc. 36th International Colloquium on Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: Proc. 36th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5555, pp. 341\u2013353. Springer, Berlin (2009)"},{"key":"9499_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"Proc. 9th Latin American Theoretical Informatics Symposium","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: Proc. 9th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 6034, pp. 158\u2013169. Springer, Berlin (2010)"},{"key":"9499_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Proc. 17th Annual Symposium on Combinatorial Pattern Matching","author":"J. Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the rmq-problem, with applications to lca and lce. In: Proc. 17th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4009, pp. 36\u201348. Springer, Berlin (2006)"},{"key":"9499_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Proc. 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of rmq-information and improvements in the enhanced suffix array. In: Proc. 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Lecture Notes in Computer Science, vol. 4614, pp. 459\u2013470. Springer, Berlin (2007)"},{"key":"9499_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-540-69068-9_16","volume-title":"Proc. 19th Annual Symposium on Combinatorial Pattern Matching","author":"J. Fischer","year":"2008","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: An(other) entropy-bounded compressed suffix tree. In: Proc. 19th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 5029, pp. 152\u2013165. Springer, Berlin (2008)"},{"key":"9499_CR17","first-page":"135","volume-title":"Proc. 16th Annual ACM Symposium on Theory of Computing","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM, New York (1984)"},{"issue":"3","key":"9499_CR18","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.tcs.2007.02.047","volume":"379","author":"A. G\u00e1l","year":"2007","unstructured":"G\u00e1l, A., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379(3), 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9499_CR19","first-page":"869","volume-title":"Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"L. Georgiadis","year":"2004","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited: extended abstract. In: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 869\u2013878. SIAM, Philadelphia (2004)"},{"issue":"3","key":"9499_CR20","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci. 387(3), 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9499_CR21","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"9499_CR22","series-title":"Leibniz International Proceedings in Informatics","first-page":"205","volume-title":"Proc. 25th International Symposium on Theoretical Aspects of Computer Science","author":"C.S. Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Crochemore, M., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 1, pp. 205\u2013216. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Leibniz (2008)"},{"key":"9499_CR23","unstructured":"Miltersen, P.B.: Cell probe complexity\u2014a survey. Advances in Data Structures Workshop (Pre-conference Workshop of Foundations of Software Technology and Theoretical Computer Science) (1999). http:\/\/www.daimi.au.dk\/~bromille\/Papers\/survey3.ps"},{"key":"9499_CR24","first-page":"657","volume-title":"Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Muthukrishnan","year":"2002","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 657\u2013666. SIAM, Philadelphia (2002)"},{"issue":"3","key":"9499_CR25","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/S0304-3975(02)00741-7","volume":"296","author":"C.K. Poon","year":"2003","unstructured":"Poon, C.K.: Dynamic orthogonal range queries in OLAP. Theory Comput. Syst. 296(3), 487\u2013510 (2003)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"9499_CR26","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9499_CR27","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"9","key":"9499_CR28","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.ipl.2008.12.006","volume":"109","author":"S. Saxena","year":"2009","unstructured":"Saxena, S.: Dominance made simple. Inf. Process. Lett. 109(9), 419\u2013421 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"9499_CR29","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253\u20131262 (1988)","journal-title":"SIAM J. Comput."},{"key":"9499_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-540-73437-6_22","volume-title":"Proc. 18th Annual Symposium on Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2007","unstructured":"V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Space-efficient algorithms for document retrieval. In: Proc. 18th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4580, pp. 205\u2013215. Springer, Berlin (2007)"},{"issue":"4","key":"9499_CR31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229\u2013239 (1980)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9499-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9499-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9499-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T15:20:06Z","timestamp":1560007206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9499-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,23]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9499"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9499-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,23]]}}}