Method and/or system for transforming between trees and arrays

• US 8,356,040 B2
• Filed: 03/20/2006
• Issued: 01/15/2013
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Letourneau, Jack J.
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): McCue, Brittany N
• Application Number:
  US11/385,257
• Publication Number:
  US 20060271573A1
• Time in Patent Office: 2,493 Days
• Field of Search: 707/101, 707/756, 707/796, 707/797
• US Class Current: 707/756
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments of articles, apparatuses, devices and/or systems for manipulating hierarchical sets of data are disclosed. In particular embodiments, the hierarchical information may be expressed as trees. Such hierarchical information expressed as a tree may be transformed to an array. Likewise, hierarchical information expressed in an array may be expanded as a tree.

Claims

1. A method comprising:

transforming between one or more electrical digital signals representing a tree and one or more electrical digital signals representing a condensed array of numerals by;

(a) identifying a label value associated with a node of said tree;

(b) factoring said label value into two or more non-composite factors;

(c) associating said non-composite factors with indices of said condensed array of numerals, wherein said condensed array comprises a fixed number of rows or a fixed number of columns;

(d) determining numerals representing one or more descendent nodes directly connected to said node based, at least in part, on said indices; and

(e) recursively applying (a) through (d) to said descendent nodes to determine numerals representing remaining nodes descendent from said node, wherein each frontier node of said tree is associated with a label value comprising a non-composite numeral times an integer number of terminal nodes descending from said frontier node.

2. The method of claim 1, wherein at least some of said numerals of said condensed array are based, at least in part, upon an association of trees and numerals.

3. The method of claim 1, the method further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

associating numerical label values with at least some nodes or edges in said tree; and

associating label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerals derived, at least in part, from label values associated with said child nodes.

4. The method of claim 3, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

pruning said child nodes.

5. The method of claim 3, wherein a numerical label value associated with at least one of said parent nodes is based, at least in part, on a combination of non-composite numerals derived, at least in part, from label values associated with said child nodes.

6. The method of claim 3, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

determining said non-composite numerals from an array of non-composite numerals indexed by sequential indices.

7. The method of claim 1, and further transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

representing a parent node as a product of factors associated with one or more subtrees of said parent node.

8. The method of claim 7, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

representing at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

determining at least one of said factors associated with said at least one subtree as at least one non-composite numeral associated with an index in an array of non-composite numerals if a predetermined function of said at least one factor matches an index among indices of said array of non-composite numerals.

9. The method of claim 7, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

representing at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

associating said numeral in said condensed array with a substitute numeral if a predetermined function of said at least one factor does not match an index among indices of an array of non-composite numerals.

10. The method of claim 9, wherein said substitute numeral comprises a multiple of a predetermined numeral and said predetermined function comprises multiplication of said numeral representing said sub tree by said predetermined numeral.

11. The method of claim 9, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by determining a factor of said product associated with said subtree based, at least in part, on said substitute numeral.

12. The method of claim 11, wherein said determining a factor of said product associated with said subtree further comprises determining said factor based, at least in part, on a natural numeral associated with an index of said array of non-composite numerals, said index corresponding with a function of said substitute numeral.

13. The method of claim 1, wherein said determining numerals associated with one or more descendant nodes further comprises associating a function of said indices with one or more numerals in said array of non-composite numerals.

14. The method of claim 1, wherein said tree comprises a BLT.

15. The method of claim 14, wherein said method further comprises transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by transforming between one or more electrical digital signals representing said BLT and one or more electrical digital signals representing a unary tree.

16. The method of claim 14, wherein said method further comprises transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

associating one or more frontier nodes of said tree with one or more ordered pairs; and

associating said one or more ordered pairs with one or more single numerals according to a Cantor pairing function.

17. The method of claim 16, and further comprising transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by associating said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

18. The method of claim 1, wherein said tree comprises an m-ary labeled tree, and wherein said method further comprises transforming between said one or more signals representing said tree and one or more electrical digital signals representing said condensed array of numerals by:

associating one or more frontier nodes of said tree with one or more m-dimensional expressions;

associating said one or more m-dimensional expressions with one or more single numerals according to a Cantor function; and

associating said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

19. The method of claim 1, wherein said condensed array comprises a fixed size in at least one dimension.

20. The method of claim 19, wherein said condensed array comprises a plurality of entries associating substitute numerals with substituted numerals.

21. The method of claim 20, wherein said substituted numerals comprise numerals associated with subtrees according to an association of trees and numerals.

22. The method of claim 20, wherein said substitute numerals comprise one or more integer multiples of a predetermined non-composite numeral, said integer multiples representing one or more frontier nodes of said tree.

23. The method of claim 20, wherein said substitute numerals comprise multiples of a predetermined integer, said multiples being associated with larger substituted numerals representative of subtrees.

24. An apparatus comprising:

means, comprising a processor programmed with instructions, for representing at least a condensed array of numerals; and

means, comprising said instructions, for transforming between a tree and condensed array of numerals, said means for transforming between said tree and said condensed array of numerals comprising;

(a) means for identifying a label value associated with a node of said tree

(b) means for factoring said label value into two or more non-composite factors;

(c) means for associating said non-composite factors with indices of said condensed array of numerals, wherein said condensed array comprises a fixed number of rows or a fixed number of columns;

(d) means for determining numerals representing one or more descendent nodes connected to said node based, at least in part, on said indices; and

(e) means for recursively applying means (a) through (d) to said descendent nodes to determine numerals representing remaining nodes descendent from said node, wherein each frontier node of said tree is associated with a label value comprising a non-composite numeral times an integer number of terminal nodes descending from said frontier node.

25. The apparatus of claim 24, wherein at least some of said numerals are based, at least in part, upon an association of trees and numerals.

26. The apparatus of claim 24, wherein said means for transforming further comprises:

means for associating numerical label values with at least some nodes or edges in said tree; and

means for associating label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerals derived, at least in part, from label values associated with said child nodes.

27. The apparatus of claim 26, wherein said means for transforming further comprises means for pruning said child nodes.

28. The apparatus of claim 26, wherein a numerical label value associated with at least one of said parent nodes is based, at least in part, on a combination of non-composite numerals derived, at least in part, from label values associated with said child nodes.

29. The apparatus of claim 26, wherein said means for transforming further comprises means for determining said non-composite numerals from an array of non-composite numerals indexed by sequential indices.

30. The apparatus of claim 24, wherein said means for transforming further comprises means for representing a parent node as a product of factors associated with one or more subtrees connected to said parent node.

31. The apparatus of claim 30, wherein said means for transforming further comprises:

means for representing at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

means for determining at least one of said factors associated with said at least one subtree as at least one non-composite numeral associated with an index in said array of non-composite numerals if a predetermined function of said at least one factor matches an index among indices of said array of non-composite numerals.

32. The apparatus of claim 30, wherein said means for transforming further comprises:

means for representing at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

means for associating said numeral in said condensed array with a substitute numeral if a predetermined function of said at least one factor does not match an index among indices of an array of non-composite numerals.

33. The apparatus of claim 32, wherein said substitute numeral comprises a multiple of a predetermined numeral and said predetermined function comprises multiplication of said numeral representing said subtree by said predetermined numeral.

34. The apparatus of claim 32, wherein said means for transforming further comprises:

means for determining a factor of said product associated with said subtree based, at least in part, on said substitute numeral.

35. The apparatus of claim 34, wherein said means for determining a factor of said product associated with said subtree further comprises means for determining said factor based, at least in part, on a natural numeral associated with an index of said array of non-composite numerals, said index corresponding with a function of said substitute numeral.

36. The apparatus of claim 24, wherein said means for determining numerals associated with one or more descendant nodes further comprises means for associating a function of said indices with one or more numerals in said array of non-composite numerals.

37. The apparatus of claim 24, wherein said tree comprises a BLT.

38. The apparatus of claim 37, wherein said means for transforming between a tree and a condensed array of numerals further comprises means for transforming between said BLT and a unary tree.

39. The apparatus of claim 37, wherein said means for transforming between said tree and said condensed array further comprises:

means for associating frontier nodes of said tree with one or more ordered pairs; and

means for associating said one or more ordered pairs with one or more single numerals according to a Cantor pairing function.

40. The apparatus of claim 39, and further comprising means for associating said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

41. The apparatus of claim 24, wherein said tree comprises an m-ary labeled tree, and wherein said means for transforming between said tree and said condensed array further comprises:

means for associating one or more frontier nodes of said tree with one or more m-dimensional expressions;

means for associating said one or more m-dimensional expressions with one or more single numerals according to a Cantor function; and

means for associating said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

42. The apparatus of claim 24, wherein said condensed array comprises a fixed size in at least one dimension.

43. The apparatus of claim 42, wherein said Condensed array comprises a plurality of entries associating substitute numerals with substituted numerals.

44. The apparatus of claim 43, wherein said substituted numerals comprise numerals associated with subtrees according to an association of trees and numerals.

45. The apparatus of claim 43, wherein said substitute numerals comprise one or more integer multiples of a predetermined non-composite numeral, said integer multiples representing one or more frontier nodes of said tree.

46. The apparatus of claim 43, wherein said substitute numerals comprise multiples of a predetermined integer, said multiples being associated with larger substituted numerals representative of subtrees.

48. The article of claim 46, wherein at least some of said numerals are based, at least in part, upon an association of trees and numerals.

49. The article of claim 46, wherein said machine-readable instructions are further executable by said processor to:

associate numerical label values with at least some nodes or edges in said tree; and

associate label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerals derived, at least in part, from label values associated with said child nodes.

50. The article of claim 49, wherein said machine-readable instructions are further executable by said processor to prune said child nodes.

51. The article of claim 49, wherein a numerical label value associated with at least one of said parent nodes is based, at least in part, on a combination of non-composite numerals derived, at least in part, from label values associated with said child nodes.

52. The article of claim 49, wherein said machine-readable instructions are further executable by said processor to determine said non-composite numerals from an array of non-composite numerals indexed by sequential indices.

47. An article comprising:

a storage medium comprising machine-readable instructions stored thereon which are executable by a processor to transform between a tree and a condensed array of numerals by;

(a) identifying a label value associated with a node of said tree;

(b) factoring said label value into two or more non-composite factors;

(c) associating said non-composite factors with indices of said condensed array of numerals, wherein said condensed array comprises a fixed number of rows or a fixed number of columns;

(d) determining numerals representing one or more descendent nodes connected to said node as a root node of said one or more subtrees based, at least in part, on said indices; and

(e) applying (a) through (d) to said descendent nodes to determine numerals representing remaining descendent nodes, wherein each frontier node of said tree is associated with a label value comprising a non-composite numeral times an integer number of terminal nodes descending from said frontier node.

53. The article of claim 47, wherein said machine-readable instructions are further executable by said processor to represent a parent node as a product of factors associated with one or more subtrees of said parent node.

54. The article of claim 53, wherein said machine-readable instructions are further executable by said processor to:

represent at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

determine at least one of said factors associated with said at least one subtree as at least one non-composite numeral associated with an index in an array of non-composite numerals if a predetermined function of said at least one factor matches an index among indices of said array of non-composite numerals.

55. The article of claim 53, wherein said machine-readable instructions are further executable by said processor to:

represent at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

associate said numeral in said condensed array with a substitute numeral if a predetermined function of said at least one factor does not match an index among indices of an array of non-composite numerals.

56. The article of claim 54, wherein said substitute numeral comprises a multiple of a predetermined numeral and said predetermined function comprises multiplication of said numeral representing said sub tree by said predetermined numeral.

57. The article of claim 54, wherein said machine-readable instructions are further executable by said processor to determine a factor of said product associated with said subtree based, at least in part, on said substitute numeral.

58. The article of claim 57, wherein said machine-readable instructions are further executable by said processor to determine said factor based, at least in part, on a natural numeral associated with an index of said array of non-composite numerals, said index corresponding with a function of said substitute numeral.

59. The article of claim 47, wherein said machine-readable instructions are further executable by said processor to associate a function of said indices with one or more numerals in said array of non-composite numerals.

60. The article of claim 47, wherein said tree comprises a BLT.

61. The article of claim 60, wherein said machine-readable instructions are further executable by said processor to transform between said BLT and a unary tree.

62. The article of claim 60, wherein said machine-readable instructions are further executable by said processor to:

associate one or more frontier nodes of said tree with one or more ordered pairs; and

associate said one or more ordered pairs with one or more single numerals according to a Cantor pairing function.

63. The article of claim 62, wherein said machine-readable instructions are further executable by said processor to associate said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

64. The article of claim 47, wherein said tree comprises an m-ary labeled tree, and wherein said machine-readable instructions are further executable by said processor to:

associate one or more frontier nodes of said tree with one or more m-dimensional expressions;

associate said one or more m-dimensional expressions with one or more single numerals according to a Cantor function; and

associate said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

65. The article of claim 47, wherein said condensed array comprises a fixed size in at least one dimension.

66. The article of claim 65, wherein said condensed array comprises a plurality of entries associating substitute numerals with substituted numerals.

67. The article of claim 66, wherein said substituted numerals comprise numerals associated with subtrees according to an association of trees and numerals.

68. The article of claim 66, wherein said substitute numerals comprise one or more integer multiples of a predetermined non-composite numeral, said integer multiples representing one or more frontier nodes of said tree.

69. The article of claim 66, wherein said substitute numerals comprise multiples of a predetermined integer, said multiples being associated with larger substituted numerals representative of subtrees.

70. An apparatus comprising:

a computing platform comprising one or more processors programmed with instructions to transform between a tree and a condensed array of numerals by;

(a) identifying a label value associated with a node of said tree;

(b) factoring said label value into two or more non-composite factors;

(c) associating said non-composite factors with indices of said condensed array of numerals, wherein said condensed array comprises a fixed number of rows or a fixed number of columns;

(d) determining numerals representing one or more descendent nodes connected to said node based, at least in part, on said indices; and

(e) applying (a) through (d) to said descendent nodes to determine numerals representing remaining descendent nodes, wherein each frontier node of said tree is associated with a label value comprising a non-composite numeral times an integer number of terminal nodes descending from said frontier node.

71. The apparatus of claim 70, wherein at least some of said numerals are based, at least in part, upon an association of trees and numerals.

72. The apparatus of claim 70, wherein said one or more processors are further programmed with instructions to:

associate numerical label values with at least some nodes or edges in said tree; and

associate label values with at least some parent nodes of child nodes based, at least in part, on non-composite numerals derived, at least in part, from label values associated with said child nodes.

73. The apparatus of claim 72, wherein said one or more processors are further programmed with instructions to prune said child nodes.

74. The apparatus of claim 72, wherein a numerical label value associated with at least one of said parent nodes is based, at least in part, on a combination of non-composite numerals derived, at least in part, from label values associated with said child nodes.

75. The apparatus of claim 72, wherein said one or more processors are further programmed to determine said non-composite numerals from an array of non-composite numerals indexed by sequential indices.

76. The apparatus of claim 70, wherein said one or more processors are further programmed with instructions to represent a parent node as a product of factors associated with one or more subtrees of said parent node.

77. The apparatus of claim 76, wherein said one or more processors are further programmed with instructions to:

represent at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

determine at least one of said factors associated with said at least one subtree as at least one non-composite numeral associated with an index in an array of non-composite numerals if a predetermined function of said at least one factor matches an index among indices of said array of non-composite numerals.

78. The apparatus of claim 76, wherein said one or more processors are further programmed with instructions to:

represent at least one of said subtrees with at least one numeral according to an association of trees and numerals; and

associate said numeral in said condensed array with a substitute numeral if a predetermined function of said at least one factor does not match an index among indices of an array of non-composite numerals.

79. The apparatus of claim 78, wherein said substitute numeral comprises a multiple of a predetermined numeral and said predetermined function comprises multiplication of said numeral representing said sub tree by said predetermined numeral.

80. The apparatus of claim 78, wherein said one or more processors are further programmed with instructions to determine a factor of said product associated with said subtree based, at least in part, on said substitute numeral.

81. The apparatus of claim 80, wherein said one or more processors are further programmed with instructions to determine said factor based, at least in part, on a natural numeral associated with an index of said array of non-composite numerals, said index corresponding with a function of said substitute numeral.

82. The apparatus of claim 70, wherein said one or more processors are further programmed with instructions to associate a function of said indices with one or more numerals in said array of non-composite numerals.

83. The apparatus of claim 70, wherein said tree comprises a BLT.

84. The apparatus of claim 83, wherein said one or more processors are further programmed with instructions to transform between said BLT and a unary tree.

85. The apparatus of claim 83, wherein said one or more processors are further programmed with instructions to:

associate one or more frontier nodes of said tree with one or more ordered pairs; and

associate said one or more ordered pairs with one or more single numerals according to a Cantor pairing function.

86. The apparatus of claim 85, wherein said one or more processors are further programmed with instructions to associate said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

87. The apparatus of claim 70, wherein said tree comprises an m-ary labeled tree, and wherein said one or more processors are further programmed with instructions to:

associate one or more frontier nodes of said tree with one or more m-dimensional expressions;

associate said one or more m-dimensional expressions with one or more single numerals according to a Cantor function; and

associate said one or more single numerals with one or more multiples of a predetermined non-composite numeral in said condensed array.

88. The apparatus of claim 70, wherein said condensed array comprises a fixed size in at least one dimension.

89. The apparatus of claim 88, wherein said condensed array comprises a plurality of entries associating substitute numerals with substituted numerals.

90. The apparatus of claim 89, wherein said substituted numerals comprise numerals associated with subtrees according to an association of trees and numerals.

91. The apparatus of claim 89, wherein said substitute numerals comprise one or more integer multiples of a predetermined non-composite numeral, said integer multiples representing one or more frontier nodes of said tree.

92. The apparatus of claim 89, wherein said substitute numerals comprise multiples of a predetermined integer, said multiples being associated with larger substituted numerals representative of subtrees.