{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:52:30Z","timestamp":1740099150003,"version":"3.37.3"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030004781"},{"type":"electronic","value":"9783030004798"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","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":[[2018]]},"DOI":"10.1007\/978-3-030-00479-8_17","type":"book-chapter","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T10:58:18Z","timestamp":1536836298000},"page":"206-217","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Compressed Range Minimum Queries"],"prefix":"10.1007","author":[{"given":"Seungbum","family":"Jo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9262-1821","authenticated-orcid":false,"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":false,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,14]]},"reference":[{"issue":"2","key":"17_CR1","doi-asserted-by":"publisher","first-page":"319","DOI":"10.3390\/a6020319","volume":"6","author":"A Abeliuk","year":"2013","unstructured":"Abeliuk, A., C\u00e1novas, R., Navarro, G.: Practical compressed suffix trees. Algorithms 6(2), 319\u2013351 (2013)","journal-title":"Algorithms"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2003","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Maintaining information in fully-dynamic trees with top trees. ACM Trans. Algorithms 1, 243\u2013264 (2003)","journal-title":"ACM Trans. Algorithms"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2012.08.010","volume":"459","author":"J Barbay","year":"2012","unstructured":"Barbay, J., Fischer, J., Navarro, G.: LRM-trees: compressed indices, adaptive sorting, and compressed permutations. Theor. Comput. Sci. 459, 26\u201341 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.ic.2014.12.012","volume":"243","author":"P Bille","year":"2015","unstructured":"Bille, P., G\u00f8rtz, I.L., Landau, G.M., Weimann, O.: Tree compression with top trees. Inf. Comput. 243, 166\u2013177 (2015)","journal-title":"Inf. Comput."},{"issue":"3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"17_CR7","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/978-3-642-32241-9_34","volume-title":"Computing and Combinatorics","author":"P Davoodi","year":"2012","unstructured":"Davoodi, P., Raman, R., Satti, S.R.: Succinct representations of binary trees for range minimum queries. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 396\u2013407. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_34"},{"issue":"4","key":"17_CR9","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"PJ Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM 27(4), 758\u2013771 (1980). https:\/\/doi.org\/10.1145\/322217.322228","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","unstructured":"Dudek, B., Gawrychowski, P.: Slowing down top trees for better worst-case compression. In: Annual Symposium on Combinatorial Pattern Matching. CPM 2018, 2\u20134 July 2018, Qingdao, China, pp. 16:1\u201316:8 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.16","key":"17_CR10","DOI":"10.4230\/LIPIcs.CPM.2018.16"},{"issue":"2","key":"17_CR11","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."},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.jda.2012.07.006","volume":"18","author":"K Goto","year":"2013","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Fast q-gram mining on SLP compressed strings. J. Discrete Algorithms 18, 89\u201399 (2013)","journal-title":"J. Discrete Algorithms"},{"unstructured":"Jez, A., Lohrey, M.: Approximation of smallest linear tree grammar. In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). STACS 2014, pp. 445\u2013457 (2014)","key":"17_CR13"},{"issue":"1\u20133","key":"17_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Takabatake, Y., I, T., Sakamoto, H.: A space-optimal grammar compression. In: 25th Annual European Symposium on Algorithms. ESA 2017, pp. 67:1\u201367:15 (2017)","key":"17_CR15"},{"issue":"4","key":"17_CR16","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"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00479-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T07:24:25Z","timestamp":1538119465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-00479-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030004781","9783030004798"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00479-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/eventos.spc.org.pe\/spire2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"22","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}