Prefix search method and data structure using compressed search tables

• US 6,782,382 B2
• Filed: 03/07/2001
• Issued: 08/24/2004
• Est. Priority Date: 05/29/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lunteren, Jan Van
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US09/801,026
• Publication Number:
  US 20020002549A1
• Time in Patent Office: 1,266 Days
• Field of Search: 707/3, 707/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The invention relates to a system in which given search keys are evaluated, segment by segment, to search through tree-structured tables for finding an output information corresponding to the longest matching prefix. For at least one of the segments, only selected bits of the search key segment are used as index for accessing an associated table where test values are stored which are to be compared to the respective search key segment. The bits to be selected are determined by an index mask, reflecting the distribution of the valid test values in the table entries (and valid search key segment values). This allows table compression for minimizing storage requirements and search time. A procedure is disclosed for generating an optimum index mask in response to the set of valid test values.

Claims

1. Method for determining an output information in response to an input search key, by a stepwise prefix search in a tree structured data base comprising stored tables, and by evaluating successive segments of the search key each of given length, comprising the steps of:

a) in at least one step for evaluating a search key segment, selected bits of the segment are used as compressed index for accessing a table of stored test values associated with that segment and

b) the test value accessed by the compressed index is compared to at least the remaining portion of the search key segment evaluated, and the comparison result determines the further processing or the result of the search procedure; and

c) generating pair-wise XOR products from all valid index values which can occur in the respective search key segment, and which correspond to the test values stored in the indexed table and from which bits are to be selected;

d) preparing sequentially tentative index masks each containing a total number of bits equal to the number of bits in the search key segment from which bits are to be selected, starting with a single 1-bit in each tentative index mask and proceeding to increasing numbers of 1-bits in the tentative index masks;

e) generating successively, for each of the tentative index masks prepared, the bitwise AND product between the respective tentative index mask and all of the XOR products previously generated in step (c); and

f) ending the procedure when each of the AND products generated for a tentative index mask contains at least one 1-bit, and storing the respective tentative index mask as optimum index mask for the respective search key segment.

2. Method according to claim 1, comprising the following additional substep during step (c) when generating pair-wise XOR products for all valid index values which can occur in the respective search key segment, each containing k bits:

providing an XOR product bit vector comprising 2^k bit positions each assigned to one of the possible XOR products, and setting after generation of a particular XOR product the respective bit position in the XOR bit vector to 1, so that not all generated XOR products need to be stored until generation of the AND products in step (e).

3. Method according to claim 1, for updating the search data structure when a new valid test value and corresponding index value has to be inserted, comprising the step of newly calculating each index mask involved, on the basis of all valid index values, including the new one.