Systems and methods for keyword spotting using adaptive management of multiple pattern matching algorithms

Abstract

Methods and systems for keyword spotting, i.e., for identifying textual phrases of interest in input data. The input data may be communication packets exchanged in a communication network. A keyword spotting system holds a dictionary (or dictionaries) of textual phrases for searching input data. The input data and the patterns are assigned to multiple different pattern matching algorithms. For example, a share of the traffic is handled by one algorithm and smaller traffic shares may be handled by the others. The system monitors the algorithms performance as they process the data to search for a match. The ratio of traffic splitting among the algorithms is dynamically reassigned or adjusted to maximize the overall performance.

1 . A method for identifying textual phrases of interest in input data, the method being performed by an apparatus comprising a network interface card (NIC) and a processor, the method comprising:
 receiving, by the NIC, input communication traffic to be searched for occurrences of a set of patterns, wherein each pattern of the set of patterns comprises one or more textual phrases;   configuring by the processor, a data splitter in accordance with an initial splitting configuration policy to assign the input communication traffic and the patterns to multiple different pattern matching algorithms, in which certain segments of the input communication traffic are assigned to a first pattern matching algorithm and certain segments are assigned to a second pattern matching algorithm, wherein at least a first pattern of the set of patterns is assigned to the first pattern matching algorithm and wherein at least a second pattern of the set of patterns is assigned to the second pattern matching algorithm;   executing, by the processor, the first and second pattern matching algorithms to identify occurrences of textual phrases from the respective first and second patterns in the communication traffic, wherein the execution comprises the first pattern matching algorithm searching within certain for the one or more textual phrases of the first assigned pattern and comprises the second pattern matching algorithm searching within certain segments for the one or more textual phases of the second assigned pattern;   monitoring, by the processor, performance of the first and second pattern matching algorithms by evaluating a predetermined metric for each of the first and second pattern matching algorithms; and   generating, by the processor, for the data splitter, based on the monitored performance, an updated splitting policy configuration that reassigns which segments of the input communication traffic are assigned to which pattern matching algorithm and or which pattern of the set of patterns is assigned to which pattern matching algorithm; and   configuring, by the processor, the data splitter in accordance with the updated splitting policy configuration.   
     
     
         2 . The method according to  claim 1 , wherein evaluating the predefined metric comprises assessing a performance measure of the pattern matching algorithms. 
     
     
         3 . The method according to  claim 1 , wherein evaluating the predefined metric comprises assessing a characteristic of the input communication traffic. 
     
     
         4 . The method according to  claim 1 , wherein assigning the input communication traffic and the patterns comprises applying each of the pattern matching algorithms to search a respective subset of the input communication traffic for the occurrences of all the patterns. 
     
     
         5 . The method according to  claim 4 , wherein reassigning the input communication traffic and the patterns comprises reassigning a portion of the input communication traffic from the first pattern matching algorithm to the second pattern matching algorithm. 
     
     
         6 . The method according to  claim 1 , wherein assigning the input communication traffic and the patterns comprises defining one of the pattern matching algorithms as a primary algorithm and assigning a majority of the input communication traffic to the primary algorithm, and wherein reassigning the input data and the patterns comprises redefining another of the pattern matching algorithms to serve as the primary algorithm and shifting the majority of the input communication traffic to the redefined primary algorithm. 
     
     
         7 . The method according to  claim 1 , wherein assigning the input communication traffic and the patterns comprises applying each of the pattern matching algorithms to search all the input communication traffic for the occurrences of a respective subset of the patterns. 
     
     
         8 . The method according to  claim 1 , wherein evaluating the metric comprises evaluating at least one metric type selected from a group of types consisting of:
 a volume of the input communication traffic processed by a given pattern matching algorithm per unit time;   a memory size occupied by the assigned patterns; and   the memory size used for maintaining state machines of respective flows of the input communication traffic.   
     
     
         9 . An apparatus for identifying textual phrases of interest in input data, comprising:
 a network interface card (NIC) configured to receive input communication traffic that is to be searched for occurrences of a set of patterns, wherein each pattern of the set of patterns comprises one or more textual phrases; and   a processor configured to:
 configure a data splitter in accordance with an initial splitting configuration policy to assign the input communication traffic and the patterns to multiple different pattern matching algorithms, in which certain segments of the input communication traffic are assigned to a first pattern matching algorithm and certain segments are assigned to a second pattern matching algorithm; 
 execute the first and second pattern matching algorithms to identify occurrences of textual phrases from the respective first and second patterns in the communication traffic, wherein the execution comprises the first pattern matching algorithm searching within certain for the one or more textual phrases of the first assigned pattern and comprises the second pattern matching algorithm searching within certain segments for the one or more textual phases of the second assigned pattern; 
 monitor performance of the first and second pattern matching algorithms by evaluating a predetermined metric for each of the first and second pattern matching algorithms; 
 generate, for the data splitter, based on the monitored performance, an updated splitting policy configuration that reassigns which segments of the input communication traffic are assigned to which pattern matching algorithm and or which pattern of the set of patterns is assigned to which pattern matching algorithm; and 
 configure the data splitter in accordance with the updated splitting policy configuration. 
   
     
     
         10 . The apparatus according to  claim 9 , wherein the processor is configured to evaluate the predefined metric by assessing a performance measure of the pattern matching algorithms. 
     
     
         11 . The apparatus according to  claim 9 , wherein the processor is configured to evaluate the predefined metric by assessing a characteristic of the input communication traffic. 
     
     
         12 . The apparatus according to  claim 9 , wherein the processor is configured to assign the input communication traffic and the patterns by applying each of the pattern matching algorithms to search a respective subset of the input communication traffic for the occurrences of all the patterns. 
     
     
         13 . The apparatus according to  claim 12 , wherein the processor is configured to reassign the input communication traffic and the patterns by reassigning a portion of the input communication traffic from the first pattern matching algorithm to the second pattern matching algorithm. 
     
     
         14 . The apparatus according to  claim 9 , wherein the processor is configured to define one of the pattern matching algorithms as a primary algorithm and assigning a majority of the input communication traffic to the primary algorithm, and to reassign the input communication traffic and the patterns by redefining another of the pattern matching algorithms to serve as the primary algorithm and to shift the majority of the input communication traffic to the redefined primary algorithm. 
     
     
         15 . The apparatus according to  claim 9 , wherein the processor is configured to assign the input communication traffic and the patterns by applying each of the pattern matching algorithms to search all the input communication traffic for the occurrences of a respective subset of the patterns. 
     
     
         16 . The apparatus according to  claim 9 , wherein the processor is configured to evaluate the metric by evaluating at least one metric type selected from a group of types consisting of:
 a volume of the input communication traffic processed by a given pattern matching algorithm per unit time;   a memory size occupied by the assigned patterns; and   the memory size used for maintaining state machines of respective flows of the input communication traffic.   
     
     
         17 . A non-transitory computer readable media having instructions stored thereon for identifying textual phrases of interest in input data that, when executed by a computing system, cause the computing device to at least:
 receive input communication traffic that is to be searched for occurrences of a set of patterns, wherein each pattern of the set of patterns comprises one or more textual phrases; and   configure a data splitter in accordance with an initial splitting configuration policy to assign the input communication traffic and the patterns to multiple different pattern matching algorithms, in which certain segments of the input communication traffic are assigned to a first pattern matching algorithm and certain segments are assigned to a second pattern matching algorithm;   execute the first and second pattern matching algorithms to identify occurrences of textual phrases from the respective first and second patterns in the communication traffic, wherein the execution comprises the first pattern matching algorithm searching within certain for the one or more textual phrases of the first assigned pattern and comprises the second pattern matching algorithm searching within certain segments for the one or more textual phases of the second assigned pattern;   monitor performance of the first and second pattern matching algorithms by evaluating a predetermined metric for each of the first and second pattern matching algorithms;   generate, for the data splitter, based on the monitored performance, an updated splitting policy configuration that reassigns which segments of the input communication traffic are assigned to which pattern matching algorithm and or which pattern of the set of patterns is assigned to which pattern matching algorithm; and   configure the data splitter in accordance with the updated splitting policy configuration.   
     
     
         18 . The non-transitory computer readable media according to  claim 17 , wherein the computing device is configured to assign the input communication traffic and the patterns by applying each of the pattern matching algorithms to search a respective subset of the input communication traffic for the occurrences of all the patterns. 
     
     
         19 . The non-transitory computer readable media according to  claim 18 , wherein the computing device is configured to reassign the input communication traffic and the patterns by reassigning a portion of the input communication traffic from the first pattern matching algorithm to the second pattern matching algorithm. 
     
     
         20 . The non-transitory computer readable media according to  claim 17 , wherein the computing device is configured to evaluate the metric by evaluating at least one metric type selected from a group of types consisting of:
 a volume of the input communication traffic processed by a given pattern matching algorithm per unit time;   a memory size occupied by the assigned patterns; and   the memory size used for maintaining state machines of respective flows of the input communication traffic.