Intel Corporation
HIGH-PERFORMANCE MULTI-LITERAL MATCHING ALGORITHM

Abstract:

Methods, software, and apparatus for implementing a high-performance multi-literal matching algorithm. Under aspects of a method, multi-literal matching is used during front-end processing to identify match candidates based on suffix patterns. An extended SHIFT-OR algorithm is performed using the chunk of data as an input to identify match candidates for the suffix patterns, wherein the extended SHIFT-OR algorithm shifts match indicia in the plurality of rows across predetermined bit boundaries and aligns the match indicia corresponding to target suffixes into single columns. Match candidates are indicated when OR'ed column values yield a `0`. Match verification for one or more search strings containing the suffix patterns is then performed by a back-end. The scheme eliminates false positives at the predetermined bit boundaries, providing substantial improvement in front-end accuracy and performance.