{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T19:21:12Z","timestamp":1777317672733,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_10","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"114-125","source":"Crossref","is-referenced-by-count":24,"title":["On Hardness of Jumbled Indexing"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[]},{"given":"Noa","family":"Lewenstein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5-6","key":"10_CR1","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/S1570-8667(03)00035-2","volume":"1","author":"A. Amir","year":"2003","unstructured":"Amir, A., Apostolico, A., Landau, G.M., Satta, G.: Efficient text fingerprinting via Parikh mapping. J. Discrete Algorithms\u00a01(5-6), 409\u2013421 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"10_CR2","unstructured":"Amir, A., Butman, A., Porat, E.: On the relationship between histogram indexing and block-mass indexing. In: Philosophical Transactions A (to appear)"},{"key":"10_CR3","unstructured":"Amir, A., Church, K.W., Dar, E.: Separable attributes: a technique for solving the sub matrices character count problem. In: SODA, pp. 400\u2013401 (2002)"},{"issue":"3","key":"10_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"A. Amir","year":"1994","unstructured":"Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett.\u00a049(3), 111\u2013115 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01215882","volume":"1","author":"G. Phanendra Babu","year":"1995","unstructured":"Phanendra Babu, G., Mehtre, B.M., Kankanhalli, M.S.: Color indexing for efficient image retrieval. Multimedia Tools and Applications\u00a01(4), 327\u2013348 (1995)","journal-title":"Multimedia Tools and Applications"},{"issue":"17","key":"10_CR6","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1016\/j.ipl.2013.05.007","volume":"113","author":"G. Badkobeh","year":"2013","unstructured":"Badkobeh, G., Fici, G., Kroon, S., Lipt\u00e1k, Z.: Binary jumbled string matching for highly run-length compressible texts. Inf. Process. Lett.\u00a0113(17), 604\u2013608 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"B.S. Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: Algorithms and applications. J. Comput. Syst. Sci.\u00a052(1), 28\u201342 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"B.S. Baker","year":"1997","unstructured":"Baker, B.S.: Parameterized duplication in strings: Algorithms and an application to software maintenance. SIAM J. Comput.\u00a026(5), 1343\u20131362 (1997)","journal-title":"SIAM J. Comput."},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/11534273_36","volume-title":"Algorithms and Data Structures","author":"I. Baran","year":"2005","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 409\u2013421. Springer, Heidelberg (2005)"},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/bioinformatics\/btl291","volume":"23","author":"S. B\u00f6cker","year":"2007","unstructured":"B\u00f6cker, S.: Simulating multiplexed SNP discovery rates using base-specific cleavage and mass spectrometry. Bioinformatics\u00a023(2), 5\u201312 (2007)","journal-title":"Bioinformatics"},{"issue":"10","key":"10_CR11","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. Commun. ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/s00453-012-9734-3","volume":"69","author":"D. Bremner","year":"2014","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., P\u0103tra\u015fcu, M., Taslakian, P.: Necklaces, convolutions, and X\u2009+\u2009Y. Algorithmica\u00a069, 294\u2013314 (2014)","journal-title":"Algorithmica"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-642-13122-6_11","volume-title":"Fun with Algorithms","author":"P. Burcsi","year":"2010","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: On table arrangements, scrabble freaks, and jumbled pattern matching. In: Boldi, P. (ed.) FUN 2010. LNCS, vol.\u00a06099, pp. 89\u2013101. Springer, Heidelberg (2010)"},{"issue":"6","key":"10_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.ipl.2004.09.002","volume":"92","author":"A. Butman","year":"2004","unstructured":"Butman, A., Eres, R., Landau, G.M.: Scaled and permuted string matching. Inf. Process. Lett.\u00a092(6), 293\u2013297 (2004)","journal-title":"Inf. Process. Lett."},{"key":"10_CR15","unstructured":"Butman, A., Lewenstein, N., Munro, I.J.: Permuted scaled matching. In: CPM 2014 (to appear, 2014)"},{"key":"10_CR16","unstructured":"Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Searching for jumbled patterns in strings. In: Prague Stringology Conference, pp. 105\u2013117 (2009)"},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-31265-6_12","volume-title":"Combinatorial Pattern Matching","author":"F. Cicalese","year":"2012","unstructured":"Cicalese, F., Laber, E.S., Weimann, O., Yuster, R.: Near linear time construction of an approximate index for all maximum consecutive sub-sums of a sequence. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 149\u2013158. Springer, Heidelberg (2012)"},{"key":"10_CR18","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":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-319-02432-5_13","volume-title":"String Processing and Information Retrieval","author":"M. Crochemore","year":"2013","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Kubica, M., Langiu, A., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Order-preserving incomplete suffix trees and order-preserving indexes. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol.\u00a08214, pp. 84\u201395. Springer, Heidelberg (2013)"},{"key":"10_CR20","unstructured":"Durocher, S., Ian Munro, J., Mondal, D., Thankachan, S.V.: Jumbled pattern matching over large alphabets (2014) (manuscript, personal communication)"},{"issue":"6","key":"10_CR21","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1089\/cmb.2004.11.1050","volume":"11","author":"R. Eres","year":"2004","unstructured":"Eres, R., Landau, G.M., Parida, L.: Permutation pattern discovery in biosequences. Journal of Computational Biology\u00a011(6), 1050\u20131060 (2004)","journal-title":"Journal of Computational Biology"},{"key":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-642-40450-4_44","volume-title":"Algorithms \u2013 ESA 2013","author":"T. Gagie","year":"2013","unstructured":"Gagie, T., Hermelin, D., Landau, G.M., Weimann, O.: Binary jumbled pattern matching on trees and tree-like structures. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 517\u2013528. Springer, Heidelberg (2013)"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n\n                  2) problems in computational geometry. Comput. Geom.\u00a05, 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"issue":"14-16","key":"10_CR24","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1016\/j.ipl.2013.04.013","volume":"113","author":"E. Giaquinta","year":"2013","unstructured":"Giaquinta, E., Grabowski, S.: New algorithms for binary jumbled pattern matching. Inf. Process. Lett.\u00a0113(14-16), 538\u2013542 (2013)","journal-title":"Inf. Process. Lett."},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Hazay, C., Lewenstein, M., Sokol, D.: Approximate parameterized matching. ACM Transactions on Algorithms\u00a03(3) (2007)","DOI":"10.1145\/1273340.1273345"},{"key":"10_CR26","unstructured":"Hermelin, D., Landau, G.M., Rabinovich, Y., Weimann, O.: Binary jumbled pattern matching via all-pairs shortest paths (2014) (manuscript), \n                    \n                      http:\/\/arxiv.org\/abs\/1401.2065"},{"issue":"3","key":"10_CR27","first-page":"525","volume":"42","author":"S. Holub","year":"2008","unstructured":"Holub, S.: Parikh test sets for commutative languages. ITA\u00a042(3), 525\u2013537 (2008)","journal-title":"ITA"},{"key":"10_CR28","unstructured":"Huang, X., Ali, H., Sadanandam, A., Singh, R.: SRPVS: a new motif searching algorithm for protein analysis. In: Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004, pp. 674\u2013675 (2004)"},{"issue":"2","key":"10_CR29","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"10_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/978-3-642-40450-4_53","volume-title":"Algorithms \u2013 ESA 2013","author":"T. Kociumaka","year":"2013","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Efficient indexes for jumbled pattern matching with constant-sized alphabet. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 625\u2013636. Springer, Heidelberg (2013)"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Kopczynski, E., Widjaja, A.: Parikh images of grammars: Complexity and applications. In: LICS, pp. 80\u201389 (2010)","DOI":"10.1109\/LICS.2010.21"},{"issue":"12","key":"10_CR32","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/j.ipl.2013.03.015","volume":"113","author":"M. Kubica","year":"2013","unstructured":"Kubica, M., Kulczynski, T., Radoszewski, J., Rytter, W., Walen, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett.\u00a0113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"key":"10_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-642-34109-0_35","volume-title":"String Processing and Information Retrieval","author":"L.-K. Lee","year":"2012","unstructured":"Lee, L.-K., Lewenstein, M., Zhang, Q.: Parikh matching in the streaming model. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 336\u2013341. Springer, Heidelberg (2012)"},{"issue":"5","key":"10_CR34","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."},{"issue":"18-19","key":"10_CR35","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1016\/j.ipl.2010.06.012","volume":"110","author":"T.M. Moosa","year":"2010","unstructured":"Moosa, T.M., Rahman, M.S.: Indexing permutations for binary strings. Inf. Process. Lett.\u00a0110(18-19), 795\u2013798 (2010)","journal-title":"Inf. Process. Lett."},{"key":"10_CR36","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.jda.2011.08.003","volume":"10","author":"T.M. Moosa","year":"2012","unstructured":"Moosa, T.M., Rahman, M.S.: Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discrete Algorithms\u00a010, 5\u20139 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"10_CR37","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: STOC, pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"issue":"1","key":"10_CR39","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00130487","volume":"7","author":"M.J. Swain","year":"1991","unstructured":"Swain, M.J., Ballard, D.H.: Color indexing. International Journal of Computer Vision\u00a07(1), 11\u201332 (1991)","journal-title":"International Journal of Computer Vision"},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT (FOCS), pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: STOC (to appear, 2014)","DOI":"10.1145\/2591796.2591811"},{"key":"10_CR42","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: FOCS, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:32:39Z","timestamp":1558909959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}