{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:13:16Z","timestamp":1742980396562,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_45","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"529-540","source":"Crossref","is-referenced-by-count":1,"title":["Document Retrieval with One Wildcard"],"prefix":"10.1007","author":[{"given":"Moshe","family":"Lewenstein","sequence":"first","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 476\u2013482 (2001)","key":"45_CR1","DOI":"10.1145\/380752.380842"},{"issue":"2","key":"45_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":"45_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"45_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. Discrete Algorithms\u00a018, 3\u201313 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"45_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":"45_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)"},{"issue":"10","key":"45_CR7","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A Fast String Searching Algorithm. Communications of the ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Communications of the ACM"},{"issue":"40-42","key":"45_CR8","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H. Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theoretical Computer Science\u00a0411(40-42), 3795\u20133800 (2010)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proc. 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 91\u2013100 (2004)","key":"45_CR9","DOI":"10.1145\/1007352.1007374"},{"key":"45_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/978-3-642-29344-3_28","volume-title":"LATIN 2012: Theoretical Informatics","author":"J. Fischer","year":"2012","unstructured":"Fischer, J., Gagie, T., Kopelowitz, T., Lewenstein, M., M\u00e4kinen, V., Salmela, L., V\u00e4lim\u00e4ki, N.: Forbidden patterns. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 327\u2013337. Springer, Heidelberg (2012)"},{"issue":"2","key":"45_CR11","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Ku, T.-H., Shah, R., Thankachan, S.V., Vitter, J.S.: Compressed dictionary matching with one error. In: Proc. 2011 Data Compression Conference (DCC 2011), pp. 113\u2013122 (2011)","key":"45_CR12","DOI":"10.1109\/DCC.2011.18"},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-40273-9_22","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"W.-K. Hon","year":"2013","unstructured":"Hon, W.-K., Patil, M., Shah, R., Thankachan, S.V., Vitter, J.S.: Indexes for document retrieval with relevance. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol.\u00a08066, pp. 351\u2013362. Springer, Heidelberg (2013)"},{"key":"45_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-16321-0_6","volume-title":"String Processing and Information Retrieval","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: String retrieval for multi-pattern queries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 55\u201366. Springer, Heidelberg (2010)"},{"key":"45_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-31265-6_15","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: Document listing for queries with excluded pattern. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 185\u2013195. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: FOCS, pp. 713\u2013722. IEEE Computer Society (2009)","key":"45_CR16","DOI":"10.1109\/FOCS.2009.19"},{"issue":"1","key":"45_CR17","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":"45_CR18","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"},{"issue":"2","key":"45_CR19","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.B.: Fast Pattern Matching in Strings. SIAM Journal on Computing\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR20","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":"45_CR21","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":"45_CR22","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)"},{"unstructured":"Lewenstein, M., Nekrich, Y., Vitter, J.S.: Space-efficient string indexing for wildcard pattern matching. In: Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 506\u2013517 (2014)","key":"45_CR23"},{"unstructured":"Lewenstein, M., Nekrich, Y., Vitter, J.S.: Space-efficient string indexing for wildcard pattern matching. CoRR, abs\/1401.0625 (2014)","key":"45_CR24"},{"issue":"5","key":"45_CR25","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":"45_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-68530-8_6","volume-title":"Algorithms - ESA \u201998","author":"Y. Matias","year":"1998","unstructured":"Matias, Y., Muthukrishnan, S., \u015eahinalp, S.C., Ziv, J.: Augmenting suffix trees, with applications. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 67\u201378. Springer, Heidelberg (1998)"},{"unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 657\u2013666 (2002)","key":"45_CR27"},{"unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. CoRR, abs\/1304.6023 (2013)","key":"45_CR28"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top-k document retrieval in optimal time and linear space. In: Rabani, Y. (ed.) SODA, pp. 1066\u20131077. SIAM (2012)","key":"45_CR29","DOI":"10.1137\/1.9781611973099.84"},{"unstructured":"Rahman, M.S., Iliopoulos, C.S.: Pattern matching algorithms with don\u2019t cares. In: Proc. 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), pp. 116\u2013126 (2007)","key":"45_CR30"},{"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)","key":"45_CR31","DOI":"10.1145\/1290672.1290680"},{"issue":"1","key":"45_CR32","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms\u00a05(1), 12\u201322 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"45_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1007\/978-3-642-40450-4_68","volume-title":"Algorithms \u2013 ESA 2013","author":"R. Shah","year":"2013","unstructured":"Shah, R., Sheng, C., Thankachan, S.V., Vitter, J.S.: Top-k document retrieval in external memory. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 803\u2013814. Springer, Heidelberg (2013)"},{"issue":"3","key":"45_CR34","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":"45_CR35","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)"},{"doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT (FOCS), pp. 1\u201311. IEEE Computer Society (1973)","key":"45_CR36","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:36:13Z","timestamp":1676637373000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}