Substring search algorithm optimized for hardware acceleration

Details Substring search algorithm optimized for hardware acceleration Substring search algorithm optimized for hardware acceleration

2011-05-10

2011-05-10

Arani, Taghi T. (Department: 2438)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

C713S190000, C726S024000, C708S252000, C377S072000

Reexamination Certificate

active

07941435

ABSTRACT:
Techniques are provided for generating a hash value for searching for substrings in a data stream without reading more than one element (e.g. one byte) at a time. According to one technique, a before a next element is added to an old hash value, the old hash value is circularly shifted one or more bits. The first original element is shifted a number of bits and XOR'ed against the old hash value. The next element is added to the old hash value. In one embodiment, an entry value is retrieved for each element from an index table and the XOR and shift operations are performed on the entry values. According to another technique, each Linear Feedback Shift Register (LFSR) of a plurality of LFSRs read in one element at a time beginning at different offsets. Each LFSR uses the same state machine. The result of reading a number of elements into an LFSR is used as the hash value.

REFERENCES:
patent: 6785389 (2004-08-01), Sella et al.
patent: 7366910 (2008-04-01), Hanner
patent: 2002/0053002 (2002-05-01), Brandin
patent: 2002/0172179 (2002-11-01), Grimsrud
patent: 2006/0212426 (2006-09-01), Shakara et al.
patent: 2007/0244951 (2007-10-01), Gressel et al.
Erdogan, Ozgun et al., “Hash-AV: Fast Virus Signature Scanning by Cache-Resident Filters” Department of Computer Science, Stanford University, 9 pages.
“The Rabin-Karp Algorithm” downloaded Oct. 18, 2006: http://www.eecs.harvard.edu/˜ellard/Q-97/HTML/root
ode43.html, 4 pages.

Affiliated with

Also associated with

Rating

Substring search algorithm optimized for hardware acceleration does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Substring search algorithm optimized for hardware acceleration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Substring search algorithm optimized for hardware acceleration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2626689