Manipulation and/or analysis of hierarchical data

• US 10,055,438 B2
• Filed: 12/14/2015
• Issued: 08/21/2018
• Est. Priority Date: 04/29/2005
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.)
• Original Assignee: Robert T. Jenkins, Virginia T. Jenkins
• Inventors: Schiffmann, Karl, LeTourneau, Jack J., Andrews, Mark
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US14/968,429
• Publication Number:
  US 20160117353A1
• Time in Patent Office: 981 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments of methods, apparatuses, devices, and/or systems for representing a tree comprising at least a node or at least an edge in the form of signals and/or states, as one or more target numerical signal values substantially in accordance with transformation of the tree to the one or more target numerical signal values based at least in part on an association of trees and numerical signal values are disclosed.

Claims

1. A method comprising:

accessing instructions from one or more physical memory devices for execution by one or more processors;

executing the instructions accessed from the one or more physical memory devices by the one or more processors;

storing, in at least one of the physical memory devices, signal values, including numerical signal values, resulting from having executed the accessed instructions on the one or more processors, wherein the one or more physical memory devices also store a database or a portion thereof;

wherein the accessed instructions to transform the database, or the portion thereof, represented as a tree to one or more target numerical signals values;

wherein the transformation instructions further comprising;

representing the tree comprising at least a node or at least an edge in the form of signals and/or states, as the one or more target numerical signal values substantially in accordance with transformation of the tree to the one or more target numerical signal values based at least in part on an association of trees and numerical signal values, wherein the tree comprises electronic content comprising binary digital signals and/or states, the transformation instructions further comprising;

identifying a plurality of partial subtrees of the tree, the plurality of partial subtrees also in the form of signals and/or states;

enumerating partial subtrees of the identified plurality of partial subtrees;

associating the one or more target numerical signal values with the enumerated partial subtrees; and

comparing a probe numerical signal values with the one or more target numerical signal values to detect a presence of a subtree in the tree, wherein the probe numerical signal value is also based, at least in part, on the association of trees and numerical signal values, and wherein a correspondence between the probe numerical signal values and at least one of the one or more target numerical signal values is indicative of a presence of content in the electronic content comprising binary digital signals and/or states and indicative of location(s) within the database.

2. The method of claim 1, and further comprising:

determining the one or more target numerical signal values based, at least in part, on an association of numerical signal values with the enumerated partial subtrees of the identified plurality of partial subtrees.

3. The method of claim 2, wherein the identifying a plurality of partial subtrees of the tree further comprises:

Identifying, non-terminal nodes of the tree, as root nodes of the plurality of partial subtrees; and

identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees to be one or more nodes of an enumerated one of the partial subtrees.

4. The method of claim 3, wherein the identifying one or more nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises identifying nodes descending from a root node of at least one of the plurality of partial subtrees down to a predetermined depth to be one or more nodes of an enumerated one of the partial subtrees.

5. The method of claim 3, wherein the identifying one or more nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees based, at least in part, on node and/or edge label values associated with the nodes.

6. The method of claim 1 wherein the correspondence between the probe numerical signal value and the at least one of the one or more target numerical signal values includes a match between the probe numerical signal value and the at least one of the one or more target numerical signal values.

7. An apparatus comprising:

means for accessing instructions from one or more physical memory devices for execution by one or more processors;

means for executing the instructions accessed from the one or more physical devices by the one or more processors;

means for storing, in at least one of the physical memory devices, signals values resulting from having executed the accessed instructions on the one or more processors, wherein the one or more physical memory devices also store a database or a portion thereof;

wherein the accessed instructions to transform the database, or the portion thereof, represented as a tree to one or more target numerical signal values; and

wherein the means for executing the transformation instructions comprises;

means for representing the tree comprising at least a node or at least an edge in the form of signals and/or states as the one or more target numerical signal values substantially in accordance with transformation of the tree to the one or more target numerical signal values based at least in part on an association of trees and numerical signal values, wherein the tree comprises electronic content comprising binary digital signals and/or states, the means for executing the transformation instructions further comprising;

means for identifying a plurality of partial subtrees of the tree, the plurality of partial subtrees also in the form of signals and/or states;

means for enumerating partial subtrees of the identified plurality of partial subtrees;

means for associating the one or more target numerical signal values with the enumerated partial subtrees; and

means for comparing a probe numerical signal value in the form of signals and/or states with the one or more target numerical signal values to detect a presence of a subtree in the tree, wherein the probe numerical signal value to be based, at least in part, on the association of trees and numerical signal values, wherein a correspondence between the probe numerical signal value and at least one of the one or more target numerical signal values is indicative of a presence of content in the electronic content comprising binary digital signals and/or states and indicative of location(s) within the database.

8. The apparatus of claim 7, and further comprising:

means for determining the one or more target numerical signal values based, at least in part, on an association of numerical signal values with the enumerated partial subtrees of the identified plurality of partial subtrees.

9. The apparatus of claim 8, wherein the means for identifying the plurality of partial subtrees of the tree further comprises:

means for identifying, non-terminal nodes of the tree, as root nodes of the plurality of partial subtrees; and

means for identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees to be one or more nodes of an enumerated one of the partial subtrees.

10. The apparatus of claim 9, wherein the means for identifying one or more nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises means for identifying one or more nodes descending from a root node of at least one of the plurality of partial subtrees down to a predetermined depth to be one or more nodes of an enumerated one of the partial subtrees.

11. The apparatus of claim 9, wherein the means for identifying one or more nodes descending from the root node of the at least one of the plurality of partial subtrees further comprises means for identifying nodes descending from a root node of at least one of the plurality of partial subtrees based, at least in part, on node and/or edge label values associated with the nodes.

12. The apparatus of claim 7 further comprising:

means for generating a first array of target numerical signal values comprising numerical signal values in the form of binary digital signals and/or states associated with the partial subtrees of the tree; and

means for updating the first array of target numerical signal values by combining the one or more target numerical signal values representing the tree with the numerical signal values of the first array of target numerical signal values.

13. An apparatus comprising:

one or more processors coupled to one or more physical memory devices to store executable instructions and to store binary digital signal quantities as physical memory states, wherein the executable instructions being accessible from the one or more physical memory devices for execution by the one or more processors; and

the one or more processors able to store in at least one of the physical memory devices, binary signal quantities, if any, that are to result from execution of the instructions on the one or more processors, wherein the one or more physical memory devices also store a database or portion thereof, and wherein the executable instructions to transform the database, or portion thereof, represented as a tree to one or more target numerical signal values; and

wherein the transformation instructions further to;

represent the tree, to comprise at least a node or at least an edge in the form of signals and/or states as the one or more target numerical signal values substantially in accordance with transformation of the tree to the one or more target numerical signal values to be based at least in part on an association of trees and numerical signal values, wherein the tree to comprise electronic content comprising binary digital signals and/or states, the transformation instructions further to;

identify a plurality of partial subtrees of the tree, the plurality of partial subtrees also to be in the form of signals and/or states;

enumerate partial subtrees of the to be identified plurality of partial subtrees;

associate the one or more target numerical signal values with the to be enumerated partial subtrees; and

compare a probe numerical signal value in the form of signals and/or states with the one or more target numerical signal values to detect a presence of a subtree in the tree, the probe numerical signal value to be based, at least in part, on the association of trees and numerical signal values, and wherein a correspondence between the probe numerical signal value and at least one of the one or more target numerical signal values to indicate a presence of content in the electronic content comprising binary digital signals and/or states and indicative of location(s) within the database.

14. The apparatus of claim 13, wherein the transformation instructions further to:

generate a first array of target numerals to comprise numerical signal values in the form of signals and/or states to be associated with the partial subtrees of the tree; and

update the first array of target numerical signal values to be based at least in part on a combination of the one or more target numerical signal values to represent the tree with the numerical signal values of the first array of target numerical signal values.

15. The apparatus of claim 14, wherein the transformation instructions further to:

generate a second array of target numerical signal values to comprise numerical signal values in the form of signals and/or states to be associated with the partial subtrees of the tree; and

wherein the comparison of the probe numerical signal values with the one or more target numerical signal values to comprise a comparison of the probe numerical signal value with the numerical signal values of the first array of target numerical signal values and with the numerical signal values of the second array of target numerical signal values.

16. A method comprising:

accessing instructions from one or more physical memory devices for execution by one or more processors;

executing the instructions accessed from the one or more physical memory devices by the one or more processors;

storing, in at least one of the physical memory devices, signal values, including numerical signal values, resulting from having executed the accessed instructions on one or more processors, wherein the one or more physical memory devices also store a database or a porotion thereof;

wherein the accessed instructions to transform the database, or the portion thereof, represented as a tree to one or more target numerical signal values;

wherein the transformation instructions further comprising;

representing the tree comprising at least a node or at least an edge substantially in accordance with transformation of the tree to the one or more target numerical signal values in the form of one or more digital signals and/or states based at least in part on an association of trees and numerical signal values wherein the tree comprises electronic content comprising digital signals and/or states;

the transformation instructions further comprising;

identifying a plurality of partial subtrees of the tree, enumerating rooted partial subtrees of the identified plurality of partial subtrees, and associating the one or more digital signals for the one or more target numerical signal values with the enumerated rooted partial subtrees; and

comparing a probe numerical signal value in the form of one or more digital signals and/or states with the one or more digital signals and/or states for the one or more target numerical signal values to detect a presence of a subtree in the tree, wherein the one or more digital signals and/or states for the probe numerical signal value are also based, at least in part, on the association of trees and numerical signal values, and wherein a correspondence between the one or more digital signals and/or states for the probe numerical signal value and at least one of the one or more digital signals and/or states of the one or more target numerical signal values is indicative of a presence of content in the electronic content comprising binary digital signals and/or states and indicative of location(s) within the database.

17. The method of claim 16, wherein the executing the transformation instructions further comprises:

determining the probe numerical signal value based, at least in part, on a probe tree comprising one or more digital signals and/or states, the probe tree comprising a subtree of interest; and

detecting a presence of the subtree of interest in the tree based, at least in part, on a correspondence of the probe numerical signal value with at least one of the target numerical signal values.

18. The method of claim 17, wherein the executing the transformation instructions further comprises determining the probe numerical signal value based, at least in part, on an association between trees and numerical signal values, and wherein the correspondence corresponds with a partial subtree of the tree matching the subtree of interest.

19. The method of claim 16, wherein the tree comprises a binary edge labeled tree.

20. The method of claim 16, wherein the probe numerical signal value comprises a query with respect to the electronic content comprising digital signals and/or states.

21. The method of claim 16, wherein the tree comprises electronically stored content and the probe numerical signal value comprises a query.