{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329062,"version":"3.37.3"},"reference-count":78,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>Data masking is a common technique for sanitizing sensitive data maintained in database systems which is becoming increasingly important in various application areas, such as in record linkage of personal data. This work formalizes the Pattern Masking for Dictionary Matching (PMDM<\/jats:sc>) problem: given a dictionary $$\\mathscr {D}$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of d<\/jats:italic> strings, each of length $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, a query string q<\/jats:italic> of length $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a positive integer z<\/jats:italic>, we are asked to compute a smallest set $$K\\subseteq \\{1,\\ldots ,\\ell \\}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \u2286<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \u2113<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, so that if q<\/jats:italic>[i<\/jats:italic>] is replaced by a wildcard for all $$i\\in K$$<\/jats:tex-math>\n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n K<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, then q<\/jats:italic> matches at least z<\/jats:italic> strings from $$\\mathscr {D}$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Solving PMDM<\/jats:sc> allows providing data utility guarantees as opposed to existing approaches. We first show, through a reduction from the well-known k<\/jats:italic>-Clique problem, that a decision version of the PMDM<\/jats:sc> problem is NP-complete, even for binary strings. We thus approach the problem from a more practical perspective. We show a combinatorial $$\\mathscr {O}((d\\ell )^{|K|\/3}+d\\ell )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n (<\/mml:mo>\n d<\/mml:mi>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n |<\/mml:mo>\n K<\/mml:mi>\n |<\/mml:mo>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n d<\/mml:mi>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time and $$\\mathscr {O}(d\\ell )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-space algorithm for PMDM<\/jats:sc> for $$|K|=\\mathscr {O}(1)$$<\/jats:tex-math>\n \n |<\/mml:mo>\n K<\/mml:mi>\n |<\/mml:mo>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In fact, we show that we cannot hope for a faster combinatorial algorithm, unless the combinatorial k<\/jats:italic>-Clique hypothesis fails (Abboud et al. in SIAM J\u00a0Comput 47:2527\u20132555,\u00a02018; Lincoln et al., in: 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018). Our combinatorial algorithm, executed with small |K<\/jats:italic>|, is the backbone of a greedy heuristic that we propose. Our experiments on real-world and synthetic datasets show that our heuristic finds nearly-optimal solutions in practice and is also very efficient. We also generalize this algorithm for the problem of masking multiple query strings simultaneously so that every string has at least z<\/jats:italic> matches in $$\\mathscr {D}$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. PMDM<\/jats:sc> can be viewed as a generalization of the decision version of the dictionary matching with mismatches problem: by querying a PMDM<\/jats:sc> data structure with string q<\/jats:italic> and $$z=1$$<\/jats:tex-math>\n \n z<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, one obtains the minimal number of mismatches of q<\/jats:italic> with any string from $$\\mathscr {D}$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The query time or space of all known data structures for the more restricted<\/jats:italic> problem of dictionary matching with at most k<\/jats:italic> mismatches incurs some exponential factor with respect to k<\/jats:italic>. A simple exact algorithm for PMDM<\/jats:sc> runs in time $$\\mathscr {O}(2^\\ell d)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \u2113<\/mml:mi>\n <\/mml:msup>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present a data structure for PMDM<\/jats:sc> that answers queries over $$\\mathscr {D}$$<\/jats:tex-math>\n D<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in time $$\\mathscr {O}(2^{\\ell \/2}(2^{\\ell \/2}+\\tau )\\ell )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u2113<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u2113<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n \u03c4<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and requires space $$\\mathscr {O}(2^{\\ell }d^2\/\\tau ^2+2^{\\ell \/2}d)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \u2113<\/mml:mi>\n <\/mml:msup>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n \u03c4<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u2113<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for any parameter $$\\tau \\in [1,d]$$<\/jats:tex-math>\n \n \u03c4<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n d<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We complement our results by showing a two-way polynomial-time reduction between PMDM<\/jats:sc> and the Minimum Union problem [Chlamt\u00e1\u010d et al., ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017]. This gives a polynomial-time $$\\mathscr {O}(d^{1\/4+\\epsilon })$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 4<\/mml:mn>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for PMDM<\/jats:sc>, which is tight under a plausible complexity conjecture. This is an extended version of a paper that was presented at International Symposium on Algorithms and Computation (ISAAC) 2021.\n<\/jats:p>","DOI":"10.1007\/s00453-024-01213-8","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T13:02:21Z","timestamp":1709730141000},"page":"1948-1978","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pattern Masking for Dictionary Matching: Theory and Practice"],"prefix":"10.1007","volume":"86","author":[{"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huiping","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Christen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigorios","family":"Loukides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"issue":"6","key":"1213_CR1","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1137\/16M1061771","volume":"47","author":"A Abboud","year":"2018","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: If the current clique algorithms are optimal, so is Valiant\u2019s parser. SIAM J. Comput. 47(6), 2527\u20132555 (2018). https:\/\/doi.org\/10.1137\/16M1061771","journal-title":"SIAM J. Comput."},{"key":"1213_CR2","doi-asserted-by":"publisher","unstructured":"Afshani, P., Nielsen, J.S.: Data structure lower bounds for document indexing problems. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), LIPIcs, vol.\u00a055, pp. 93:1\u201393:15 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.93","DOI":"10.4230\/LIPIcs.ICALP.2016.93"},{"issue":"6","key":"1213_CR3","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975). https:\/\/doi.org\/10.1145\/360825.360855","journal-title":"Commun. ACM"},{"key":"1213_CR4","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 522\u2013539. SIAM, Philadelphia (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.32","DOI":"10.1137\/1.9781611976465.32"},{"issue":"5","key":"1213_CR5","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/120884857","volume":"42","author":"B Applebaum","year":"2013","unstructured":"Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput. 42(5), 2008\u20132037 (2013). https:\/\/doi.org\/10.1137\/120884857","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1213_CR6","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10878-006-9029-1","volume":"13","author":"H Arimura","year":"2007","unstructured":"Arimura, H., Uno, T.: An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence. J. Comb. Optim. 13(3), 243\u2013262 (2007). https:\/\/doi.org\/10.1007\/s10878-006-9029-1","journal-title":"J. Comb. Optim."},{"key":"1213_CR7","unstructured":"Bailey, D.R., Battle, A.J., Gomes, B.A., Nayak, P.P.: Estimating Confidence for Query Revision Models. U.S. Patent US7617205B2 (granted to Google) (2009)"},{"key":"1213_CR8","doi-asserted-by":"publisher","unstructured":"Bailey, M., Cole, C., Henderson, M., Massey, C.: How well do automated linking methods perform? Lessons from U.S. historical data. NBER Working Papers 24019, National Bureau of Economic Research, Inc (2017). https:\/\/doi.org\/10.3386\/w24019","DOI":"10.3386\/w24019"},{"issue":"43","key":"1213_CR9","doi-asserted-by":"publisher","first-page":"4327","DOI":"10.1016\/j.tcs.2009.07.014","volume":"410","author":"G Battaglia","year":"2009","unstructured":"Battaglia, G., Cangelosi, D., Grossi, R., Pisanti, N.: Masking patterns in sequences: a new class of motif discovery with don\u2019t cares. Theor. Comput. Sci. 410(43), 4327\u20134340 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.07.014","journal-title":"Theor. Comput. Sci."},{"key":"1213_CR10","doi-asserted-by":"publisher","unstructured":"Belazzougui, D.: Faster and space-optimal edit distance \u201c1\u201d dictionary. In: 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), Lecture Notes in Computer Science, vol. 5577, pp. 154\u2013167. Springer, New York (2009). https:\/\/doi.org\/10.1007\/978-3-642-02441-2_14","DOI":"10.1007\/978-3-642-02441-2_14"},{"issue":"3","key":"1213_CR11","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1007\/s00453-015-9990-0","volume":"74","author":"D Belazzougui","year":"2016","unstructured":"Belazzougui, D., Venturini, R.: Compressed string dictionary search with edit distance one. Algorithmica 74(3), 1099\u20131122 (2016). https:\/\/doi.org\/10.1007\/s00453-015-9990-0","journal-title":"Algorithmica"},{"issue":"1","key":"1213_CR12","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00224-013-9498-4","volume":"55","author":"P Bille","year":"2014","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Vind, S.: String indexing for patterns with wildcards. Theory Comput. Syst. 55(1), 41\u201360 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9498-4","journal-title":"Theory Comput. Syst."},{"key":"1213_CR13","doi-asserted-by":"publisher","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower bounds for high dimensional nearest neighbor search and related problems. In: 31st ACM Symposium on Theory of Computing (STOC 1999), pp. 312\u2013321 (1999). https:\/\/doi.org\/10.1145\/301250.301330","DOI":"10.1145\/301250.301330"},{"issue":"1\u20132","key":"1213_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0020-0190(00)00079-X","volume":"75","author":"GS Brodal","year":"2000","unstructured":"Brodal, G.S., Venkatesh, S.: Improved bounds for dictionary look-up with one error. Inf. Process. Lett. 75(1\u20132), 57\u201359 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00079-X","journal-title":"Inf. Process. Lett."},{"key":"1213_CR15","doi-asserted-by":"publisher","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Parameterized and Exact Computation, 4th International Workshop (IWPEC 2009), Lecture Notes in Computer Science, vol. 5917, pp. 75\u201385. Springer, New York (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_6","DOI":"10.1007\/978-3-642-11269-0_6"},{"issue":"2","key":"1213_CR16","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00453-008-9263-2","volume":"58","author":"H Chan","year":"2010","unstructured":"Chan, H., Lam, T.W., Sung, W., Tam, S., Wong, S.: Compressed indexes for approximate string matching. Algorithmica 58(2), 263\u2013281 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9263-2","journal-title":"Algorithmica"},{"key":"1213_CR17","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Chen, H., Christen, P., Loukides, G., Pisanti, N., Pissis, S.P., Radoszewski, J.: Pattern Masking for Dictionary Matching. In: Ahn, H.K., Sadakane, K. (eds.) 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 212, pp. 65:1\u201365:19. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.65.","DOI":"10.4230\/LIPIcs.ISAAC.2021.65."},{"key":"1213_CR18","doi-asserted-by":"publisher","unstructured":"Charikar, M., Indyk, P., Panigrahy, R.: New algorithms for subset query, partial match, orthogonal range searching, and related problems. In: 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), pp. 451\u2013462 (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_39","DOI":"10.1007\/3-540-45465-9_39"},{"issue":"8","key":"1213_CR19","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"1213_CR20","doi-asserted-by":"publisher","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Makarychev, Y.: Minimizing the union: tight approximations for small set bipartite vertex expansion. In: 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 881\u2013899 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.56","DOI":"10.1137\/1.9781611974782.56"},{"issue":"2","key":"1213_CR21","doi-asserted-by":"publisher","first-page":"1458","DOI":"10.1137\/16M1096402","volume":"32","author":"E Chlamt\u00e1\u010d","year":"2018","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Konrad, C., Kortsarz, G., Rabanca, G.: The densest k-subhypergraph problem. SIAM J. Discrete Math. 32(2), 1458\u20131477 (2018). https:\/\/doi.org\/10.1137\/16M1096402","journal-title":"SIAM J. Discrete Math."},{"key":"1213_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31164-2","volume-title":"Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. Data-Centric Systems and Applications","author":"P Christen","year":"2012","unstructured":"Christen, P.: Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection. Data-Centric Systems and Applications. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31164-2"},{"key":"1213_CR23","doi-asserted-by":"publisher","DOI":"10.1145\/2889311","author":"P Christen","year":"2016","unstructured":"Christen, P., Gayler, R.W., Tran, K.N., Fisher, J., Vatsalan, D.: Automatic discovery of abnormal values in large textual databases. J. Data Inf. Qual. (2016). https:\/\/doi.org\/10.1145\/2889311","journal-title":"J. Data Inf. Qual."},{"key":"1213_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59706-1","volume-title":"Linking Sensitive Data","author":"P Christen","year":"2020","unstructured":"Christen, P., Ranbaduge, T., Schnell, R.: Linking Sensitive Data. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-59706-1"},{"key":"1213_CR25","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Feuilloley, L., Starikovskaya, T.: Lower bounds for text indexing with mismatches and differences. In: 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 1146\u20131164 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.70","DOI":"10.1137\/1.9781611975482.70"},{"key":"1213_CR26","doi-asserted-by":"publisher","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 91\u2013100 (2004). https:\/\/doi.org\/10.1145\/1007352.1007374","DOI":"10.1145\/1007352.1007374"},{"key":"1213_CR27","doi-asserted-by":"publisher","unstructured":"Cuzzocrea, A., Shahriar, H.: Data masking techniques for nosql database security: a systematic review. In: 2017 IEEE International Conference on Big Data (BigData 2017), pp. 4467\u20134473 (2017). https:\/\/doi.org\/10.1109\/BigData.2017.8258486","DOI":"10.1109\/BigData.2017.8258486"},{"key":"1213_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1213_CR29","doi-asserted-by":"publisher","unstructured":"Ding, B., Lo, D., Han, J., Khoo, S.C.: Efficient mining of closed repetitive gapped subsequences from a sequence database. In: 25th IEEE International Conference on Data Engineering (ICDE), pp. 1024\u20131035 (2009). https:\/\/doi.org\/10.1109\/ICDE.2009.104","DOI":"10.1109\/ICDE.2009.104"},{"issue":"12","key":"1213_CR30","doi-asserted-by":"publisher","first-page":"2956","DOI":"10.1109\/TKDE.2013.91","volume":"26","author":"EA Durham","year":"2014","unstructured":"Durham, E.A., Kantarcioglu, M., Xue, Y., T\u00f3th, C., Malin, B.: Composite bloom filters for secure record linkage. IEEE Trans. Knowl. Data Eng. 26(12), 2956\u20132968 (2014). https:\/\/doi.org\/10.1109\/TKDE.2013.91","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"43","key":"1213_CR31","doi-asserted-by":"publisher","first-page":"4391","DOI":"10.1016\/J.TCS.2009.07.020","volume":"410","author":"M Federico","year":"2009","unstructured":"Federico, M., Pisanti, N.: Suffix tree characterization of maximal motifs in biological sequences. Theor. Comput. Sci. 410(43), 4391\u20134401 (2009). https:\/\/doi.org\/10.1016\/J.TCS.2009.07.020","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1213_CR32","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $${O}(1)$$ worst case access time. J. ACM 31(3), 538\u2013544 (1984). https:\/\/doi.org\/10.1145\/828.1884","journal-title":"J. ACM"},{"issue":"4","key":"1213_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1749603.1749605","volume":"42","author":"BCM Fung","year":"2010","unstructured":"Fung, B.C.M., Wang, K., Chen, R., Yu, P.S.: Privacy-preserving data publishing: a survey of recent developments. ACM Comput. Surv. 42(4), 1\u201353 (2010). https:\/\/doi.org\/10.1145\/1749603.1749605","journal-title":"ACM Comput. Surv."},{"key":"1213_CR34","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Algorithms - 22th Annual European Symposium (ESA 2014), Lecture Notes in Computer Science, vol. 8737, pp. 455\u2013466. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_38","DOI":"10.1007\/978-3-662-44777-2_38"},{"key":"1213_CR35","doi-asserted-by":"publisher","unstructured":"Gollapudi, S., Ieong, S., Ntoulas, A., Paparizos, S.: Efficient query rewrite for structured web queries. In: 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 2417\u20132420 (2011). https:\/\/doi.org\/10.1145\/2063576.2063981","DOI":"10.1145\/2063576.2063981"},{"issue":"4","key":"1213_CR36","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1089\/CMB.2010.0177","volume":"18","author":"R Grossi","year":"2011","unstructured":"Grossi, R., Pietracaprina, A., Pisanti, N., Pucci, G., Upfal, E., Vandin, F.: MADMX: a strategy for maximal dense motif extraction. J. Comput. Biol. 18(4), 535\u2013545 (2011). https:\/\/doi.org\/10.1089\/CMB.2010.0177","journal-title":"J. Comput. Biol."},{"key":"1213_CR37","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2017.04.012","volume":"710","author":"R Grossi","year":"2018","unstructured":"Grossi, R., Menconi, G., Pisanti, N., Trani, R., Vind, S.: Motif trie: An efficient text index for pattern discovery with don\u2019t cares. Theor. Comput. Sci. 710, 74\u201387 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.04.012","journal-title":"Theor. Comput. Sci."},{"key":"1213_CR38","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J Hastad","year":"1999","unstructured":"Hastad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Math. 182, 105\u2013142 (1999). https:\/\/doi.org\/10.1007\/BF02392825","journal-title":"Acta Math."},{"key":"1213_CR39","volume-title":"Data Quality and Record Linkage Techniques","author":"TN Herzog","year":"2007","unstructured":"Herzog, T.N., Scheuren, F.J., Winkler, W.E.: Data Quality and Record Linkage Techniques. Springer, New York (2007)"},{"key":"1213_CR40","doi-asserted-by":"publisher","unstructured":"I, T., Enokuma, Y., Bannai, H., Takeda, M.: General algorithms for mining closed flexible patterns under various equivalence relations. In: Machine Learning and Knowledge Discovery in Databases, pp. 435\u2013450 (2012). https:\/\/doi.org\/10.1007\/978-3-642-33486-3_28","DOI":"10.1007\/978-3-642-33486-3_28"},{"key":"1213_CR41","unstructured":"IBM Synthetic Data Generator for Itemsets and Sequences. https:\/\/github.com\/zakimjz\/IBMGenerator (2020)"},{"key":"1213_CR42","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730","author":"IF Ilyas","year":"2008","unstructured":"Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surveys (2008). https:\/\/doi.org\/10.1145\/1391729.1391730","journal-title":"ACM Comput. Surveys"},{"issue":"2","key":"1213_CR43","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1213_CR44","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2004.04.006","volume":"69","author":"TS Jayram","year":"2004","unstructured":"Jayram, T.S., Khot, S., Kumar, R., Rabani, Y.: Cell-probe lower bounds for the partial match problem. J. Comput. Syst. Sci. 69(3), 435\u2013447 (2004). https:\/\/doi.org\/10.1016\/j.jcss.2004.04.006","journal-title":"J. Comput. Syst. Sci."},{"key":"1213_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-019-07263-0","author":"D Karapiperis","year":"2019","unstructured":"Karapiperis, D., Gkoulalas-Divanis, A., Verykios, V.S.: Summarizing and linking electronic health records. Distrib. Parallel Datab. (2019). https:\/\/doi.org\/10.1007\/s10619-019-07263-0","journal-title":"Distrib. Parallel Datab."},{"key":"1213_CR46","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pp. 219\u2013241. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-540-68279-0_8","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"1213_CR47","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-24777-7_11","volume-title":"The Multiple-Choice Knapsack Problem","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: The Multiple-Choice Knapsack Problem, pp. 317\u2013347. Springer, Berlin, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7_11"},{"issue":"1","key":"1213_CR48","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3277006.3277015","volume":"47","author":"P Konda","year":"2018","unstructured":"Konda, P., et al.: Technical perspective: toward building entity matching management systems. SIGMOD Record 47(1), 33\u201340 (2018). https:\/\/doi.org\/10.1145\/3277006.3277015","journal-title":"SIGMOD Record"},{"key":"1213_CR49","doi-asserted-by":"publisher","unstructured":"Kum, H.C., Ragan, E.D., Ilangovan, G., Ramezani, M., Li, Q., Schmit, C.: Enhancing privacy through an interactive on-demand incremental information disclosure interface: applying privacy-by-design to record linkage. In: Fifteenth USENIX Conference on Usable Privacy and Security, pp. 175\u2013189 (2019). https:\/\/doi.org\/10.5555\/3361476.3361489","DOI":"10.5555\/3361476.3361489"},{"issue":"2","key":"1213_CR50","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1136\/amiajnl-2013-002165","volume":"21","author":"HC Kum","year":"2014","unstructured":"Kum, H.C., Krishnamurthy, A., Machanavajjhala, A., Reiter, M.K., Ahalt, S.: Privacy preserving interactive record linkage (PPIRL). J. Am. Med. Inform. Assoc. 21(2), 212\u2013220 (2014). https:\/\/doi.org\/10.1136\/amiajnl-2013-002165","journal-title":"J. Am. Med. Inform. Assoc."},{"key":"1213_CR51","unstructured":"Kumar, P.S., Arasada, P., Jammalamadaka, R.C.: Systems and Methods for Generating Search Query Rewrites. U.S. Patent US10108712B2 (granted to ebay) (2018)"},{"key":"1213_CR52","doi-asserted-by":"publisher","unstructured":"Lewenstein, M., Nekrich, Y., Vitter, J.S.: Space-efficient string indexing for wildcard pattern matching. In: 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 506\u2013517 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.506","DOI":"10.4230\/LIPIcs.STACS.2014.506"},{"key":"1213_CR53","doi-asserted-by":"publisher","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Nabeshima, K., Nagasaka, K., Winkler, F., Sz\u00e1nt\u00f3, \u00c1. (eds.) International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, Kobe, Japan, July 23\u201325, 2014, pp. 296\u2013303. ACM (2014). https:\/\/doi.org\/10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"key":"1213_CR54","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.tcs.2014.09.003","volume":"557","author":"M Lewenstein","year":"2014","unstructured":"Lewenstein, M., Munro, J.I., Raman, V., Thankachan, S.V.: Less space: Indexing for queries with wildcards. Theor. Comput. Sci. 557, 120\u2013127 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.09.003","journal-title":"Theor. Comput. Sci."},{"key":"1213_CR55","doi-asserted-by":"publisher","unstructured":"Lincoln, A., Williams, V.V., Williams, R.R.: Tight hardness for shortest cycles and paths in sparse graphs. In: 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1236\u20131252 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.80","DOI":"10.1137\/1.9781611975031.80"},{"issue":"1","key":"1213_CR56","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"PB Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. 57(1), 37\u201349 (1998). https:\/\/doi.org\/10.1006\/jcss.1998.1577","journal-title":"J. Comput. Syst. Sci."},{"key":"1213_CR57","unstructured":"North Carolina Voter Registration database (dataset ncvoter_Statewide.zip). https:\/\/dl.ncsbe.gov\/?prefix=data\/ (2020)"},{"key":"1213_CR58","doi-asserted-by":"publisher","DOI":"10.1145\/3377455","author":"G Papadakis","year":"2020","unstructured":"Papadakis, G., Skoutas, D., Thanos, E., Palpanas, T.: Blocking and filtering techniques for entity resolution: a survey. ACM Comput. Surv. (2020). https:\/\/doi.org\/10.1145\/3377455","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"1213_CR59","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M P\u01cetra\u015fcu","year":"2011","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40(3), 827\u2013847 (2011). https:\/\/doi.org\/10.1137\/09075336X","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1213_CR60","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1137\/070684859","volume":"39","author":"M P\u01cetra\u015fcu","year":"2009","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Higher lower bounds for near-neighbor and further rich problems. SIAM J. Comput. 39(2), 730\u2013741 (2009). https:\/\/doi.org\/10.1137\/070684859","journal-title":"SIAM J. Comput."},{"key":"1213_CR61","doi-asserted-by":"publisher","unstructured":"Pisanti, N., Crochemore, M., Grossi, R., Sagot, M.: A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum. In: 28th International Symposium on Mathematical Foundations of Computer Science 2003 (MFCS), Lecture Notes in Computer Science, vol. 2747, pp. 622\u2013631. Springer, New York (2003). https:\/\/doi.org\/10.1007\/978-3-540-45138-9_56","DOI":"10.1007\/978-3-540-45138-9_56"},{"issue":"1","key":"1213_CR62","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1109\/TCBB.2005.5","volume":"2","author":"N Pisanti","year":"2005","unstructured":"Pisanti, N., Crochemore, M., Grossi, R., Sagot, M.: Bases of motifs for generating repeated patterns with wild cards. IEEE\/ACM Trans. Comput. Biol. Bioinf. 2(1), 40\u201350 (2005). https:\/\/doi.org\/10.1109\/TCBB.2005.5","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"1213_CR63","doi-asserted-by":"publisher","unstructured":"Ragan, E.D., Kum, H.C., Ilangovan, G., Wang, H.: Balancing privacy and information disclosure in interactive record linkage with visual masking. In: ACM Conference on Human Factors in Computing Systems (CHI 2018) (2018). https:\/\/doi.org\/10.1145\/3173574.3173900","DOI":"10.1145\/3173574.3173900"},{"issue":"1","key":"1213_CR64","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0205003","volume":"5","author":"RL Rivest","year":"1976","unstructured":"Rivest, R.L.: Partial-match retrieval algorithms. SIAM J. Comput. 5(1), 19\u201350 (1976). https:\/\/doi.org\/10.1137\/0205003","journal-title":"SIAM J. Comput."},{"key":"1213_CR65","doi-asserted-by":"publisher","unstructured":"Samarati, P., Sweeney, L.: Generalizing data to provide anonymity when disclosing information (abstract). In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1998), p. 188. Association for Computing Machinery (1998). https:\/\/doi.org\/10.1145\/275487.275508","DOI":"10.1145\/275487.275508"},{"key":"1213_CR66","unstructured":"Samarati, P., Sweeney, L.: Protecting Privacy When Disclosing Information: $$k$$-Anonymity and Its Enforcement Through Generalization and Suppression. Tech. rep, Computer Science Laboratory, SRI International (1998)"},{"issue":"6","key":"1213_CR67","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1109\/69.971193","volume":"13","author":"P Samarati","year":"2001","unstructured":"Samarati, P.: Protecting respondents\u2019 identities in microdata release. IEEE Trans. Knowl. Data Eng. 13(6), 1010\u20131027 (2001). https:\/\/doi.org\/10.1109\/69.971193","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"1213_CR68","doi-asserted-by":"publisher","unstructured":"Santos, R.J., Bernardino, J., Vieira, M.: A data masking technique for data warehouses. In: 15th International Database Engineering and Applications Symposium (IDEAS 2011), pp. 61\u201369 (2011). https:\/\/doi.org\/10.1145\/2076623.2076632","DOI":"10.1145\/2076623.2076632"},{"key":"1213_CR69","unstructured":"Secure critical data with Oracle Data Safe (white paper). https:\/\/www.oracle.com\/a\/tech\/docs\/dbsec\/data-safe\/wp-security-data-safe.pdf (2020)"},{"key":"1213_CR70","unstructured":"Sweeney, L.: Computational disclosure control: a primer on data privacy protection. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (2001). http:\/\/hdl.handle.net\/1721.1\/8589"},{"key":"1213_CR71","unstructured":"Tan, Z., Xu, C., Jiang, M., Yang, H., Wu, X.: Query rewrite for null and low search results in ecommerce. In: SIGIR Workshop On eCommerce, CEUR Workshop Proceedings, vol. 2311 (2017)"},{"key":"1213_CR72","doi-asserted-by":"publisher","unstructured":"Tao, Y.: Entity matching with active monotone classification. In: 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2018), pp. 49\u201362 (2018). https:\/\/doi.org\/10.1145\/3196959.3196984","DOI":"10.1145\/3196959.3196984"},{"key":"1213_CR73","doi-asserted-by":"publisher","unstructured":"Vatsalan, D., Christen, P.: Scalable privacy-preserving record linkage for multiple databases. In: 23rd ACM International Conference on Information and Knowledge Management (CIKM 2014), pp. 1795\u20131798 (2014). https:\/\/doi.org\/10.1145\/2661829.2661875","DOI":"10.1145\/2661829.2661875"},{"key":"1213_CR74","doi-asserted-by":"publisher","unstructured":"Vatsalan, D., Sehili, Z., Christen, P., Rahm, E.: Privacy-preserving record linkage for Big Data: Current approaches and research challenges. In: Handbook of Big Data Technologies, pp. 851\u2013895. Springer, New York (2017). https:\/\/doi.org\/10.1007\/978-3-319-49340-4","DOI":"10.1007\/978-3-319-49340-4"},{"key":"1213_CR75","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), pp. 1\u201311. IEEE Computer Society (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"},{"key":"1213_CR76","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: 2018 International Congress of Mathematicians (ICM), pp. 3447\u20133487 (2019). https:\/\/doi.org\/10.1142\/9789813272880_0188","DOI":"10.1142\/9789813272880_0188"},{"issue":"1","key":"1213_CR77","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jagm.1997.0875","volume":"25","author":"AC Yao","year":"1997","unstructured":"Yao, A.C., Yao, F.F.: Dictionary look-up with one error. J. Algorithms 25(1), 194\u2013202 (1997). https:\/\/doi.org\/10.1006\/jagm.1997.0875","journal-title":"J. Algorithms"},{"issue":"1","key":"1213_CR78","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01213-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01213-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01213-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T07:03:35Z","timestamp":1716361415000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01213-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,6]]},"references-count":78,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1213"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01213-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,3,6]]},"assertion":[{"value":"1 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}