{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:30:56Z","timestamp":1773279056153,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319238258","type":"print"},{"value":"9783319238265","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23826-5_28","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:20:20Z","timestamp":1441354820000},"page":"287-298","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Sampling the Suffix Array with Minimizers"],"prefix":"10.1007","author":[{"given":"Szymon","family":"Grabowski","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Raniszewski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"key":"28_CR1","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: SODA, pp. 819\u2013828. Society for Industrial and Applied Mathematics (2000)"},{"issue":"5","key":"28_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1089\/cmb.2014.0160","volume":"22","author":"R Chikhi","year":"2015","unstructured":"Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the representation of de Bruijn graphs. Journal of Computational Biology 22(5), 336\u2013352 (2015)","journal-title":"Journal of Computational Biology"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jda.2010.09.004","volume":"11","author":"F Claude","year":"2012","unstructured":"Claude, F., Navarro, G., Peltola, H., Salmela, L., Tarhio, J.: String matching with alphabet sampling. Journal of Discrete Algorithms 11, 37\u201350 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"28_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-44450-5_23","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"P Crescenzi","year":"2000","unstructured":"Crescenzi, P., Del Lungo, A., Grossi, R., Lodi, E., Pagli, L., Rossi, G.: Text sparsification via local maxima. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol. 1974, pp. 290\u2013301. Springer, Heidelberg (2000)"},{"issue":"304","key":"28_CR5","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0304-3975(03)00142-7","volume":"1\u20133","author":"P Crescenzi","year":"2003","unstructured":"Crescenzi, P., Lungo, A.D., Grossi, R., Lodi, E., Pagli, L., Rossi, G.: Text sparsification via local maxima. Theoretical Computer Science 1\u20133(304), 341\u2013364 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"10","key":"28_CR6","doi-asserted-by":"publisher","first-page":"1569","DOI":"10.1093\/bioinformatics\/btv022","volume":"31","author":"S Deorowicz","year":"2015","unstructured":"Deorowicz, S., Kokot, M., Grabowski, S., Debudaj-Grabysz, A.: KMC 2: fast and resource-frugal k-mer counting. Bioinformatics 31(10), 1569\u20131576 (2015)","journal-title":"Bioinformatics"},{"key":"28_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-540-73437-6_33","volume-title":"Combinatorial Pattern Matching","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Fischer, J.: Suffix arrays on words. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 328\u2013339. Springer, Heidelberg (2007)"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: From theory to practice. ACM Journal of Experimental Algorithmics 13, article 12, 30 (2009)","DOI":"10.1145\/1412228.1455268"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating LZ77 via small-space multiple-pattern matching. CoRR, abs\/1504.06647 (2015)","DOI":"10.1007\/978-3-662-48350-3_45"},{"issue":"11","key":"28_CR10","doi-asserted-by":"publisher","first-page":"1287","DOI":"10.1002\/spe.2198","volume":"44","author":"S Gog","year":"2014","unstructured":"Gog, S., Petri, M.: Optimized succinct data structures for massive data. Software-Practice and Experience 44(11), 1287\u20131314 (2014)","journal-title":"Software-Practice and Experience"},{"issue":"9","key":"28_CR11","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1093\/bioinformatics\/btu844","volume":"31","author":"S Grabowski","year":"2015","unstructured":"Grabowski, S., Deorowicz, S., Roguski, \u0141.: Disk-based compression of data from genome sequencing. Bioinformatics 31(9), 1389\u20131395 (2015)","journal-title":"Bioinformatics"},{"key":"28_CR12","unstructured":"Grabowski, S., Raniszewski, M.: Two simple full-text indexes based on the suffix array. In: Holub, J., Zd\u00e1rek, J. (eds.) PSC, pp. 179\u2013191. Faculty of Information Technology, Czech Technical University in Prague, Department of Theoretical Computer Science (2014)"},{"key":"28_CR13","unstructured":"Grabowski, S., Raniszewski, M.: Two simple full-text indexes based on the suffix array (2015). Submitted to a journal"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Han,Y.: Deterministic sorting in $${O}(n \\log \\log n)$$ time and linear space. In: STOC, pp. 602\u2013608. ACM (2002)","DOI":"10.1145\/509989.509993"},{"key":"28_CR15","unstructured":"Tomohiro, I., K\u00e4rkk\u00e4inen, J., Kempa, D.: Faster sparse suffix sorting. In: Mayr, E.W., Portier, N. (eds.) STACS. LIPIcs, vol. 25, pp. 386\u2013396. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","volume-title":"Computing and Combinatorics","author":"J K\u00e4rkk\u00e4inen","year":"1996","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Sparse suffix trees. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 219\u2013230. Springer, Heidelberg (1996)"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., Suri, S.: Memory efficient minimum substring partitioning. In: VLDB, pp. 169\u2013180. VLDB Endowment (2013)","DOI":"10.14778\/2535569.2448951"},{"issue":"2","key":"28_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys 39(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/11880561_11","volume-title":"String Processing and Information Retrieval","author":"SJ Puglisi","year":"2006","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: Inverted files versus suffix arrays for locating patterns in primary memory. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol. 4209, pp. 122\u2013133. Springer, Heidelberg (2006)"},{"issue":"18","key":"28_CR21","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","volume":"20","author":"M Roberts","year":"2004","unstructured":"Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., Yorke, J.A.: Reducing storage requirements for biological sequence comparison. Bioinformatics 20(18), 3363\u20133369 (2004)","journal-title":"Bioinformatics"},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Symmetry breaking for suffix tree construction. In: STOC, pp. 300\u2013309. ACM (1994)","DOI":"10.1145\/195058.195164"},{"issue":"3","key":"28_CR23","doi-asserted-by":"publisher","first-page":"R46","DOI":"10.1186\/gb-2014-15-3-r46","volume":"15","author":"DE Wood","year":"2014","unstructured":"Wood, D.E., Salzberg, S.L.: Kraken: ultrafast metagenomic sequence classification using exact alignments. Genome Biology 15(3), R46 (2014)","journal-title":"Genome Biology"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23826-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T22:46:18Z","timestamp":1718059578000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23826-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319238258","9783319238265"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23826-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}