{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:21:39Z","timestamp":1747196499729,"version":"3.40.5"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_13","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"157-168","source":"Crossref","is-referenced-by-count":4,"title":["Hashing and Indexing: Succinct DataStructures and Smoothed Analysis"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Policriti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L., et al.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 10(3), R25 (2009)","journal-title":"Genome Biol."},{"issue":"15","key":"13_CR2","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R Li","year":"2009","unstructured":"Li, R., Yu, C., Li, Y., Lam, T.W., Yiu, S.M., Kristiansen, K., Wang, J.: SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics 25(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"issue":"1","key":"13_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1093\/bioinformatics\/btr617","volume":"28","author":"F Vezzi","year":"2012","unstructured":"Vezzi, F., Del Fabbro, C., Tomescu, A.I., Policriti, A.: rNA: a fast and accurate short reads numerical aligner. Bioinformatics 28(1), 123\u2013124 (2012)","journal-title":"Bioinformatics"},{"issue":"6","key":"13_CR4","doi-asserted-by":"publisher","first-page":"1868","DOI":"10.1016\/j.jcss.2011.12.007","volume":"78","author":"A Policriti","year":"2012","unstructured":"Policriti, A., Tomescu, A.I., Vezzi, F.: A randomized numerical aligner (rna). J. Comput. Syst. Sci. 78(6), 1868\u20131882 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pp. 91\u2013100. ACM (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11780441_6","volume-title":"Combinatorial Pattern Matching","author":"H-L Chan","year":"2006","unstructured":"Chan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S.: A linear size index for approximate pattern matching. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 49\u201359. Springer, Heidelberg (2006)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-45995-2_20","volume-title":"LATIN 2002: Theoretical Informatics","author":"E Ch\u00e1vez","year":"2002","unstructured":"Ch\u00e1vez, E., Navarro, G.: A metric index for approximate string matching. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, p. 181. Springer, Heidelberg (2002)"},{"issue":"4","key":"13_CR8","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1016\/j.jda.2006.11.001","volume":"5","author":"MG Maa\u00df","year":"2007","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. Journal of Discrete Algorithms 5(4), 662\u2013681 (2007)","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"13_CR9","first-page":"205","volume":"1","author":"G Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. Journal of Discrete Algorithms 1(1), 205\u2013239 (2000)","journal-title":"Journal of Discrete Algorithms"},{"issue":"5","key":"13_CR10","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1093\/bioinformatics\/btn025","volume":"24","author":"R Li","year":"2008","unstructured":"Li, R., Li, Y., Kristiansen, K., Wang, J.: SOAP: short oligonucleotide alignment program. Bioinformatics 24(5), 713\u2013714 (2008)","journal-title":"Bioinformatics"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory, SWAT 2008, pp. 1\u201311. IEEE (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"5","key":"13_CR12","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 22(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"13_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys (CSUR) 39(1), 2 (2007)","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symposium on Foundations of Computer Science, pp. 549\u2013554. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"10","key":"13_CR15","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM 52(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 296\u2013305. ACM (2001)","DOI":"10.1145\/380752.380813"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 390\u2013398. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"13_CR18","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850. Society for Industrial and Applied Mathematics (2003)"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-30213-1_23","volume-title":"String Processing and Information Retrieval","author":"P Ferragina","year":"2004","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: An alphabet-friendly FM-index. In: Apostolico, A., Melucci, M. (eds.) SPIRE 2004. LNCS, vol. 3246, pp. 150\u2013160. Springer, Heidelberg (2004)"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-540-70575-8_30","volume-title":"Automata, Languages and Programming","author":"A Andoni","year":"2008","unstructured":"Andoni, A., Krauthgamer, R.: The smoothed complexity of edit distance. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 357\u2013369. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:11:27Z","timestamp":1747159887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}