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

• US 9,589,073 B2
• Filed: 04/28/2014
• Issued: 03/07/2017
• Est. Priority Date: 04/28/2013
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Yishay, Yitshak
• Primary Examiner(s): Burke, Jeffrey A
• Assistant Examiner(s): Vu, Thong
• Application Number:
  US14/263,108
• Publication Number:
  US 20150310014A1
• Time in Patent Office: 1,044 Days
• Field of Search: 707/728, 707/758, 707/798, 707/710, 707/771, 707/748, 707/713, 706/48, 382/176, 382/181, 382/218, 345/168
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2483 involving identification of individual flows

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.

Claims

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 from a communication network, the input communication traffic comprising multiple flows of network packets exchanged in the communication network, the input communication traffic being received 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 comprising at least one import port and at least a first and second output port, wherein the at least one input port is configured to receive the input communication traffic from the NIC, wherein the data splitter is configured by the processor to assign the input communication traffic and the patterns to multiple different pattern matching algorithms by at least directing certain segments of the multiple flows to the first output port and directing other segments of the multiple flows to the second output port in accordance with an initial splitting configuration policy, wherein the first output port is associated with a first pattern matching algorithm and wherein the second output port is associated with a second pattern matching algorithm, wherein the at least a first pattern of the set of patterns is assigned to 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 the textual phrases of the assigned patterns in the network packets, wherein the execution comprises the first pattern matching algorithm searching within the segments sent from the first output port for the one or more textual phrases of the first assigned pattern and the second pattern matching algorithm searching within the segments sent from the second output port 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;

generating, by the processor, an updated splitting policy configuration for the data splitter based on the monitored performance that reassigns which segments of the multiple flows of the input communication traffic are assigned to which output ports of the data splitter and which pattern of the set of patterns are assigned to which pattern matching algorithms; and

configuring 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

a memory size occupied by the assigned pattern.

9. An apparatus for identifying textual phrases of interest in input data, comprising:

a network interface card (NIC) configured to receive input communication traffic from a communication network, the input communication traffic comprising multiple flows of network packets exchanged in the communication network, the input communication traffic being received 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 comprising at least one import port and at least a first and second output port, wherein the at least one import port is configured to receive the input communication traffic from the NIC, wherein the data splitter is configured by the processor to assign the input communication traffic and the patterns to multiple different pattern matching algorithm by at least directing certain segments of the multiple flows to the first output port and directing other segments of the multiple flows to the second output port in accordance with an initial splitting configuration policy, wherein the first output port is associated with a first pattern matching algorithm and wherein the second output port is associated with a second pattern matching algorithm, wherein the at least a first pattern of the set of patterns is assigned to first pattern matching algorithm and wherein at least a second pattern of the set of patterns is assigned to the second pattern matching algorithm;

execute the first and second pattern matching algorithms to identify occurrences of the textual phrases of the assigned patterns in the network packets, wherein the execution comprises the first pattern matching algorithm searching within the segments sent from the first output port for the one or more textual phrases of the first assigned pattern and the second pattern matching algorithm searching within the segments sent from the second output port 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 an updated splitting policy configuration for the data splitter based on the monitored performance that reassigns which segments of the multiple flows of the input communication traffic are assigned to which output ports of the data splitter and which pattern of the set of patterns are 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

a memory size occupied by the assigned patterns.