{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:03:10Z","timestamp":1746158590173,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_9","type":"book-chapter","created":{"date-parts":[[2013,12,12]],"date-time":"2013-12-12T02:32:52Z","timestamp":1386815572000},"page":"89-99","source":"Crossref","is-referenced-by-count":0,"title":["Less Space: Indexing for Queries with Wildcards"],"prefix":"10.1007","author":[{"given":"Moshe","family":"Lewenstein","sequence":"first","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS, pp. 198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1006\/jagm.2000.1104","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms\u00a037(2), 309\u2013325 (2000)","journal-title":"J. Algorithms"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. In: SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jda.2012.07.005","volume":"18","author":"D. Belazzougui","year":"2013","unstructured":"Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval. J. Algorithms\u00a018, 3\u201313 (2013)","journal-title":"J. Algorithms"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-21458-5_26","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring range reporting. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 299\u2013308. Springer, Heidelberg (2011)"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-31155-0_25","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"P. Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Vind, S.: String indexing for patterns with wildcards. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 283\u2013294. Springer, Heidelberg (2012)"},{"key":"9_CR7","unstructured":"Bucher, P., Bairoch, A.: A generalized profile syntax for biomolecular sequence motifs and its function in automatic sequence interpretation. In: ISMB, pp. 53\u201361 (1994)"},{"issue":"2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00453-008-9263-2","volume":"58","author":"H.-L. Chan","year":"2010","unstructured":"Chan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S.: Compressed indexes for approximate string matching. Algorithmica\u00a058(2), 263\u2013281 (2010)","journal-title":"Algorithmica"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Chien, Y.-F., Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Geometric BWT: Compressed text indexing via sparse suffixes and range searching. Algorithmica (2013)","DOI":"10.1007\/s00453-013-9792-1"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Golynski, A., Ian Munro, J., Srinivasa Rao, S.: Rank\/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"issue":"1","key":"9_CR13","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1093\/nar\/27.1.215","volume":"27","author":"K. Hofmann","year":"1999","unstructured":"Hofmann, K., Bucher, P., Falquet, L., Bairoch, A.: The prosite database, its status in 1999. Nucleic Acids Research\u00a027(1), 215\u2013219 (1999)","journal-title":"Nucleic Acids Research"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.jda.2012.12.003","volume":"19","author":"W.-K. Hon","year":"2013","unstructured":"Hon, W.-K., Ku, T.-H., Shah, R., Thankachan, S.V., Vitter, J.S.: Compressed text indexing with wildcards. J. Discrete Algorithms\u00a019, 23\u201329 (2013)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"9_CR15","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2005.11.022","volume":"352","author":"T.N.D. Huynh","year":"2006","unstructured":"Huynh, T.N.D., Hon, W.-K., Lam, T.-W., Sung, W.-K.: Approximate string matching using compressed suffix arrays. Theoretical Comp. Science\u00a0352(1), 240\u2013249 (2006)","journal-title":"Theoretical Comp. Science"},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-007-9141-3","volume":"55","author":"C.S. Iliopoulos","year":"2009","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Indexing factors with gaps. Algorithmica\u00a055(1), 60\u201370 (2009)","journal-title":"Algorithmica"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Puglisi, S.J.: Medium-space algorithms for inverse BWT. ESA\u00a0(1), 451\u2013462 (2010)","DOI":"10.1007\/978-3-642-15775-2_39"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1007\/978-3-540-77120-3_73","volume-title":"Algorithms and Computation","author":"T.-W. Lam","year":"2007","unstructured":"Lam, T.-W., Sung, W.-K., Tam, S.-L., Yiu, S.-M.: Space efficient indexes for string matching with don\u2019t cares. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 846\u2013857. Springer, Heidelberg (2007)"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-24583-1_14","volume-title":"String Processing and Information Retrieval","author":"M. Lewenstein","year":"2011","unstructured":"Lewenstein, M.: Indexing with gaps. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 135\u2013143. Springer, Heidelberg (2011)"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-40273-9_18","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"M. Lewenstein","year":"2013","unstructured":"Lewenstein, M.: Orthogonal range searching for text indexing. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol.\u00a08066, pp. 267\u2013302. Springer, Heidelberg (2013)"},{"issue":"5","key":"9_CR21","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"9_CR22","unstructured":"Rahman, M.S., Iliopoulos, C.S.: Pattern matching algorithms with don\u2019t cares. In: SOFSEM (2), pp. 116\u2013126 (2007)"},{"key":"9_CR23","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":"9_CR24","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci.\u00a026(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-03784-9_5","volume-title":"String Processing and Information Retrieval","author":"A. Tam","year":"2009","unstructured":"Tam, A., Wu, E., Lam, T.-W., Yiu, S.-M.: Succinct text indexing with wildcards. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 39\u201350. Springer, Heidelberg (2009)"},{"key":"9_CR27","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2012.08.011","volume":"483","author":"C. Thachuk","year":"2013","unstructured":"Thachuk, C.: Compressed indexes for text with wildcards. Theor. Comput. Sci.\u00a0483, 22\u201335 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT (FOCS), pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T04:24:46Z","timestamp":1746073486000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}