Method and apparatus for ternary PATRICIA trie blocks

• US 7,299,235 B2
• Filed: 07/26/2004
• Issued: 11/20/2007
• Est. Priority Date: 07/28/2003
• Status: Expired due to Fees

• Current Assignee: RightOrder, Inc.
• Original Assignee: RightOrder, Inc.
• Inventors: Sample, Neal
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US10/899,657
• Publication Number:
  US 20050027679A1
• Time in Patent Office: 1,212 Days
• Field of Search: 707/3, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An architecture and method for efficient termination of variable length keys in a PATRICIA trie is disclosed. By adding a null-labeled link, it is possible to terminate such variable length PATRICIA trie nodes, allowing to overcome the need for complex termination solutions. Specifically, a ternary PATRICIA block is introduced.

Claims

1. A computer implemented method for creating a labeled PATRICIA trie block, the computer implemented method comprising the steps of:

selecting a size of said labeled PATRICIA trie block;

defining a size of a header of said labeled PATRICIA trie block;

determining a number of nodes of a PATRICIA trie;

determining a number of pointers of said nodes;

determining a number of bits for an offset value of said labeled PATRICIA block;

determining a number of bits of a left sub-tree of the PATRICIA trie;

using a bit aligned representation to allow an increase in the number of pointers;

determining a number of bits for a status indicator of said labeled PATRICIA trie block, wherein the labeled PATRICIA trie block is maximum the number of pointers, the number of pointers determines a fanout in said PATRICIA trie block;

creating the labeled PATRICIA trie block based on said determining a number of bits for a status indicator and the determining of said fanout;

the determining of said fanout comprises the steps of;

selecting a number of bits devoted to storing a number of nodes for a first practice value;

selecting a number of bits devoted to a number of left leaves for a second practical value;

selecting a number of bits devoted to said offset value for a third practice value;

selecting a number of bits devoted to said number of pointers for a fourth practical value;

said second practical value and said third practical value are substantially equal; and

selected values for said second practical value and said third practical value adhere to an inequality, where said third practice value plus logarithm sub two of sum of said second practical value, said third practical value and said fourth practical value is equal to or larger than logarithm sub two of block size, header size and said first practical value.

2. The computer implemented method of claim 1, wherein a total number of bits for said second practical value and said third practical value are aligned on at least half a byte.

3. A computer implemented method for creating a labeled PATRICIA trie block, the computer implemented method comprising the steps of:

selecting a size of said labeled PATRICIA trie block;

defining a size of a header of said labeled PATRICIA trie block;

determining a number of nodes of a PATRICIA trie;

determining a number of pointers of said nodes;

determining a number of bits for an offset value of said labeled PATRICIA trie block;

using a bit aligned representation to allow an increase in the number of pointers;

determining a number of bits of a left sub-tree of the PATRICIA trie;

determining a number of bits for a status indicator of said labeled PATRICIA trie block;

wherein the labeled PATRICIA trie block is maximum the number of pointers, the number of pointers determines a fanout in said PATRICIA trie block;

wherein the status indicator comprises an indication of labels respective of each node of said PATRICIA trie block;

wherein said indication of null-labels comprise any of all labels present, no null-label, no left label, and no right label;

creating the labeled PATRICIA trie block based on said determining a number of bits for a status indicator and the determining of said fanout;

the determining of said fanout comprises the steps of;

selecting a number of bits devoted to storing a number of nodes for a first practice value;

selecting a number of bits devoted to a number of left leaves for a second practical value;

selecting a number of bits devoted to said offset value for a third practice value;

selecting a number of bits devoted to said number of pointers for a fourth practical value;

said second practical value and said third practical value are substantially equal; and

selected values for said second practical value and said third practical value adhere to an inequality, wherein said third practice value plus logarithm sub two of sum of said second practical value, said third practical value and said fourth practical value is equal to or larger than logarithm sub two of block size, header size and said first practical value.

4. The computer implemented method of claim 3, wherein a total number of bits for said second practical value and said third practical value are aligned on at least half a byte.

5. A computer memory, said computer memory containing computer program instructions for operating a computer to create a labeled PATRICIA trie block, said computer program instructions executing a computer implemented method comprising the steps of:

selecting a size of said labeled PATRICIA trie block;

defining a size of a header of said labeled PATRICIA trie block;

determining a number of nodes of a PATRICIA trie;

determining a number of pointers of said nodes;

determining a number of bits for an offset value of said labeled PATRICIA trie block;

using a bit aligned representation to allow an increase in the number of pointers;

determining a number of bits of a left sub-tree of the PATRICIA trie;

determining a number of bits for a status indicator of said labeled PATRICIA trie block;

wherein the labeled PATRICIA trie block is maximum the number of pointers, the number of pointers determines a fanout in said PATRICIA trie block;

wherein the status indicator comprises an indication of labels respective of each node of said PATRICIA trie block;

wherein said indication of null-labels comprise any of all labels present, no null-label, no left label, and no right label;

creating the labeled PATRICIA trie block based on said determining a number of bits for a status indicator and the determining of said fanout;

the determining of said fanout comprises the steps of;

selecting a number of bits devoted to storing a number of nodes for a first practice value;

selecting a number of bits devoted to a number of left leaves for a second practical value;

selecting a number of bits devoted to said offset value for a third practice value;

selecting a number of bits devoted to said number of pointers for a fourth practical value;

said second practical value and said third practical value are substantially equal; and

selected values for said second practical value and said third practical value adhere to an inequality, wherein said third practice value plus logarithm sub two of sum of said second practical value, said third practical value and said fourth practical value is equal to or larger than logarithm sub two of block size, header size and said first practical value.

6. The computer memory of claim 5, wherein a total number of bits corresponding to said third practical value, said fourth practical value, and said fifth practical value are aligned on at least half a byte.

7. A computer memory, said computer memory containing computer program instructions for operating a computer to create a labeled PATRICIA trie block, said computer program instructions executing a computer implemented method comprising the steps of:

selecting a size of said labeled PATRICIA trie block;

defining a size of a header of said labeled PATRICIA trie block;

determining a number of nodes of a PATRICIA trie;

determining a number of pointers of said nodes;

determining a number of bits for an offset value of said labeled PATRICIA trie block;

using a bit aligned representation to allow an increase in the number of pointers;

determining a number of bits of a left sub-tree of the PATRICIA trie;

determining a number of bits for a status indicator of said labeled PATRICIA trie block;

wherein the labeled PATRICIA trie block is maximum the number of pointers, the number of pointers determines a fanout in said PATRICIA trie block;

creating the labeled PATRICIA trie block based on said determining a number of bits for a status indicator and the determining of said fanout;

the determining of said fanout comprises the steps of;

selecting a number of bits devoted to storing a number of nodes for a first practice value;

selecting a number of bits devoted to a number of left leaves for a second practical value;

selecting a number of bits devoted to said offset value for a third practice value;

selecting a number of bits devoted to said number of pointers for a fourth practical value;

said second practical value and said third practical value are substantially equal; and

selected values for said second practical value and said third practical value adhere to an inequality, wherein said third practice value plus logarithm sub two of sum of said second practical value, said third practical value and said fourth practical value is equal to or larger than logarithm sub two of block size, header size and said first practical value.

8. The computer memory of claim 7, wherein a total number of bits for said second practical value and said third practical value are aligned on at least half a byte.