Binary tree with override nodes for representing a time-varying function in an enterprise model

• US 6,321,230 B1
• Filed: 09/29/1999
• Issued: 11/20/2001
• Est. Priority Date: 08/11/1999
• Status: Expired due to Term

• Current Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: Cline, Kevin A., Joslin, David E., Morgado, Laerte F.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US09/408,336
• Time in Patent Office: 783 Days
• Field of Search: 707/100, 707/101, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of using a binary tree data structure to represent a time-varying variable, and to solve queries about the variable. The tree is especially useful for solving “find” type queries, such as “What is the earliest/latest time when a minimum of y units are on hand?” The binary tree is comprised of delta nodes that store delta values, that is, changes in the value of the variable. A delta value may be an “override” value, which represents a predetermined change in value of the function, such as a capacity value of a resource that is periodically replenished.

Claims

1. A method of storing values of a time-varying variable, comprising the steps of:

representing the variable as a time-varying function having time values and function values;

creating a balanced binary tree, each node of the tree associated with a change in value of the function; and

for each node, storing a time value, a delta value, a maximum subtree value, and a minimum subtree value, each subtree value representing a relative contribution from the subtree beginning with that node;

wherein at least one node is an override node, such that its delta value is a predetermined override value.

2. The method of claim 1, wherein the function is a step function and each node stores a constant delta value.

3. The method of claim 1, wherein said storing step is further performed by storing, for each node, a net subtree value representing the sum of deltas in the subtree associated with that node.

4. A method of solving find earliest/latest queries about values of a time-varying function, comprising the steps of:

representing the function as a balanced binary tree, the tree having delta nodes that each represent a change in value of the variable, each node having an associated time value, delta value, subtree maximum value, and subtree minimum value;

wherein at least one nodes stores a delta value that is a predetermined override value;

traversing the tree, at each node calculating function bounding values representing the maximum and minimum function values associated with the subtree and a start value representing the function value at the start of the time span associated with the subtree; and

at each node, using the associated function bounding values and start value to determine if the solution is in the subtree of that node.

5. The method of claim 4, wherein the query specifies an upper bound on quantity, and the traversing step solves the query by finding an earliest time when the quantity satisfies that bound.

6. The method of claim 4, wherein the query specifies an upper bound on quantity, and the traversing step solves the query by finding a latest time when the quantity satisfies that bound.

7. The method of claim 4, wherein the query specifies a lower bound of quantity, and the traversing step solves the query by finding an earliest time when the quantity satisfies that bound.

8. The method of claim 4, wherein the query specifies a lower bound of quantity, and the traversing step solves the query by finding a latest time when the quantity satisfies that bound.

9. The method of claim 4, wherein the query specifies a lower bound on time and a lower bound on quantity, and the traversing step solves the query by determining the earliest time after the specified time bound when the quantity satisfies the specified quantity bound.

10. The method of claim 4, wherein the query specifies an upper bound on time and a lower bound on quantity, and the traversing step solves the query by determining the latest time before the specified time bound when the quantity satisfies the specified quantity bound.

11. The method of claim 4, wherein the query specifies a lower bound on time and an upper bound on quantity, and the traversing step solves the query by determining the earliest time after the specified time bound when the quantity satisfies the specified quantity bound.

12. The method of claim 4, wherein the query specifies an upper bound on time and an upper bound on quantity, and the traversing step solves the query by determining the latest time before the specified time bound when the quantity satisfies the specified quantity bound.

13. The method of claim 4, wherein the query specifies a time interval, and the traversing step solves the query by determining a maximum in the time interval.

14. The method of claim 4, wherein the query specifies a time interval, and the traversing step solves the query by determining a minimum in the time interval.

15. A computer-readable medium for storing programming operable to provide values of a time-varying variable, by performing the steps of:

representing the variable in terms of a function that is a series of time value and function value pairs;

creating a balanced binary tree, each node of the tree having an associated time value and delta value representing a change in value of the function, wherein at least one delta value is a predetermined override value;

accessing the tree in response to a query; and

using delta values obtained during the accessing step to determine at least one function value that represents the value of the variable at a certain time.

16. A system for providing on-hand inventory data, comprising:

a memory that stores a balanced binary tree that representing inventory values in terms of a function that is a series of time value and function value pairs;

wherein each node of the tree has an associated time value and delta value representing a change in value of the function, and each node stores either a producer delta or a consumer delta, with each producer delta having a positive value and each consumer delta having a negative value; and

an engine for accessing the tree, the engine further operable to use delta values to determine at least one value of the function that represents inventory quantity at a certain time.

17. The system of claim 16, further comprising a user interface operable deliver query data to the engine, and to provide data output derived from the function value, in response to the query.