Abstract
Cyber security is a critical modern concern. Network intrusion detection systems (NIDS) perform protocol analysis, content searching and content matching, in order to detect harmful software. The high performance demands of NIDS applications in both speed and space consumption, as well as the diverse characteristics of the scenario conditions, have motivated a recent line of research on several formal problems all within the broad scope of dictionary matching with gaps. The goal of this paper is to supply a comparative survey of this line of research in terms of the problems, the formally proven limitations of any solution suggested, the techniques developed to deal with the limitations and different problems, to supply complementary techniques, and finally, to point out existing challenges still to be handled by future work.
Similar content being viewed by others
Notes
The closely related problem of deciding whether a given vertex is contained by any triangle (a decision version) has been addressed [44].
If \(\min \{|{\varSigma }|!,d_s\cdot {{{ plsc }}}\cdot (\beta -\alpha )\}=|{\varSigma }|!\), where \(d_s\) is the number of vertices in \(G_D\), lookup tables with hashing may be a better solution.
References
Krishnamurthy, M., Seagren, E.S., Alder, R., Bayles, A.W., Burke, J., Carter, S., Faskha, E.: How to Cheat at Securing Linux. Syngress Publishing Inc., Elsevier Inc (2008)
Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333–340 (1975)
Amir, A., Călinescu, G.: Alphabet-independent and scaled dictionary matching. J. Algorithms 36(1), 34–62 (2000)
Amir, A., Farach, M., Galil, Z., Giancarlo, R., Park, K.: Dynamic dictionary matching. J. Comput. Syst. Sci. 49(2), 208–222 (1994)
Amir, A., Farach, M., Idury, R.M., Poutré, J.A.L., Schäffer, A.A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258–282 (1995)
Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms 37(2), 309–325 (2000)
Brodal, G.S., Gasieniec, L.: Approximate dictionary queries. In: 7th Annual Symposium on Combinatorial Pattern Matching CPM (Laguna Beach, California, USA), June 10–12, pp. 65–74 (1996)
Cole, R., Gottlieb, L., Lewenstein, M., Dictionary matching and indexing with errors and don’t cares. In: Proceedings 36th Annual ACM Symposium on the Theory of Computing (STOC), ACM Press, pp. 91–100 (2004)
Idury, R.M., Schäffer, A.A.: Multiple matching of parameterized patterns. Theor. Comput. Sci. 154(2), 203–224 (1996)
Kleene, S.C.: Representation of events in nerve nets and finite automata
Bille, P., Farach-Colton, M.: Fast and compact regular expression matching. Theor. Comput. Sci. 409(3), 486–496 (2008)
Bille, P., Thorup, M.: Regular expression matching with multi-strings and intervals. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17–19, 2010 (Moses Charikar, ed.), SIAM, pp. 1297–1308 (2010)
Myers, E.W.: A four russians algorithm for regular expression pattern matching. J. ACM 39(2), 430–448 (1992)
Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap! online dictionary matching with one gap. Algorithmica 81(6), 2123–2157 (2019)
Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap: essentially optimal algorithms for online dictionary matching with one gap. In: 27th International Symposium on Algorithms and Computation, ISAAC (Sydney, Australia), December 12–14, pp. 12:1–12:12 (2016)
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Online recognition of dictionary with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 28–30, pp. 3–17 (2017)
Verint Systems, Personal communication. 2013, Addres: Maskit St. 33 Herzliya Israel
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with a few gaps. Theor. Comput. Sci. 589, 34–46 (2015)
Chase, M., Shen, E.: Substring-searchable symmetric encryption. PoPETs 2015(2), 263–281 (2015)
Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. ACM CCS 06 (Ari Juels Rebecca N. Wright and Sabrina De Capitani di Vimercati, eds.), ACM Press, pp. 9–88 (2006)
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: IEEE Symposium on Security and Privacy IEEE Computer Society Press, pp. 44–55 (2000)
Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. EUROCRYPT 2004 (Christian Cachin and Jan Camenisch, eds.), LNCS, vol. 3027, Springer, pp. 506–522 (2004)
Desmoulins, N., Fouque, P.A., Onete, C., Sanders, O.: Pattern matching on encrypted streams, ASIACRYPT (2018)
Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, CA, USA), May 16–18, pp. 71–80 (1993)
Shalom, B.R.: Parameterized dictionary matching with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), pp. 103–116 (2018)
Shalom, B.R.: Parameterized dictionary matching and recognition with one gap. Theor. Comput. Sci. 854, 1–16 (2021)
Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. In: Stringology (Proceedings of the Prague Stringology Conference), pp. 41–55 (2019)
Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. Submitted for publication (2020)
Burr, S.A., Erdős, P.: On the magnitude of generalized ramsey numbers for graphs. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday) (János Bolyai, ed.), Colloq. Math. Soc., vol. 1, 1975, p. 214–240
Kucherov, G., Rusinowitch, M.: Matching a set of strings with variable length don’t cares. Theor. Comput. Sci. 178(12), 129–154 (1997)
Zhang, M., Zhang, Y., Hu, L.: A faster algorithm for matching a set of patterns with variable length don’t cares. Inf. Process. Lett. 110(6), 216–220 (2010)
Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: 10th International Symposium on Experimental Algorithms SEA (Kolimpari, Chania, Crete, Greece), May 5–7, pp. 76–87 (2011)
Hon, W., Lam, T.W., Shah, R., Thankachan, S.V., Ting, H., Yang, Y.: Dictionary matching with a bounded gap in pattern or in text. Algorithmica 80(2), 698–713 (2018)
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with one gap. In: The Proceedings of the 25th Symposium on Combinatorial Pattern Matching (CPM), pp. 11–20 (2014)
Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS. pp. 434–443 (2014)
Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. FOCS 621–630 (2014)
Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3sum conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2016)
Pǎtraşcu, M.: Towards polynomial lower bounds for dynamic problems. STOC 603–610 (2010)
Bjørklund, A., Pagh, R., Vassilevska Williams, V., Zwick, U.: Listing triangles. In: Proceedings 41st Int’l Colloquium on Automata, Languages, and Programming (ICALP (I)), pp. 223–234 (2014)
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph 7(4), 413–423 (1978)
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. (SICOMP) 14(1), 210–223 (1985)
Pettie, S., Kopelowitz, T., Porat, E.: Dynamic set intersection. WADS (2015)
Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40–42), 3795–3800 (2010)
Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. Theory Comput. 8(1), 69–94 (2012)
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Online recognition of dictionary with one gap. Inf. Comput. 275, 104633 (2020)
Mortensen, C.W.: Fully dynamic orthogonal range reporting on RAM. SIAM J. Comput. 35(6), 1494–1525 (2006)
Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett. 49(3), 111–115 (1994)
Baker, B.S.: Parameterized duplication in strings: algorithms and an application to software maintenance. SIAM J. Comput. 26(5), 1343–1362 (1997)
Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), September 1–3, pp. 84–94 (2008)
Ferragina, P., Grossi, R.: The string b-tree: a new data structure for string search in external memory and its applications. J. ACM 46(2), 236–280 (1999)
Ganguly, A., Hon, W., Shah, R.: A framework for dynamic parameterized dictionary matching. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory SWAT (Reykjavik, Iceland), June 22–24, pp. 10:1–10:14 (2016)
Keller, O., Kopelowitz, T., Lewenstein, M.: On the longest common parameterized subsequence. Theor. Comput. Sci. 410(51), 5347–5353 (2009)
Lewenstein, M.: Parameterized pattern matching. Encyclopedia of Algorithms 1525–1530,(2016)
Mendivelso, J., Pinzón, Y.: Parameterized matching: Solutions and extensions. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 24–26, pp. 118–131 (2015)
Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \(\theta (n)\). Inf. Process. Lett. 17(2), 81–84 (1983)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Levy, A., Shalom, B.R. A Comparative Study of Dictionary Matching with Gaps: Limitations, Techniques and Challenges. Algorithmica 84, 590–638 (2022). https://doi.org/10.1007/s00453-021-00851-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-021-00851-6