{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:33:22Z","timestamp":1725744802015},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_8","type":"book-chapter","created":{"date-parts":[[2013,8,10]],"date-time":"2013-08-10T01:20:34Z","timestamp":1376097634000},"page":"97-111","source":"Crossref","is-referenced-by-count":4,"title":["From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"\u00c1vila, B.T., Laber, E.S.: Merge source coding. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), pp. 214\u2013218. IEEE (2009)","DOI":"10.1109\/ISIT.2009.5205774"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-540-27801-6_30","volume-title":"Combinatorial Pattern Matching","author":"R. Baeza-Yates","year":"2004","unstructured":"Baeza-Yates, R.: A fast set intersection algorithm for sorted sequences. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 400\u2013408. Springer, Heidelberg (2004)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Barbay, J., Claude, F., Gagie, T., Navarro, G., Nekrich, Y.: Efficient fully-compressed sequence representations. Algorithmica (to appear, 2013)","DOI":"10.1007\/s00453-012-9726-3"},{"key":"8_CR4","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. Elsevier Theoretical Computer Science (TCS)\u00a0459, 26\u201341 (2012)","journal-title":"Elsevier Theoretical Computer Science (TCS)"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms\u00a07(4), 52 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Barbay, J., Kenyon, C.: Deterministic algorithm for the t-threshold set problem. In: Proceedings of the 14th International Symposium Algorithms and Computation (ISAAC), pp. 575\u2013584 (2003)","DOI":"10.1007\/978-3-540-24587-2_59"},{"key":"8_CR7","unstructured":"Barbay, J., Navarro, G.: Compressed representations of permutations, and applications. In: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), vol.\u00a03, pp. 111\u2013122 (2009)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. ACM Transactions on Algorithms (TALG) (to appear, 2013)","DOI":"10.1145\/2635816"},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"J.L. Bentley","year":"1976","unstructured":"Bentley, J.L., Yao, A.C.-C.: An almost optimal algorithm for unbounded searching. Information Processing Letters\u00a05(3), 82\u201387 (1976)","journal-title":"Information Processing Letters"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(58)80001-7","volume":"1","author":"W.H. Burge","year":"1958","unstructured":"Burge, W.H.: Sorting, trees, and measures of order. Information and Control\u00a01(3), 181\u2013197 (1958)","journal-title":"Information and Control"},{"issue":"6","key":"8_CR11","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/BF01190160","volume":"9","author":"S. Carlsson","year":"1993","unstructured":"Carlsson, S., Levcopoulos, C., Petersson, O.: Sublinear merging and natural mergesort. Algorithmica\u00a09(6), 629\u2013648 (1993)","journal-title":"Algorithmica"},{"key":"8_CR12","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 743\u2013752 (2000)"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P. Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory\u00a021(2), 194\u2013203 (1975)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Computing Surveys\u00a024(4), 441\u2013476 (1992)","journal-title":"ACM Computing Surveys"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/3-540-52921-7_61","volume-title":"Algorithms","author":"W. Fernandez de la Vega","year":"1990","unstructured":"Fernandez de la Vega, W., Kannan, S., Santha, M.: Two probabilistic results on merging. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 118\u2013127. Springer, Heidelberg (1990)"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. STOC, pp. 135\u2013143. ACM Press (1984)","DOI":"10.1145\/800057.808675"},{"key":"8_CR18","unstructured":"Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: IEEE Symposium on Foundations of Computer Science, pp. 305\u2013313 (2000)"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/11786986_33","volume-title":"Automata, Languages and Programming","author":"A. Golynski","year":"2006","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 370\u2013381. Springer, Heidelberg (2006)"},{"key":"8_CR20","unstructured":"Golynski, A.: Upper and Lower Bounds for Text Indexing Data Structures. PhD thesis. University of Waterloo (2007)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 368\u2013373. ACM (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"8_CR22","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841\u2013850. ACM (2003)"},{"issue":"12","key":"8_CR23","first-page":"1339","volume":"11","author":"J.D. Harris","year":"1981","unstructured":"Harris, J.D.: Sorting unsorted and partially sorted lists using the natural merge sort. Software: Practice and Experience\u00a011(12), 1339\u20131340 (1981)","journal-title":"Software: Practice and Experience"},{"issue":"1","key":"8_CR24","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F.K. Hwang","year":"1972","unstructured":"Hwang, F.K., Lin, S.: A simple algorithm for merging two disjoint linearly-ordered sets. SIAM J. Comput.\u00a01(1), 31\u201339 (1972)","journal-title":"SIAM J. Comput."},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"8_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-52846-6_88","volume-title":"SWAT \u201990","author":"C. Levcopoulos","year":"1990","unstructured":"Levcopoulos, C., Petersson, O.: Sorting shuffled monotone sequences. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 181\u2013191. Springer, Heidelberg (1990)"},{"issue":"1","key":"8_CR27","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/inco.1994.1050","volume":"112","author":"C. Levcopoulos","year":"1994","unstructured":"Levcopoulos, C., Petersson, O.: Sorting shuffled monotone sequences. Inf. Comput.\u00a0112(1), 37\u201350 (1994)","journal-title":"Inf. Comput."},{"issue":"4","key":"8_CR28","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"34","author":"H. Mannila","year":"1985","unstructured":"Mannila, H.: Measures of presortedness and optimal sorting algorithms. IEEE Trans. Computers\u00a034(4), 318\u2013325 (1985)","journal-title":"IEEE Trans. Computers"},{"issue":"2","key":"8_CR29","first-page":"70","volume":"24","author":"A. Moffat","year":"1992","unstructured":"Moffat, A., Petersson, O.: An overview of adaptive sorting. Australian Computer Journal\u00a024(2), 70\u201377 (1992)","journal-title":"Australian Computer Journal"},{"issue":"1","key":"8_CR30","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1023\/A:1013002601898","volume":"3","author":"A. Moffat","year":"2000","unstructured":"Moffat, A., Stuiver, L.: Binary interpolative coding for effective index compression. Inf. Retr.\u00a03(1), 25\u201347 (2000)","journal-title":"Inf. Retr."},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2012.03.005","volume":"438","author":"J.I. Munro","year":"2012","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations and functions. Theor. Comput. Sci.\u00a0438, 74\u201388 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"8_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"J.I. Munro","year":"1976","unstructured":"Munro, J.I., Spira, P.M.: Sorting and searching in multisets. SIAM J. Comput.\u00a05(1), 1\u20138 (1976)","journal-title":"SIAM J. Comput."},{"key":"8_CR33","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0166-218X(93)E0160-Z","volume":"59","author":"O. Petersson","year":"1995","unstructured":"Petersson, O., Moffat, A.: A framework for adaptive sorting. Discrete Applied Mathematics\u00a059, 153\u2013179 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"8_CR35","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1109\/TCOM.1971.1090789","volume":"COM-19","author":"R.F. Rice","year":"1971","unstructured":"Rice, R.F., Plaunt, J.R.: Adaptive variable-length coding for efficient compression of spacecraft television data. IEEE Trans. Commun.\u00a0COM-19, 889\u2013897 (1971)","journal-title":"IEEE Trans. Commun."},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. SODA, pp. 134\u2013149. ACM\/SIAM (2010)","DOI":"10.1137\/1.9781611973075.13"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T14:50:22Z","timestamp":1558018222000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}