{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T21:01:59Z","timestamp":1694638919852},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,4,13]],"date-time":"2010-04-13T00:00:00Z","timestamp":1271116800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1007\/s11786-010-0037-2","type":"journal-article","created":{"date-parts":[[2010,4,12]],"date-time":"2010-04-12T21:08:01Z","timestamp":1271106481000},"page":"433-442","source":"Crossref","is-referenced-by-count":4,"title":["Cache Oblivious Algorithms for the RMQ and the RMSQ Problems"],"prefix":"10.1007","volume":"3","author":[{"given":"Masud","family":"Hasan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanaeem M.","family":"Moosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Sohel","family":"Rahman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,4,13]]},"reference":[{"issue":"10","key":"37_CR1","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1093\/bioinformatics\/btg135","volume":"19","author":"L. Allison","year":"2003","unstructured":"Allison L.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19(10), 1294\u20131295 (2003)","journal-title":"Bioinformatics"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN, pp. 88\u201394. (2000)","DOI":"10.1007\/10719839_9"},{"issue":"9","key":"37_CR3","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1145\/358234.381162","volume":"27","author":"J.L. Bentley","year":"1984","unstructured":"Bentley J.L.: Algorithm design techniques. Commun. ACM 27(9), 865\u2013871 (1984)","journal-title":"Commun. ACM"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Berkman, O., Breslauer, D., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems (extended abstract). In: STOC, pp. 309\u2013319. ACM, New York (1989)","DOI":"10.1145\/73007.73036"},{"issue":"6","key":"37_CR5","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.ipl.2005.08.006","volume":"96","author":"K.-Y. Chen","year":"2005","unstructured":"Chen K.-Y., Chao K.-M.: Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint. Inf. Process. Lett. 96(6), 197\u2013201 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"16","key":"37_CR6","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1016\/j.dam.2007.05.018","volume":"155","author":"K.-Y. Chen","year":"2007","unstructured":"Chen K.-Y., Chao K.-M.: On the range maximum-sum segment query problem. Discrete Appl. Math. 155(16), 2043\u20132052 (2007)","journal-title":"Discrete Appl. Math."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Iliopoulos, C.S., Rahman, M.S.: Finding patterns in given intervals. In: Kucera, L., Kucera, A. (eds.) MFCS. Lecture Notes in Computer Science, vol. 4708\u00a0pp. 645\u2013656. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74456-6_57"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Iliopoulos, C.S., Rahman, M.S.: Optimal prefix and suffix queries on texts. In: Jacquet, P. (ed.) AofA, DMTCS Proc., AH, pp. 645\u2013656 (2007)","DOI":"10.46298\/dmtcs.3541"},{"key":"37_CR9","unstructured":"Demaine, E.: Cache-oblivious algorithms and data structures. In: Lecture Notes from the EEF Summer School on Massive Data Sets (2002)"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 5555, pp. 341\u2013353. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-02927-1_29"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Fan, T.-H., Lee, S., Lu, H.-I., Tsou, T.-S., Wang, T.-C., Yao, A.: An optimal algorithm for maximum-sum segment and its application in bioinformatics extended abstract. In: Ibarra, O.H., Dang, Z. (eds.) CIAA. Lecture Notes in Computer Science, vol. 2759, pp. 251\u2013257. Springer, Berlin (2003)","DOI":"10.1007\/3-540-45089-0_23"},{"key":"37_CR12","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th Annual Symposium on Foundations of Computer Science (FOCS \u201999), IEEE, Washington, Brussels, Tokyo, Oct. 1999"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Gabow, H., Bentley, J., Tarjan, R.: Scaling and related techniques for geometry problems. In: Symposium on the Theory of Computing (STOC), pp. 135\u2013143. ACM, New York (1984)","DOI":"10.1145\/800057.808675"},{"issue":"2","key":"37_CR14","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":"37_CR15","doi-asserted-by":"crossref","unstructured":"Johannes Fischer, V.H.: A new succinct representation of RMQ-information and improvements in the enhanced suffix array. In: Chen, B., Zhang, G. (eds.) ESCAPE. Lecture Notes in Computer Science, vol. 4614, pp. 459\u2013470. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74450-4_41"},{"issue":"1","key":"37_CR16","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1093\/bioinformatics\/19.1.151","volume":"19","author":"Y.-L. Lin","year":"2003","unstructured":"Lin Y.-L., Huang X., Jiang T., Chao K.-M.: Mavg: locating non-overlapping maximum average segments in a given sequence. Bioinformatics 19(1), 151\u2013152 (2003)","journal-title":"Bioinformatics"},{"issue":"3","key":"37_CR17","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/S0022-0000(02)00010-7","volume":"65","author":"Y.-L. Lin","year":"2002","unstructured":"Lin Y.-L., Jiang T., Chao K.-M.: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. Syst. Sci. 65(3), 570\u2013586 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"37_CR18","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/S0097539704440430","volume":"34","author":"K. min Chung","year":"2004","unstructured":"min Chung K., Lu H.-I.: An optimal algorithm for the maximum-density segment problem. SIAM J. Comput. 34(2), 373\u2013387 (2004)","journal-title":"SIAM J. Comput."},{"key":"37_CR19","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 657\u2013666 (2002)"},{"key":"37_CR20","unstructured":"Prokop, H.: Cache-oblivious algorithms. Master\u2019s thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science (1999)"},{"issue":"1","key":"37_CR21","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":"6","key":"37_CR22","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":"37_CR23","doi-asserted-by":"crossref","unstructured":"Vitter, J.S.: External memory algorithms. In: PODS, pp. 119\u2013128. ACM Press, New York (1998)","DOI":"10.1145\/275487.275501"},{"issue":"2","key":"37_CR24","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1093\/bioinformatics\/19.2.297","volume":"19","author":"L. Wang","year":"2003","unstructured":"Wang, L., Xu, Y.: Segid: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics 19(2), 297\u2013298 (2003)","journal-title":"Bioinformatics"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0037-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-010-0037-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0037-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T22:39:05Z","timestamp":1635201545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-010-0037-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,13]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["37"],"URL":"https:\/\/doi.org\/10.1007\/s11786-010-0037-2","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,13]]}}}