Method or system for transforming between trees and arrays

• US 9,020,961 B2
• Filed: 09/24/2012
• Issued: 04/28/2015
• Est. Priority Date: 03/31/2005
• Status: Expired due to Fees

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Letourneau, Jack J.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Allen, Brittany N
• Application Number:
  US13/625,812
• Publication Number:
  US 20130198239A1
• Time in Patent Office: 946 Days
• Field of Search: 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 herein including, for example, an apparatus that includes a computing platform to transform between a tree and a condensed array of numerals.

Claims

1. An apparatus comprising:

a computing platform comprising a computing device including one or more processors;

said one or more processors including executable instructions to;

transform between binary digital signals to represent a tree and binary digital signals to represent a condensed array of numerals, wherein said condensed array of numerals is to represent said tree in a compressed and/or compact format having a fixed size in at least one dimension;

associate binary digital signals to represent numerical label values with at least one node of said tree;

derive binary digital signals to represent one or more non-composite numerals from said numerical label values to be associated with said at least one node of said tree; and

associate binary digital signals to represent a numerical label value with a parent node of said at least one node of said tree to be based, at least in part, on said derived binary digital signals to represent said one or more non-composite numerals.

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

3. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to prune said at least one node of said tree after said derived binary digital signals to represent said one or more non-composite numerals are used to associate binary digital signals to represent numerical label values with said parent node.

4. The apparatus of claim 1, wherein said binary digital signals to represent said numerical label value to be associated with said parent node are to be based, at least in part, on a combination of non-composite numerals to be derived, at least in part, from label values to be associated with child nodes of said parent node, said child nodes to comprise said at least one node of said tree.

5. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to determine said binary digital signals to represent non-composite numerals to be based at least in part on an array of non-composite numerals to be indexed by sequential indices from said condensed array of numerals, said array of non-composite numerals to be distinct from said condensed array of numerals.

6. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to:

determine two or more factors to be associated with one or more subtrees of a parent node, said two or more factors to be in the form of binary digital signals; and

determine one or more numerals to represent said parent node as a product of said two or more factors, said one or more numerals to represent said parent node in the form of binary digital signals.

7. The apparatus of claim 6, wherein said one or more processors of said computing device include executable instructions further to:

represent at least one of said one or more subtrees with at least one numeral according to an association of trees and numerals, said at least one numeral to represent said at least one of said subtrees in the form of binary digital signals; and

wherein to determine two or more factors to be associated with said one or more subtrees to comprise a match as a result of a function to be based, at least in part, on at least one of said two or more factors with an index in an array of non-composite numerals.

8. The apparatus of claim 6, wherein said one or more processors of said computing device further include instructions further to:

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

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

9. The apparatus of claim 8, wherein said substitute numeral to comprise a multiple of a predetermined numeral and said predetermined function to comprise multiplication of said numeral to represent said at least one of said one or more subtrees by said predetermined numeral.

10. The apparatus of claim 8, wherein said one or more processors of said computing device include executable instructions further to determine a factor of said product to be associated with said at least one of said one or more subtrees to be based, at least in part, on said substitute numeral.

11. The apparatus of claim 10, wherein said one or more processors of said computing device include executable instructions further to determine said factor to be based, at least in part, on a natural numeral to be associated with an index of said array of non-composite numerals, said index to correspond with a function of said substitute numeral.

12. The apparatus of claim 10, wherein said one or more processors of said computing device include executable instructions further to represent a frontier node in said condensed array of numerals as a numeral to be associated with a number of terminal node children of said frontier node.

13. The apparatus of claim 12, wherein said numeral to be associated with the number of terminal node children to comprise a multiple of a predetermined non-composite numeral.

14. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to:

factor a numeral to be associated with a node of a tree into one or more non-composite factors;

associate said non-composite factors with indices of an array of non-composite numerals; and

determine numerals to be associated with one or more subtrees associated with said node based, at least in part, on said indices.

15. The apparatus of claim 14, wherein said one or more processors of said computing device include executable instructions further to associate a function of said indices with one or more numerals in said array of non-composite numerals.

16. The apparatus of claim 1, wherein said tree to comprise a BLT with at least a node or an edge and wherein said at least a node or an edge of said BLT to represent a binary digital signal value.

17. The apparatus of claim 16, wherein said one or more processors of said computing device include executable instructions further to transform between said BLT and a unary tree.

18. The apparatus of claim 16, wherein said one or more processors of said computing device include executable instructions further 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.

19. The apparatus of claim 18, wherein said one or more processors of said computing device include executable instructions further to associate said one or more single numerals with one or more multiples of a predetermined non-composite numeral to be in said condensed array of numerals.

20. The apparatus of claim 1, wherein said tree to comprise an m-ary labeled tree, and wherein said one or more processors of said computing device include executable instructions further 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 to be in said condensed array of numerals.

21. The apparatus of claim 1, wherein said condensed array of numerals to comprise a fixed number of rows or columns.

22. The apparatus of claim 1, wherein said condensed array of numerals to comprise a plurality of entries to associate substitute numerals with substituted numerals.

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

24. The apparatus of claim 22, wherein said substitute numerals to comprise one or more integer multiples of a predetermined non-composite numeral, said integer multiples to represent one or more frontier nodes of said tree.

25. The apparatus of claim 22, wherein said substitute numerals to comprise multiples of a predetermined integer, said multiples to be associated with larger substituted numerals representative of subtrees.

26. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to:

determine a non-composite numeral to associate with a terminal node of said tree, said non-composite numeral and terminal node to be represented as binary digital signals, respectively;

determine a label value for a parent node of said terminal node, said label value to be based, at least in part, on said non-composite numeral to be associated with said terminal node, said label value also to be represented as binary digital signals;

update said condensed array of numerals with said label value for said parent node; and

prune said terminal node from said tree.

27. The apparatus of claim 1, wherein said one or more processors of said computing device include executable instructions further to:

obtain a substituted numeral value to be associated with a node of said tree from said condensed array of numerals, said substituted numeral value and said node of said tree to be represented as binary digital signals, respectively;

factor said substituted numeral value from said condensed array of numerals into non-composite factors, said non-composite factors to be associated with subtrees of said node; and

determine numerical label values for said subtrees of said node, said numerical label values to be based, at least in part, on said non-composite factors and an array of non-composite numerals.