{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:30:21Z","timestamp":1756312221222},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,4,20]],"date-time":"2013-04-20T00:00:00Z","timestamp":1366416000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s00453-013-9782-3","type":"journal-article","created":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T15:57:23Z","timestamp":1366387043000},"page":"529-546","source":"Crossref","is-referenced-by-count":8,"title":["Distribution-Aware Compressed Full-Text Indexes"],"prefix":"10.1007","volume":"67","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[]},{"given":"Jouni","family":"Sir\u00e9n","sequence":"additional","affiliation":[]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,20]]},"reference":[{"key":"9782_CR1","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02574380","volume":"12","author":"A. Aggarwal","year":"1994","unstructured":"Aggarwal, A., Schieber, B., Tokuyama, T.: Finding a minimum-weight k-link path graphs with the concave Monge property and applications. Discrete Comput. Geom. 12, 263\u2013280 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9782_CR2","series-title":"LNCS","first-page":"315","volume-title":"Proceedings of the 21st International Symposium on Algorithms and Computation, Part II (ISAAC 2010)","author":"J. Barbay","year":"2010","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, Part II (ISAAC 2010). LNCS, vol. 6507, pp. 315\u2013326. Springer, Berlin (2010)"},{"key":"9782_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011)","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011). LNCS, vol. 6942, pp. 748\u2013759. Springer, Berlin (2011)"},{"key":"9782_CR4","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, (1994)"},{"issue":"4","key":"9782_CR5","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"},{"key":"9782_CR6","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1145\/1718487.1718536","volume-title":"Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM)","author":"P. Ferragina","year":"2010","unstructured":"Ferragina, P., Manzini, G.: On compressing the textual web. In: Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM), pp. 391\u2013400 (2010)"},{"key":"9782_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: from theory to practice. ACM J. Exp. Algorithmics 13 (2008)","DOI":"10.1145\/1412228.1455268"},{"key":"9782_CR8","first-page":"760","volume-title":"Proc 19th Annual European Symposium on Algorithms (ESA)","author":"P. Ferragina","year":"2011","unstructured":"Ferragina, P., Sir\u00e9n, J., Venturini, R.: Distribution-aware compressed full-text indexes. In: Proc 19th Annual European Symposium on Algorithms (ESA), pp. 760\u2013771 (2011)"},{"key":"9782_CR9","first-page":"201","volume-title":"Pattern Matching Algorithms","author":"R. Giancarlo","year":"1997","unstructured":"Giancarlo, R.: Dynamic programming: special cases. In: Apostolico, A., Galil, Z. (eds.) Pattern Matching Algorithms, 2nd edn., pp. 201\u2013236. Oxford Univ. Press, Oxford (1997)","edition":"2"},{"key":"9782_CR10","first-page":"397","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC)","author":"R. Grossi","year":"2000","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 397\u2013406 (2000)"},{"key":"9782_CR11","first-page":"841","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"R. Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841\u2013850 (2003)"},{"key":"9782_CR12","first-page":"317","volume-title":"Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science (STACS)","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 317\u2013326 (2001)"},{"issue":"4","key":"9782_CR13","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1137\/0216043","volume":"16","author":"D.S. Hirschberg","year":"1987","unstructured":"Hirschberg, D.S., Larmore, L.L.: The least weight subsequence problem. SIAM J. Comput. 16(4), 628\u2013638 (1987)","journal-title":"SIAM J. Comput."},{"key":"9782_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-642-24583-1_18","volume-title":"Proceedings of the 18th Symposium on String Processing and Information Retrieval (SPIRE 2011)","author":"J. K\u00e4rkk\u00e4inen","year":"2011","unstructured":"K\u00e4rkk\u00e4inen, J., Puglisi, S.J.: Fixed block compression boosting in FM-indexes. In: Proceedings of the 18th Symposium on String Processing and Information Retrieval (SPIRE 2011). LNCS, vol. 7024, pp. 174\u2013184. Springer, Berlin (2011)"},{"issue":"3","key":"9782_CR15","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro Sir\u00e9n J, G., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comput. Biol. 17(3), 281\u2013308 (2010)","journal-title":"J. Comput. Biol."},{"key":"9782_CR16","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"issue":"2","key":"9782_CR17","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294\u2013313 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"9782_CR18","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jagm.1998.0955","volume":"29","author":"B. Schieber","year":"1998","unstructured":"Schieber, B.: Computing a minimum weight k-link path in graphs with the concave Monge property. J. Algorithms 29(2), 204\u2013222 (1998)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"9782_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/1500000013","volume":"4","author":"F. Silvestri","year":"2010","unstructured":"Silvestri, F.: Mining query logs: turning search usage data into knowledge. Found. Trends Inf. Retr. 4(1\u20132), 1\u2013174 (2010)","journal-title":"Found. Trends Inf. Retr."},{"key":"9782_CR20","unstructured":"Sir\u00e9n, J.: Compressed full-text indexes for highly repetitive collections. PhD thesis, University of Helsinki (2012)"},{"issue":"3","key":"9782_CR21","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/0196-6774(88)90032-6","volume":"9","author":"R.E. Wilber","year":"1988","unstructured":"Wilber, R.E.: The concave least-weight subsequence problem revisited. J. Algorithms 9(3), 418\u2013425 (1988)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9782-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9782-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9782-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T21:19:22Z","timestamp":1562966362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9782-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,20]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["9782"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9782-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,20]]}}}