{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:40:14Z","timestamp":1775079614108,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T00:00:00Z","timestamp":1410307200000},"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":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9936-y","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T20:42:08Z","timestamp":1410295328000},"page":"65-90","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Space-Efficient Substring Occurrence Estimation"],"prefix":"10.1007","volume":"74","author":[{"given":"Alessio","family":"Orlandi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,10]]},"reference":[{"issue":"1","key":"9936_CR1","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00453-010-9443-8","volume":"62","author":"D Arroyuelo","year":"2012","unstructured":"Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel-Ziv based compressed text indexing. Algorithmica 62(1), 54\u2013101 (2012)","journal-title":"Algorithmica"},{"key":"9936_CR2","doi-asserted-by":"crossref","unstructured":"Barbay, J., Gagie, T., Navarro, G., Nekrich, Y.: Alphabet partitioning for compressed rank\/select and applications. In: Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), pp. 315\u2013326 (2010)","DOI":"10.1007\/978-3-642-17514-5_27"},{"key":"9936_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pp. 427\u2013438 (2010)","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"9936_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pp. 181\u2013192 (2012)","DOI":"10.1007\/978-3-642-33090-2_17"},{"key":"9936_CR5","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"9936_CR6","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Ganti, V., Gravano, L.: Selectivity estimation for string predicates: overcoming the underestimation problem. In: Proceedings of the 20th International Conference on Data Engineering (ICDE), p. 227 (2004)","DOI":"10.1109\/ICDE.2004.1319999"},{"issue":"2","key":"9936_CR7","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"9936_CR8","unstructured":"Fano, R.M.: On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, MA (1971)"},{"key":"9936_CR9","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: from theory to practice. ACM J. Exp. Algorithmics 13, 12\u201331 (2008)"},{"key":"9936_CR10","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a new data structure for string search in external memory and its applications. J. ACM 46, 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"9936_CR11","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"1","key":"9936_CR12","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1868237.1868248","volume":"7","author":"P Ferragina","year":"2010","unstructured":"Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Trans. Algorithms 7(1), 10 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9936_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: Compressed cache-oblivious String B-tree. In: Proceedings of 21th Annual European Symposium on Algorithms (ESA), pp. 469\u2013480 (2013)","DOI":"10.1007\/978-3-642-40450-4_40"},{"issue":"1","key":"9936_CR14","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2071379.2071383","volume":"8","author":"M Frigo","year":"2012","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. ACM Trans. Algorithms 8(1), 4 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9936_CR15","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"9936_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"9936_CR17","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 317\u2013326 (2001)","DOI":"10.1007\/3-540-44693-1_28"},{"key":"9936_CR18","doi-asserted-by":"crossref","unstructured":"Jagadish, H.V., Ng, R.T., Srivastava, D.: Substring selectivity estimation. In: Proceedings of the 18th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of database systems (PODS), pp. 249\u2013260 (1999)","DOI":"10.1145\/303976.304001"},{"key":"9936_CR19","doi-asserted-by":"crossref","unstructured":"Krishnan, P., Vitter, J.S., Iyer, B.R.: Estimating alphanumeric selectivity in the presence of wildcards. In: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 282\u2013293 (1996)","DOI":"10.1145\/233269.233341"},{"issue":"3","key":"9936_CR20","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows\u2013Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"9936_CR21","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA: practical algorithm to retrieve coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"9936_CR22","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full text indexes. ACM Comput. Surv. 39(1), 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"9936_CR23","doi-asserted-by":"crossref","unstructured":"Orlandi, A., Venturini, R.: Space-efficient substring occurrence estimation. In: Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 95\u2013106 (2011)","DOI":"10.1145\/1989284.1989300"},{"key":"9936_CR24","doi-asserted-by":"crossref","unstructured":"Russo, L.M.S., Navarro, G., Oliveira, A.: Fully-compressed suffix trees. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008: Theoretical Informatics, LNCS, vol. 4957, pp. 362\u2013373. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-78773-0_32"},{"key":"9936_CR25","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"IH Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann Publishers, Los Altos, CA (1999)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9936-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9936-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9936-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:14Z","timestamp":1559137514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9936-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,10]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9936"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9936-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,10]]}}}