{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:56:01Z","timestamp":1725566161179},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228943"},{"type":"electronic","value":"9783540278214"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27821-4_24","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T18:54:06Z","timestamp":1284490446000},"page":"261-272","source":"Crossref","is-referenced-by-count":10,"title":["The Sketching Complexity of Pattern Matching"],"prefix":"10.1007","author":[{"given":"Ziv","family":"Bar-Yossef","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. S.","family":"Jayram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proceedings of IEEE Data Compression Conference, DCC, pp. 279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: Pattern matching in Z-compressed files. J. of Computer and System Sciences\u00a052(2), 299\u2013307 (1996)","journal-title":"J. of Computer and System Sciences"},{"key":"24_CR4","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficientl (2004) (manuscript)"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: Information theory methods in communication complexity. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pp. 93\u2013102 (2002)","DOI":"10.1109\/CCC.2002.1004344"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Batu, T., Erg\u00fcn, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 316\u2013324 (2003)","DOI":"10.1145\/780542.780590"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A. Broder","year":"2000","unstructured":"Broder, A., Charikar, M., Frieze, A., Mitzenmacher, M.: Min-wise independent permutations. Journal of Computer and System Sciences\u00a060(3), 630\u2013659 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"8-13","key":"24_CR8","first-page":"1157","volume":"29","author":"A. Broder","year":"1997","unstructured":"Broder, A., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the web. WWW6\/Computer Networks\u00a029(8-13), 1157\u20131166 (1997)","journal-title":"WWW6\/Computer Networks"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M.: Similarity estimation techniques from rounding algorithms. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 380\u2013388 (2002)","DOI":"10.1145\/509907.509965"},{"key":"24_CR10","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"T.M. Cover","year":"1991","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Inc. Chichester (1991)"},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/348751.348754","volume":"18","author":"E. Moura de","year":"2000","unstructured":"de Moura, E., Navarro, G., Ziviani, N., Baeza-Yates, R.: Fast and flexible word searching on compressed text. ACM Transactions on Information Systems\u00a018(2), 113\u2013139 (2000)","journal-title":"ACM Transactions on Information Systems"},{"issue":"4","key":"24_CR12","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/PL00009202","volume":"20","author":"M. Farach","year":"1998","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. Algorithmica\u00a020(4), 388\u2013404 (1998)","journal-title":"Algorithmica"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/3-540-48224-5_75","volume-title":"Automata, Languages and Programming","author":"J. Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M.J., Wright, R.N.: Secure multiparty computation of approximations. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 927\u2013938. Springer, Heidelberg (2001)"},{"issue":"1","key":"24_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/S0097539799361701","volume":"32","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M.J., Viswanathan, M.: An approximate L1-difference algorithm for massive data streams. SIAM J. Comput.\u00a032(1), 131\u2013151 (2002)","journal-title":"SIAM J. Comput."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1109\/SFCS.2000.892127","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"P. Ferragina","year":"2000","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 Computer Society, Los Alamitos (2000)"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"issue":"2","key":"24_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"issue":"1","key":"24_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I. Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Computational Complexity\u00a08(1), 21\u201349 (1999)","journal-title":"Computational Complexity"},{"issue":"2","key":"24_CR19","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/S0097539798347177","volume":"30","author":"E. Kushilevitz","year":"2000","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing\u00a030(2), 457\u2013474 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR20","unstructured":"Lonardi, S.: Pattern matching pointers (2004), Available http:\/\/www.cs.ucr.edu\/~stelo\/pattern.html"},{"issue":"2","key":"24_CR21","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/248625.248639","volume":"15","author":"U. Manber","year":"1997","unstructured":"Manber, U.: A text compression scheme that allows fast searching directly in the compressed file. ACM Transactions on Information Systems\u00a015(2), 124\u2013136 (1997)","journal-title":"ACM Transactions on Information Systems"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-45123-4_16","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Tarhio, J.: Boyer-Moore string matching over Ziv-Lempel compressed text. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 166\u2013180. Springer, Heidelberg (2000)"},{"issue":"2","key":"24_CR23","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett.\u00a039(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"24_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-45123-4_17","volume-title":"Combinatorial Pattern Matching","author":"Y. Shibata","year":"2000","unstructured":"Shibata, Y., Matsumoto, T., Takeda, M., Shinohara, A., Arikawa, S.: A Boyer- Moore type algorithm for compressed pattern matching. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 181\u2013194. Springer, Heidelberg (2000)"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Yao, C.-C.: Lower bounds by probabilistic arguments. In: Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, pp. 420\u2013428 (1983)","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27821-4_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:23:10Z","timestamp":1605759790000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27821-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228943","9783540278214"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27821-4_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}