{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:00:28Z","timestamp":1757613628125,"version":"3.44.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T00:00:00Z","timestamp":1748649600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T00:00:00Z","timestamp":1748649600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2020R1G1A1101477","NRF-2020R1G1A1101477"],"award-info":[{"award-number":["NRF-2020R1G1A1101477","NRF-2020R1G1A1101477"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,10]]},"DOI":"10.1007\/s00453-025-01325-9","type":"journal-article","created":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T01:38:28Z","timestamp":1748655508000},"page":"1369-1392","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient Data Structure for Next\/Previous Larger\/Smaller Value Queries"],"prefix":"10.1007","volume":"87","author":[{"given":"Seungbum","family":"Jo","sequence":"first","affiliation":[]},{"given":"Geunho","family":"Kim","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,31]]},"reference":[{"key":"1325_CR1","doi-asserted-by":"crossref","unstructured":"Raman, R.: Encoding data structures. In: WALCOM 2015. Proceedings. Lecture Notes in Computer Science, vol. 8973, p. 1\u20137 (2015)","DOI":"10.1007\/978-3-319-15612-5_1"},{"issue":"4","key":"1325_CR2","doi-asserted-by":"publisher","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"},{"issue":"1","key":"1325_CR3","doi-asserted-by":"publisher","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":"3","key":"1325_CR4","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1325_CR5","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1325_CR6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"1325_CR7","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Nicholson, P.K.: Optimal encodings for range top-[CDATA[k]]$$k$$, selection, and min-max. In: Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42, 593\u2013604 (2015). Springer","DOI":"10.1007\/978-3-662-47672-7_48"},{"issue":"3","key":"1325_CR8","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1993.1018","volume":"14","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344\u2013370 (1993)","journal-title":"J. Algorithms"},{"key":"1325_CR9","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E., Fischer, J., Gog, S.: CST++. In: SPIRE 2010. Proceedings. Lecture Notes in Computer Science, vol. 6393, pp. 322\u2013333 (2010)","DOI":"10.1007\/978-3-642-16321-0_34"},{"issue":"22","key":"1325_CR10","doi-asserted-by":"publisher","first-page":"2451","DOI":"10.1016\/j.tcs.2011.01.036","volume":"412","author":"J Fischer","year":"2011","unstructured":"Fischer, J.: Combined data structure for previous- and next-smaller-values. Theor. Comput. Sci. 412(22), 2451\u20132456 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1325_CR11","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.dam.2003.11.012","volume":"144","author":"D Merlini","year":"2004","unstructured":"Merlini, D., Sprugnoli, R., Verri, M.C.: Waiting patterns for a printer. Discrete. Appl. Math. 144(3), 359\u2013373 (2004)","journal-title":"Discrete. Appl. Math."},{"key":"1325_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2016.01.043","volume":"654","author":"S Jo","year":"2016","unstructured":"Jo, S., Satti, S.R.: Simultaneous encodings for range and next\/previous larger\/smaller value queries. Theor. Comput. Sci. 654, 80\u201391 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1325_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.ipl.2019.01.011","volume":"145","author":"D Tsur","year":"2019","unstructured":"Tsur, D.: The effective entropy of next\/previous larger\/smaller value queries. Inf. Process. Lett. 145, 39\u201343 (2019)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1325_CR14","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.2000.1151","volume":"39","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39(2), 205\u2013222 (2001)","journal-title":"J. Algorithms"},{"issue":"4","key":"1325_CR15","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1325_CR16","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16\u201311639 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"1325_CR17","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jda.2016.09.002","volume":"43","author":"H Ferrada","year":"2017","unstructured":"Ferrada, H., Navarro, G.: Improved range minimum queries. J. of Discrete Algorithms 43, 72\u201380 (2017)","journal-title":"J. of Discrete Algorithms"},{"key":"1325_CR18","doi-asserted-by":"crossref","unstructured":"Dodis, Y., P\u0103tra\u015fcu, M., Thorup, M.: Changing base without losing space. In: Proceedings of the forty-second ACM symposium on theory of computing, vol. 593\u2013602 (2010)","DOI":"10.1145\/1806689.1806771"},{"issue":"6","key":"1325_CR19","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1090\/S0002-9939-1964-0184217-8","volume":"15","author":"G Baxter","year":"1964","unstructured":"Baxter, G.: On fixed points of the composite of commuting functions. Proc. of the Am. Math. Soc. 15(6), 851\u2013855 (1964)","journal-title":"Proc. of the Am. Math. Soc."},{"key":"1325_CR20","doi-asserted-by":"crossref","unstructured":"Jo, S., Kim, G.: Space-efficient data structure for next\/previous larger\/smaller value queries. In: LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, Proceedings. Lecture Notes in Computer Science, vol. 13568, pp. 71\u201387 (2022)","DOI":"10.1007\/978-3-031-20624-5_5"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01325-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01325-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01325-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T23:02:33Z","timestamp":1757026953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01325-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,31]]},"references-count":20,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["1325"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01325-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,5,31]]},"assertion":[{"value":"13 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}