Method of a data range search with plural pre-set rules

• US 6,961,725 B2
• Filed: 08/24/2002
• Issued: 11/01/2005
• Est. Priority Date: 05/16/2002
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chen, Wen-Jyh, Yuan, Kuo-Hua
• Primary Examiner(s): Rones, Charles
• Application Number:
  US10/228,232
• Publication Number:
  US 20030217046A1
• Time in Patent Office: 1,165 Days
• Field of Search: 707/3, 707/4, 707/101, 707/203
• US Class Current: 707/694
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A search method for a range search with a plurality of pre-set rules constructs a rule mapping table by dividing data associated with the rules into a plurality of sub-keys and generating output tables for each sub-key. A rule column is formed for a rule by following through each sub-key based on the associated range of data. A first output table for the first sub-key and upper and lower output tables are generated for each remaining sub-key. All the rule columns are arranged in parallel to form the rule mapping table. The method of search is accomplished by dividing an input data into a plurality of sub-keys and each sub-key is used to search through the rule mapping table for determining a rule that is satisfied with the input data. If multiple rules are satisfied, a priority encoder selects a highest priority rule as the search result.

Claims

1. A search method implemented with a computer for finding a rule from a plurality of rules each having an associated range of data, said data having n bits and said method comprising the steps of:

(a) dividing said n bits into a plurality of sub-keys each having at least one bit, and constructing a rule mapping table having a rule column for each rule of said plurality of rules, each rule column being formed by generating a first output table for a first sub-key, and an upper output table and a lower output table for each remaining sub-key according to the associated range of data of a corresponding rule; and

(b) dividing an input data into a plurality of input sub-keys for searching through said rule mapping table and determining rules that are satisfied with said input data, the first output table and upper and lower output tables in each rule column being addressed by said plurality of input sub-keys to determine if said input data satisfies a corresponding rule.

2. The search method as claimed in claim 1, wherein said step (b) further determines a highest priority rule as a search result if more than one rule are determined to be satisfied with said input data.

3. The search method as claimed in claim 1, wherein in step (a) a first output table of a first sub-key of a rule column has an entry for each possible value of the first sub-key and the value of each entry is 00, 01, 10 or 11 to represent no match, exact match, further search in an upper output table of a second sub-key or further search in a lower output table of a second sub-key;

an upper output table of a k^th sub-key of a rule column has an entry for each possible value of the k^th sub-key and the value of each entry is 00, 01 or 10 to represent no match, exact match and further search in an upper output table of a next sub-key; and

a lower output table of a k^th sub-key of a rule column has an entry for each possible value of the k^th sub-key and the value of each entry is 00, 01 or 11 to represent no match, exact match and further search in a lower output table of a next sub-key.

4. A search method implemented with a computer for finding a rule from a plurality of rules each having an associated range of data, said data having n bits and said method comprising the steps of:

(a) dividing said n bits into a plurality of sub-keys each having at least one bit, and constructing a rule mapping table having a rule column for each rule of said plurality of rules, each rule column being formed by generating a first output table for a first sub-key, and an upper output table and a lower output table for each remaining sub-key according to the associated range of data of a corresponding rule; and

(b) dividing an input data into a plurality of input sub-keys for searching through said rule mapping table and determining rules that are satisfied with said input data, the first output table and upper and lower output tables in each rule column being addressed by said plurality of input sub-keys to determine if said input data satisfies a corresponding rule;

wherein in step (a) a rule column for a given rule is generated according to the steps of;

(a1) determining a start value and an end value from the range of data associated with said given rule and representing said start and end values as Start and End respectively;

(a2) filling each entry in a first output table of a first sub-key according to a first sub-key rule based on a smallest possible first key data Key_1_min, a largest possible first key data Key_1_max, Start and End;

(a3) filling each entry in an upper output table of a k^th sub-key according to a k^th sub-key upper table rule based on a smallest possible k^th sub-key data Key_k_min, a largest possible k^th sub-key data Key_k_max, Start and End;

(a4) filling each entry in a lower output table of a k^th sub-key according to a k^th sub-key lower table rule based on a smallest possible k^th sub-key data Key_k_min, a largest possible k^th sub-key data Key_k_max, Start and End;

(a5) repeating step (a3) and (a4) for all remaining sub-keys; and

(a6) arranging all output tables generated in steps (a2), (a3) and (a4) from top to bottom in the order of a first output table of a first sub-key, an upper output table of a second sub-key, a lower output table of a second sub-key, an upper output table of a third sub-key, a lower output table of a third sub-key, and so forth for all sub-keys to form a rule column for the given rule.

5. The search method as claimed in claim 4, wherein a first sub-key has a binary representation x₁¹x₂¹x₃¹ . . . x_m1¹, a smallest possible first key data Key_1_min is x₁¹x₂¹x₃¹ . . . x_m1¹00 . . . 0 which has n−

m₁ trailing 0, a largest possible first key data Key_1_max is x₁¹x₂¹x₃¹ . . . x_m1¹11 . . . 1 which has n−

m₁ trailing 1, and the first sub-key rule in said step (a2) comprises;

(i) filling all entries corresponding to x₁¹x₂¹x₃¹ . . . x_m1¹ with 00 representing no match if Key_1_max<

Start;

(ii) filling all entries corresponding to x₁¹x₂¹x₃¹ . . . x_m1¹ with 10 representing further search in an upper output table if Key_k_min<

Start and Start≦

Key_k_max≦

End;

(iii) filling all entries corresponding to x₁¹x₂¹x₃¹ . . . x_m1¹ with 01 representing exact match if Start≦

Key_1_min and Key_1_max≦

End;

(iv) filling all entries corresponding to x₁¹x₂¹x₃¹ . . . x_m1¹ with 11 representing further search in a lower output table if Start≦

Key_1_min≦

End and End<

Key_1_max; and

(v) filling all entries corresponding to x₁¹x₂¹x₃¹ . . . x_m1¹ with 00 representing no match if End<

Key_1_min.

6. The search method as claimed in claim 5, wherein a second sub-key is x₁²x₂²x₃² . . . x_m2², a third sub-key is x₁³x₂³x₃³ . . . x_m3³, . . . , a k^th−

1 sub-key is x₁<sup>k−

1</sup>x₂<sup>k−

1</sup>x₃<sup>k−

1</sup> . . . x<sub>m(k−

1)</sub><sup>k−

1</sup>, a k^th sub-key is x₁^kx₂^kx₃^k . . . x_mk^k respectively in binary representation in which n=m₁+m₂+m₃+ . . . +m_k, a smallest possible k^th sub-key data Key_k_min is x₁¹x₂¹x₃¹ . . . x_m1¹x₁²x₂²x₃² . . . x_m2² . . . x₁<sup>k−

1</sup>x₂<sup>k−

1</sup>x₃<sup>k−

1</sup> . . . x<sub>m(k−

1)</sub><sup>k−

1</sup>x₁^kx₂^kx₃^k . . . x_mk^k00 . . . 0 which has n−

(m₁+m₂+ . . . +m_k) trailing 0, a largest possible k^th sub-key data Key_k_max is x₁¹x₂¹x₃¹ . . . x_m1¹x₁²x₂²x₃² . . . x_m2² . . . x₁<sup>k−

1</sup>x₂<sup>k−

1</sup>x₃<sup>k−

1</sup> . . . x<sub>m(k−

1)</sub><sup>k−

1</sup>x₁^kx₂^kx₃^k . . . x_mk^k11 . . . 1 which has n−

(m₁+m₂+ . . . +m_k) trailing 1, and the k^th sub-key upper table rule in said step (a3) comprises;

(i) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 00 representing no match if Key_k_max<

Start;

(ii) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 10 representing search in an upper output table if Key_k_min<

Start and Start≦

Key_k_max≦

End; and

(iii) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 01 representing exact match if Start≦

Key_1_min and Key_1_max≦

End.

7. The search method as claimed in claim 6, wherein the k^th sub-key lower table rule in said step (a4) comprises:

(i) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 01 representing exact match iff Start≦

Key_k_min and Key_k_max<

=End;

(ii) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 11 representing further search in a lower output table if Start≦

Key_k_min≦

End and End<

Key_k_max; and

(iii) filling all entries corresponding to x₁^kx₂^kx₃^k . . . x_mk^k with 00 representing no match if End<

Key_k_min.

8. A search method implemented with a computer for finding a rule from a plurality of rules each having an associated range of data, said data having n bits and said method comprising the steps of:

(a) dividing said n bits into a plurality of sub-keys each having at least one bit, and constructing a rule mapping table having a rule column for each rule of said plurality of rules, each rule column being formed by generating a first output table for a first sub-key, and an upper output table and a lower output table for each remaining sub-key according to the associated range of data of a corresponding rule; and

(b) dividing an input data into a plurality of input sub-keys for searching through said rule mapping table and determining rules that are satisfied with said input data, the first output table and upper and lower output tables in each rule column being addressed by said plurality of input sub-keys to determine if said input data satisfies a corresponding rule;

wherein said step (b) comprises the steps of;

(b1) reading and dividing an n-bit input data into K sub-keys having m₁, m₂, m₃, . . . , m_K bits respectively from high order bit to low order bit, wherein n, m₁, m₂, m₃, . . . , m_K are positive numbers;

(b2) using a first sub-key as an address for searching in the first output table of a first level of each rule to output a search result;

(b3) using a k^th sub-key as an address for searching in the upper and lower output tables of a k^th level in each rule to output search results, wherein k=2; and

(b4) repeating step (b3) for k=3, 4, . . . , K;

wherein the search results of steps (b2), (b3) and (b4) are used to determine if said input data satisfies each rule being searched.

9. The search method as claimed in claim 8, wherein each search result in said steps (b2), (b3) and (b4) is exact match, no match, further search in an upper output table, or further search in a lower output table, said search method stops searching if a search result is exact match or no match, and a next level search continues if a search result is neither exact match nor no match.

10. The search method as claimed in claim 9, wherein in said step (b3) or (b4), the search result of the lower output table at a current level is ignored if the search result of a previous level is further search in an upper output table;

and the search result of the upper output table at a current level is ignored if the search result of a previous level is further search in a lower output table.

11. The search method as claimed in claim 8, wherein each search result in said steps (b2), (b3) and (b4) is sent sequentially to a post-stage circuit associated to a rule being searched.

12. The search method as claimed in claim 11, wherein said steps (b2), (b3) and (b4) are performed for each rule in parallel, and each post-stage circuit sends an output to a priority encoder which selects a highest priority rule that is satisfied with said input data.

13. The search method as claimed in claim 11, wherein each search result in said steps (b2), (b3) and (b4) is encoded as 00, 01, 10 or 11, said post stage circuit has an initial state, a lookup state, an ignore state and a final state, and said post stage circuit implements a logic comprising:

(i) transitioning to a final state if 00 or 01 is received by said post stage circuit in an initial state and outputting 0 or 1 respectively;

(ii) transitioning to a lookup state if 10 is received by said post stage circuit in an initial state;

(iii) transitioning to an ignore state if 11 is received by said post stage circuit in an initial state;

(iv) transitioning to a final state if 00 or 01 is received by said post stage circuit in a lookup state and outputting 0 or 1 respectively;

(v) transitioning to an ignore state if 10 or 11 is received by said post stage circuit in a lookup state;

(vi) transitioning to a final state and keeping a previous output regardless of what is received if said post stage circuit is in a final state; and

(vii) transitioning to a lookup state regardless of what is received if said post stage circuit is in an ignore state.