High-speed data searching apparatus and method capable of operation in retrospective and dissemination modes

• US 5,379,420 A
• Filed: 12/26/1991
• Issued: 01/03/1995
• Est. Priority Date: 12/26/1991
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: TRW Limited (Zeppelin - Stiftung der Stadt Friedrichshafen)
• Inventors: Ullner, Michael K.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/813,636
• Time in Patent Office: 1,104 Days
• Field of Search: 340/146.2, 395/600, 395/425, 395/800, 365/49
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A highly versatile data search engine in which multiple search cells are connected together in a pipeline through which data can be streamed. Each cell has multiple registers, and corresponding registers in each cell are connected together to form the pipeline. Characters in two data streams are compared in the pipeline, a first data stream that includes a sequence of database characters and parallel sequences of associated data, and a second data stream that includes a sequence of pattern characters and parallel sequences of associated data. The parallel data sequences associated with the pattern data include coded signals that control cell operation. One of the parallel data sequences associated with the database is a sequence of character marks, which are used to indicate search starting points in the database character sequence, and which are propagated along the database character sequence as a result of successive character matches between the pattern and database characters. Use of the character marks facilitates searches in both forward and reverse directions, and permits selected database characters to be ignored. The search engine can be operated in either a retrospective mode, in which the database is streamed through cells containing a stationary pattern, or in dissemination mode, in which patterns are streamed through cells containing a stationary database.

Claims

1. High speed data searching apparatus capable of operation in retrospective and dissemination modes, the apparatus comprising:

a plurality of functionally identical search cells, wherein each search cell includes a plurality of registers;

means for connecting corresponding registers in each cell together to form a number of serially connected pipelines of registers through which data can be passed;

means for inputting into the apparatus a first data stream from a database to be searched; and

means for inputting into the apparatus a second data stream defining a pattern to be searched for in the database;

wherein each search cell includes means for comparing a database character with a pattern character and means for controlling further operation of the cell in response to the result of each such comparison;

and wherein some of the registers in each cell are designated to hold a database character and associated data, and others of the registers are designated to hold a pattern character and associated data;

and wherein either one of the data streams is first stored in the designated registers of the search cells, and then the other of the data streams is streamed through the search cells to perform the search, whereby the search may be performed in either a retrospective mode in which pattern characters are first stored in and database characters are then streamed through the apparatus, or in a dissemination mode in which database characters are first stored in and pattern characters are then streamed through the apparatus;

and wherein the first data stream includes a sequence of database characters and parallel sequences of associated data, one of the parallel sequences being a sequence of character marks, and wherein a character mark of a particular state indicates that the corresponding database character is to be compared with a pattern character in any cell in which both characters are present.

2. Apparatus as defined in claim 1, wherein:

the means for comparing a database character with a pattern character provides a match signal for any selected condition of equality or inequality, including having one character equal to the other, or having the equivalent numerical value of one character greater than or less than that of the other.

3. Apparatus as defined in claim 1, wherein:

the second data stream, containing the pattern characters and associated data, is shifted into the search cells prior to the search;

the first data stream, containing the database characters and associated data, is streamed through the search cells during the search; and

the search is of the retrospective type, to locate relatively small patterns in a large database.

4. Apparatus as defined in claim 1, wherein:

the first data stream, containing the database characters and associated data, is shifted into the search cells prior to the search;

the second data stream, containing the pattern characters and associated data, is streamed through the search cells during the search; and

the search is of the dissemination type, to locate a relatively large number of patterns in a relatively small database.

5. High speed data searching apparatus capable of operation in retrospective and dissemination modes, the apparatus comprising:

a plurality of functionally identical search cells, wherein each search cell includes a plurality of registers;

means for connecting corresponding registers in each cell together to form a number of serially connected pipelines of registers through which data can be passed;

means for inputting into the apparatus a first data stream from a database to be searched;

means for inputting into the apparatus a second data stream defining a pattern to be searched for in the database;

wherein each search cell includes means for comparing a database character with a pattern character and means for controlling further operation of the cell in response to the result of each such comparison;

and wherein some of the registers in each cell are designated to hold a database character and associated data, and others of the registers are designated to hold a pattern character and associated data;

and wherein either one of the data streams is first stored in the designated registers of the search cells, and then the other of the data streams is streamed through thee search cells to perform the search, whereby the search may be performed in either a retrospective mode in which pattern characters are first stored in and database characters are then streamed through the apparatus, or in a dissemination mode in which database characters are first stored in and pattern characters are then streamed through the apparatus;

and wherein

the first data stream includes a sequence of database characters and parallel sequences of associated data, one of the parallel sequences being a sequence of character marks;

the second data stream includes a sequence of pattern characters and parallel sequences of coded data that determine the manner in which comparisons and other functions are performed in each element of the pattern; and

a character mark of a particular state indicates that the corresponding database character is to be compared with a pattern character in any cell in which both characters are present.

6. Apparatus as defined in claim 5, wherein:

each cell further includes means for shifting any of the parallel sequences of data associated with the database characters in either direction with respect to the sequence of database characters, whereby a mark associated with a particular database character may be shifted to and associated with a neighboring database character.

7. Apparatus as defined in claim 6, wherein:

each cell further includes means for modifying data in any of the parallel sequences associated with the database characters, as determined by code contained within the parallel sequences of coded data associated with the pattern characters, and conditioned as desired on the results of any comparison operation performed in the cell, whereby a cell has the ability to mark or unmark a database character currently present in one of the cell'"'"'s registers.

8. Apparatus as defined in claim 7, wherein:

the parallel sequences of data in the second data stream are conditioned to have the collective effect of initially marking all of the database characters, extinguishing the marks that do not match a first encountered pattern character, and shifting any remaining marks by one position toward the end of the sequence of database characters;

a second pattern character can be next compared with each database character that is still marked; and

a character mark is propagated toward the end of the sequence of database characters if a matching comparison is made at each successive database character position, whereby a match of all of the pattern characters with a corresponding string of database characters results in a mark being left in a database position immediately following the last character in the matching string.

9. Apparatus as defined in claim 7, wherein:

at least some of the pattern characters in the second data stream are stored in reverse order, to effect a search of the database in reverse sequence;

the parallel sequences of data in the second data stream are conditioned to have the collective effect of initially marking all of the database characters, shifting the marks by one position toward the beginning of the sequence of database characters, and then extinguishing the marks that do not match a first encountered pattern character;

a second pattern character in the reverse sequence of pattern characters can be next compared with each database character that is still marked;

a character mark is propagated toward the beginning of the sequence of database characters if a matching comparison is made at each database character position, whereby a match of all of the pattern characters with a corresponding string of database characters results in a mark being left in a database position corresponding to the first character in the matching string.

10. Apparatus as defined in claim 8, wherein:

one of the parallel sequences of data associated with the sequence of database characters contains an "ignore" flag; and

each cell includes means for ignoring any character in the sequence of database characters when the "ignore" flag accompanies the character, whereby searches can be performed in such a manner that selected characters in the database can be ignored.

11. Apparatus as defined in claim 8, wherein:

one of the parallel sequences of data associated with the sequence of database characters contains a "kill" flag, indicative of a "kill" boundary between a cell containing the flag, in a selected state, and a neighboring cell; and

each cell includes means responsive to detection of the "kill" flag in the selected state, for extinguishing any character mark that would otherwise be propagated across the "kill" boundary in either direction.

12. Apparatus as defined in claim 8, wherein:

each character mark is a numeric value;

each cell includes means, responsive to the coded data in the parallel sequences associated with the sequence of pattern data, for initially setting the numeric marks to a value indicative of a degree to which errors will tolerated in a search; and

each cell further includes means for reducing the numeric value of a mark in the event that no match is found in the cell, whereby nonzero marks still remaining after the search represent pattern matches to within the desired degree of tolerance.

13. Apparatus as defined in claim 12, wherein:

each cell further includes means for assigning different costs to different types of matching errors and to different errors of the same type,

14. Apparatus as defined in claim 13, wherein:

the types of errors that may be detected include misspellings, missing characters and extra characters.

15. A generalized method for searching databases in either retrospective or dissemination mode, the method comprising the steps of:

inputting a first data stream into a pipeline of search cells, each having a plurality of registers, with corresponding registers of each cell being serially connected to form the pipeline, wherein the first data stream contains a sequence of database characters and parallel sequences of other data associated with the database, one of the parallel sequences being a sequence of character marks;

inputting a second data stream into the pipeline of search cells, although not necessarily after input of the first data stream, wherein the second data stream contains a sequence of pattern characters and parallel sequences of other data, including coded data to control operation of the cells, and wherein one of the first and second data streams is shifted into the pipeline prior to a search and the other of the data streams is streamed through the pipeline in performance of the search;

setting all of the character marks to a nonzero value, to mark all of the characters in the database character sequence and to indicate initially that every character is a candidate for the beginning of a search;

comparing each marked database character with a first pattern character;

unmarking all characters that do not match the first pattern character;

shifting any remaining marks toward the end of the sequence of database characters;

comparing each marked database character with subsequent pattern characters in turn; and

after each comparison, unmarking any nonmatching database characters and shifting any remaining marks toward the end of the sequence of database characters;

whereby any string of characters in the database that matches the pattern will be marked at the character position next following the last character in the matching string.

16. A method as defined in claim 15, wherein:

the second data stream, containing the pattern characters and associated data, is shifted into the search cells prior to the search;

the first data stream, containing the database characters and associated data, is streamed through the search cells during the search; and

the search is of the retrospective type, to locate at least one relatively small pattern in a large database.

17. A method as defined in claim 15, wherein:

the first data stream, containing the database characters and associated data, is shifted into the search cells prior to the search;

the second data stream, containing the pattern characters and associated data, is streamed through the search cells during the search;

the search is of the dissemination type, to locate a relatively large pattern or a number of patterns in a relatively small database.

18. A method as defined in claim 15, wherein the method performs a reverse sequence search for a string of pattern characters appearing in reverse order, the method further comprising the steps of:

first shifting any character marks toward the beginning of the sequence of database characters;

then comparing each marked database character with a first of the pattern characters stored in reverse order;

unmarking all characters that do not match the first reverse-order pattern character;

comparing each marked database character with subsequent pattern reverse-order characters in turn and, before each comparing step, shifting any remaining marks toward the beginning of the sequence of database characters; and

after each comparison, unmarking any nonmatching database characters;

whereby any string of characters in the database that matches the reverse-order pattern will be marked at the character position corresponding to the first character in the matching string, which is the last to be compared in the reverse-order pattern.

19. A method as defined in claim 15, wherein the comparing steps include comparing for equality between the compared characters.

20. A method as defined in claim 15, wherein the comparing steps include detecting a selected relationship of inequality between the compared characters.

21. A method as defined in claim 15, and further comprising the steps of:

searching the sequence of database characters for occurrences of at least one selected character that is to be ignored in a search;

tagging each occurrence of the selected character by setting the value of a corresponding item in one of the parallel data sequences associated with the database; and

ignoring the tagged characters in the search for database characters that match the pattern characters.

22. A method as defined in claim 15, and further comprising the steps of:

searching the sequence of database characters for occurrences of at least a selected character that is to the site of a "kill" boundary;

tagging each occurrence of the selected character by setting the value of a corresponding item in one of the parallel data sequences associated with the database; and

during performance of a search, extinguishing a mark when the steps of the search call for shifting the mark across a "kill" boundary.

23. A method as defined in claim 15, wherein:

each character mark has a positive numerical value;

the step of extinguishing a mark is effected by reducing the value of the numerical mark; and

the method further comprises the steps of setting the marks to a selected initial value indicative of a desired degree of error tolerance for the search, and reducing the numerical value of a mark when a nonmatching condition is detected, whereby the numerical values of any marks remaining at the end of the search are indicative of the degree of match for each string of characters located in the sequence of database characters.

24. A method as defined in claim 23, and further comprising the steps of:

selecting a cost for each type of error, wherein different costs may be selected for different types of errors.

25. High speed data searching apparatus, comprising:

a plurality of functionally identical search cells, wherein each search cell includes a plurality of registers;

means for connecting corresponding registers in each cell together to form a number of serially connected pipelines of registers through which data can be passed;

means for inputting into the apparatus a first data stream from a database to be searched; and

means for inputting into the apparatus a second data stream defining a pattern to be searched for in the database;

wherein each search cell includes means for comparing a database character with a pattern character and means for controlling further operation of the cell in response to the result of each such comparison;

and wherein some of the registers in each cell are designated to hold a database character and associated data, and others of the registers are designated to hold a pattern character and associated data;

and wherein either one of the data streams is first stored in the designated registers of the search cells, and then the other of the data streams is streamed through the search cells to perform the search;

and wherein the first data stream includes a sequence of database characters and parallel sequences of associated data, one of the parallel sequences being a sequence of character marks, and wherein a character mark of a particular state indicates that the corresponding database character is to be compared with a pattern character in any cell in which both characters are present.

26. Apparatus as defined in claim 25, wherein:

the means for comparing a database character with a pattern character provides a match signal for any selected condition of equality or inequality, including having one character equal to the other, or having the equivalent numerical value of one character greater than or less than that of the other.

27. Apparatus as defined in claim 25, wherein:

the second data stream, containing the pattern characters and associated data, is shifted into the search cells prior to the search;

the first data stream, containing the database characters and associated data, is streamed through the search cells during the search; and

the search is of the retrospective type, to locate relatively small patterns in a large database.

28. Apparatus as defined in claim 25, wherein:

the first data stream, containing the database characters and associated data, is shifted into the search cells prior to the search;

the second data stream, containing the pattern characters and associated data, is streamed through the search cells during the search; and

the search is of the dissemination type, to locate a relatively large number of patterns in a relatively small database.

29. High speed data searching apparatus, comprising:

a plurality of functionally identical search cells, wherein each search cell includes a plurality of registers;

means for connecting corresponding registers in each cell together to form a number of serially connected pipelines of registers through which data can be passed;

means for inputting into the apparatus a first data stream from a database to be searched; and

means for inputting into the apparatus a second data stream defining a pattern to be searched for in the database;

wherein each search cell includes means for comparing a database character with a pattern character and means for controlling further operation of the cell in response to the result of each such comparison;

and wherein some of the registers in each cell are designated to hold a database character and associated data, and others of the registers are designated to hold a pattern character and associated data;

and wherein either one of the data streams is first stored in the designated registers of the search cells, and then the other of the data streams is streamed through the search cells to perform the search; and

wherein

the first data stream includes a sequence of database characters and parallel sequences of associated data, one of the parallel sequences being a sequence of character marks;

the second data stream includes a sequence of pattern characters and parallel sequences of coded data that determine the manner in which comparisons and other functions are performed in each element of the pattern; and

a character mark of a particular state indicates that the corresponding database character is to be compared with a pattern character in any cell in which both characters are present.

30. Apparatus as defined in claim 29, wherein:

each cell further includes means for shifting any of the parallel sequences of data associated with the database characters in either direction with respect to the sequence of database characters, whereby a mark associated with a particular database character may be shifted to and associated with a neighboring database character.

31. Apparatus as defined in claim 30, wherein:

each cell further includes means for modifying data in any of the parallel sequences associated with the database characters, as determined by code contained within the parallel sequences of coded data associated with the pattern characters, and conditioned as desired on the results of any comparison operation performed in the cell, whereby a cell has the ability to mark or unmark a database character currently present in one of the cell'"'"'s registers.

32. Apparatus as defined in claim 31, wherein:

the parallel sequences of data in the second data stream are conditioned to have the collective effect of initially marking all of the database characters, extinguishing the marks that do not match a first encountered pattern character, and shifting any remaining marks by one position toward the end of the sequence of database characters;

a second pattern character can be next compared with each database character that is still marked; and

a character mark is propagated toward the end of the sequence of database characters if a matching comparison is made at each successive database character position, whereby a match of all of the pattern characters with a corresponding string of database characters results in a mark being left in a database position immediately following the last character in the matching string.

33. Apparatus as defined in claim 31, wherein:

at least some of the pattern characters in the second data stream are stored in reverse order, to effect a search of the database in reverse sequence;

the parallel sequences of data in the second data stream are conditioned to have the collective effect of initially marking all of the database characters, shifting the marks by one position toward the beginning of the sequence of database characters, and then extinguishing the marks that do not match a first encountered pattern character;

a second pattern character in the reverse sequence of pattern characters can be next compared with each database character that is still marked;

a character mark is propagated toward the beginning of the sequence of database characters if a matching comparison is made at each database character position, whereby a match of all of the pattern characters with a corresponding string of database characters results in a mark being left in a database position corresponding to the first character in the matching string.

34. Apparatus as defined in claim 32, wherein:

one of the parallel sequences of data associated with the sequence of database characters contains an "ignore" flag; and

each cell includes means for ignoring any character in the sequence of database characters when the "ignore" flag accompanies the character, whereby searches can be performed in such a manner that selected characters in the database can be ignored.

35. Apparatus as defined in claim 32, wherein:

one of the parallel sequences of data associated with the sequence of database characters contains a "kill" flag, indicative of a "kill" boundary between a cell containing the flag, in a selected state, and a neighboring cell; and

each cell includes means responsive to detection of the "kill" flag in the selected state, for extinguishing any character mark that would otherwise be propagated across the "kill" boundary in either direction.

36. Apparatus as defined in claim 32, wherein:

each character mark is a numeric value;

each cell includes means, responsive to the coded data in the parallel sequences associated with the sequence of pattern data, for initially setting the numeric marks to a value indicative of a degree to which errors will tolerated in a search; and

each cell further includes means for reducing the numeric value of a mark in the event that no match is found in the cell, whereby nonzero marks still remaining after the search represent pattern matches to within the desired degree of tolerance.

37. Apparatus as defined in claim 36, wherein:

each cell further includes means for assigning different costs to different types of matching errors and to different errors of the same type.

38. Apparatus as defined in claim 37, wherein:

the types of errors that may be detected include misspellings, missing characters and extra characters.

39. A generalized method for searching databases, the method comprising the steps of:

inputting a first data stream into a pipeline of search cells, each having a plurality of registers, with corresponding registers of each cell being serially connected to form the pipeline, wherein the first data stream contains a sequence of database characters and parallel sequences of other data associated with the database, one of the parallel sequences being a sequence of character marks;

inputting a second data stream into the pipeline of search cells, although not necessarily after input of the first data stream, wherein the second data stream contains a sequence of pattern characters and parallel sequences of other data, including coded data to control operation of the cells, and wherein one of the first and second data streams is shifted into the pipeline prior to a search and the other of the data streams is streamed through the pipeline in performance of the search;

setting all of the character marks to a nonzero value, to mark all of the characters in the database character sequence and to indicate initially that every character is a candidate for the beginning of a search;

comparing each marked database character with a first pattern character;

unmarking all characters that do not match the first pattern character;

shifting any remaining marks toward the end of the sequence of database characters;

comparing each marked database character with subsequent pattern characters in turn; and

after each comparison, unmarking any nonmatching database characters and shifting any remaining marks toward the end of the sequence of database characters;

whereby any string of characters in the database that matches the pattern will be marked at the character position next following the last character in the matching string.

40. A method as defined in claim 39, wherein:

the second data stream, containing the pattern characters and associated data, is shifted into the search cells prior to the search;

the first data stream, containing the database characters and associated data, is streamed through the search cells during the search; and

the search is of the retrospective type, to locate at least one relatively small pattern in a large database.

41. A method as defined in claim 39, wherein:

the first data stream, containing the database characters and associated data, is shifted into the search cells prior to the search;

the second data stream, containing the pattern characters and associated data, is streamed through the search cells during the search;

the search is of the dissemination type, to locate a relatively large pattern or a number of patterns in a relatively small database.

42. A method as defined in claim 39, wherein the method performs a reverse sequence search for a string of pattern characters appearing in reverse order, the method further comprising the steps of:

first shifting any character marks toward the beginning of the sequence of database characters;

then comparing each marked database character with a first of the pattern characters stored in reverse order;

unmarking all characters that do not match the first reverse-order pattern character;

comparing each marked database character with subsequent pattern reverse-order characters in turn and, before each comparing step, shifting any remaining marks toward the beginning of the sequence of database characters; and

after each comparison, unmarking any nonmatching database characters;

whereby any string of characters in the database that matches the reverse-order pattern will be marked at the character position corresponding to the first character in the matching string, which is the last to be compared in the reverse-order pattern.

43. A method as defined in claim 39, wherein the comparing steps include comparing for equality between the compared characters.

44. A method as defined in claim 39, wherein the comparing steps include detecting a selected relationship of inequality between the compared characters.

45. A method as defined in claim 39, and further comprising the steps of:

searching the sequence of database characters for occurrences of at least one selected character that is to be ignored in a search;

tagging each occurrence of the selected character by setting the value of a corresponding item in one of the parallel data sequences associated with the database; and

ignoring the tagged characters in the search for database characters that match the pattern characters.

46. A method as defined in claim 39, and further comprising the steps of:

searching the sequence of database characters for occurrences of at least a selected character that is to the site of a "kill" boundary;

tagging each occurrence of the selected character by setting the value of a corresponding item in one of the parallel data sequences associated with the database; and

during performance of a search, extinguishing a mark when the steps of the search call for shifting the mark across a "kill" boundary.

47. A method as defined in claim 39, wherein:

each character mark has a positive numerical value;

the step of extinguishing a mark is effected by reducing the value of the numerical mark; and

the method further comprises the steps of setting the marks to a selected initial value indicative of a desired degree of error tolerance for the search, and reducing the numerical value of a mark when a nonmatching condition is detected, whereby the numerical values of any marks remaining at the end of the search are indicative of the degree of match for each string of characters located in the sequence of database characters.

48. A method as defined in claim 47, and further comprising the steps of:

selecting a cost for each type of error, wherein different costs may be selected for different types of errors.