Method and apparatus for ternary patricia trie blocks

• US 20050027679A1
• Filed: 07/26/2004
• Published: 02/03/2005
• Est. Priority Date: 07/28/2003
• Status: Active Grant

• Current Assignee: RightOrder, Inc.
• Original Assignee: RightOrder, Inc.
• Inventors: Sample, Neal
• Granted Patent: US 7,299,235 B2
• Time in Patent Office: Days
• 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. An architecture for a labeled PATRICIA trie block, the block architecture comprising:

a header portion;

a number-of-nodes portion;

a plurality of pointers portion;

a plurality of offset and left sub-tree portions; and

a plurality of status indicator portions.

2. The architecture of claim 1, wherein said status indicator portion comprises an indication of null-labels respective of each node of said PATRICIA trie.

3. The architecture of claim 2, wherein said node comprises any of two and three sub-trees.

4. The architecture of claim 2, wherein said indication of null-labels comprises any of all labels present, no null-label, no left label, and no right label.

5. The architecture of claim 4, wherein said indication of null-labels comprises at least two bits.

6. The architecture of claim 1, wherein said labeled PATRICIA trie block comprises a ternary implementation of a PATRICIA trie block.

7. The architecture of claim 5, wherein sub-trees having said null-labels are added to a node to handle keys that do not have unique end-of-key tokens.

8. The architecture of claim 5, wherein said keys comprise variable-length binary keys.

9. The architecture of claim 1, wherein said labeled PATRICIA trie block indexes infinite strings.

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

selecting a block size;

defining the size of a header of said block;

determining a number-of-nodes;

determining a number of pointers;

determining a number of bits for an offset value;

determining a number of bits for a left sub-tree; and

determining a number of bits for a status indicator.

11. The method of claim 10, wherein said status indicator comprises an indication of labels respective of each node of said PATRICIA trie block.

12. The method of claim 11, wherein said node comprises any of two and three sub-trees.

13. The method of claim 11, wherein said indication of null-labels comprises any of all labels present, no null-label, no left label, and no right label.

14. The method of claim 13, wherein said indication of null-labels comprises at least two bits.

15. The method of claim 10, wherein sub-trees having said null-labels are added to a node to handle keys that do not have unique end-of-key tokens.

16. The method of claim 15, wherein said keys comprises variable-length binary keys.

17. The method of claim 10, wherein said labeled PATRICIA trie block indexes infinite strings.

18. The method of claim 10, wherein said labeled PATRICIA trie block comprises a ternary implementation of a PATRICIA trie block.

19. The method of claim 10, wherein labeled PATRICIA trie block is maximizes the said number of pointers.

20. The method of claim 19, wherein said number of pointers determines a fanout in said PATRICIA trie block.

21. The method of claim 20, wherein said step of determining said fanout comprises the steps of:

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

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

selecting a number of bits devoted to said offset value to a third practical value; and

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

22. The method of claim 21, wherein said first practical value is byte aligned.

23. The method of claim 22, wherein said first practical value is equal to or larger than said third practical value.

24. The method of claim 21, wherein said second practical value and said third practical value are substantially equal.

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

26. The method of claim 25, wherein the total number of bits for said second practical value and said third practical value are aligned on at least half a byte.

27. The method of claim 21, wherein said fourth practical value is aligned on at least half a byte.

28. The method of claim 27, wherein said fourth practical value comprises twenty bits.

29. The method of claim 21, further comprising the step of calculating a fanout.

30. The method of claim 29, wherein said step of calculating the fanout comprises the steps of:

subtracting from the size of said block the size of a header value and the said first practical value; and

dividing a result of said subtracting step by the sum of said second practical value, said third practical value, and said fourth practical value.

31. The method of claim 14, wherein said method further comprising the step of:

selecting a number of bits devoted to said status indicator to a fifth practical value.

32. The method of claim 31, wherein said selected values for said second practical value and said third practical value adhere to an inequality where said third practical value plus the logarithm sub two of the sum of said second practical value, said third practical value, said fourth practical value, and said fifth practical value is equal to or larger than the logarithm sub two of the block size, the header size, and said first practical value.

33. The method of claim 32, 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.

34. A computer software product, said computer product containing program instructions for creating a labeled PATRICIA trie block, said program instructions comprising the steps of:

selecting a block size;

defining the size of a header of said block;

determining a number-of-nodes;

determining a number of pointers;

determining a number of bits for an offset value;

determining a number of bits for a left sub-tree; and

determining a number of bits for a status indicator.

35. The computer software product of claim 34, wherein said status indicator comprises an indication of labels respective of each node of said PATRICIA trie block.

36. The computer software product of claim 35, wherein said node comprises any of two and three sub-trees.

37. The computer software product of claim 35, wherein said indication of null-labels comprises any of all labels present, no null-label, no left label, and no right label.

38. The computer software product of claim 37, wherein said indication of null-labels comprise at least two bits.

39. The computer software product of claim 34, wherein sub-trees having said null-labels are added to a node for handling keys that do not have unique end-of-key tokens.

40. The computer software product of claim 34, wherein said keys comprise variable-length binary keys.

41. The computer software product of claim 34, wherein said labeled PATRICIA trie block indexes infinite strings.

42. The computer software product of claim 34, wherein said labeled PATRICIA trie block comprises a ternary implementation of a PATRICIA trie block.

43. The computer software product of claim 34, wherein labeled PATRICIA trie block maximizes said number of index pointers.

44. The computer software product of claim 43, wherein said number of index pointers determines a fanout in said PATRICIA trie block.

45. The computer software product of claim 44, wherein said step of determining said fanout comprises the steps of:

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

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

selecting a number of bits devoted to said offset value to a third practical value; and

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

46. The computer software product of claim 45, wherein said first practical value is byte aligned.

47. The computer software product of claim 46, wherein said first practical value is equal to or larger than said third practical value.

48. The computer software product of claim 45, wherein said second practical value and said third practical value are substantially equal.

49. The computer software product of claim 48, wherein the selected values for said second practical value and said third practical value adhere to an inequality where said third practical value plus the logarithm sub two of the sum of said second practical value, said third practical value and said fourth practical value is equal to or larger than the logarithm sub two of the block size, the header size and said first practical value.

50. The computer software product of claim 49, wherein the total number of bits for said second practical value and said third practical value are aligned on at least half a byte.

51. The computer software product of claim 45, wherein said fourth practical value is aligned on at least half a byte.

52. The computer software product of claim 51, wherein said fourth practical value comprises twenty bits.

53. The computer software product of claim 45, further comprising the step of calculating a fanout.

54. The computer software product of claim 53, wherein said step of calculating the fanout comprises the steps of:

subtracting from the size of said block the size of a header value and said first practical value; and

dividing a result of said subtracting previous step by the sum of said second practical value, said third practical value, and said fourth practical value.

55. The computer software product of claim 38, wherein said method further comprises the step of:

selecting a number of bits devoted to said status indicator to a fifth practical value.

56. The computer software product of claim 55, wherein the selected values for said second practical value and said third practical value adhere to an inequality, where said third practical value plus the logarithm sub two of the sum of said second practical value, said third practical value, said fourth practical value and said fifth practical value is equal to or larger than the logarithm sub two of the block size, the header size, and said first practical value.

57. The computer software product of claim 56, 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.

58. A memory structure for storing a PATRICIA trie block that supports variable length key termination, said structure comprising:

a header;

a number-of-nodes;

a plurality of pointers;

a plurality of offset and left sub-tree; and

a plurality of status indicator.

59. The structure of claim 58, wherein said status indicators comprises an indication of null-labels respective of each node of said PATRICIA trie block.

60. The structure of claim 58, wherein said node comprises any of two and three sub-trees.

61. The structure of claim 59, wherein said indication of null-labels comprises any of all labels present, no null-label, no left label, and no right label.

62. The structure of claim 61, wherein said indication of null-labels comprises two bits.

63. The structure of claim 58, further comprises:

variable length key that comprises a binary key.

64. The structure of claim 58, further comprising:

a ternary implementation of a PATRICIA trie block.

65. A PATRICIA trie block that supports variable length key termination, said PATRICIA trie block placed in memory and comprising:

a header placed;

a number-of-nodes;

a plurality of pointers;

a plurality of offset and left sub-tree; and

a plurality of status indicator.

66. The apparatus of claim 65, wherein said status indicator an indication of null-labels respective of each node of said PATRICIA trie block.

67. The apparatus of claim 66, said node comprising any of two and three sub-trees.

68. The apparatus of claim 67, wherein said indication of null-labels comprises any of all labels present, no null-label, no left label, any no right label.

69. The apparatus of claim 68, wherein said indication of null-labels comprises two bits.

70. The apparatus of claim 65, further comprises using a variable length key that comprises a binary key.

71. The apparatus of claim 65, further comprises a ternary implementation of a PATRICIA trie block.

72. A ternary PATRICIA trie block comprising:

a plurality of nodes, wherein each of said nodes is capable of handling at least two sub-trees.

73. The ternary PATRICIA trie block of claim 72, wherein said nodes of said PATRICIA trie block further comprise a null-label status indication.

74. The ternary PATRICIA trie block of claim 73, wherein said status indication of said null-labels comprises any of all labels present, no null-label, no left label, and no right label.

75. A cascading index for referencing at least two or more PATRICIA trie blocks, comprising:

a PATRICIA trie block containing said cascading index, and

each node of said PATRICIA trie blocks having at least two sub-trees.