Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-29
2001-11-20
Lintz, Paul R. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06321230
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to computer data structures and algorithms, and more particularly to a binary tree data structure for representing a time-varying function and to algorithms that use the data structure, for applications related to enterprise modeling.
BACKGROUND OF THE INVENTION
As applications for computer software get increasingly complex and sophisticated, so does the need for efficiency in performance of the software. An example of complex software is the “enterprise” software being used to model the operation of businesses, such as manufacturers or service providers. The enterprise model often includes time-varying quantities, such as inventory.
The enterprise model often includes scheduling type processes, where a need exists for performing queries about time-varying quantities. Sometimes the query might be a simple “function value” type of query, such as, “How many on hand at time t?”. However, a more practical “find” type of query asks for earliest/latest or maximum/minimum information. For example, a query seeking both “earliest” time and “minimum” amount information might ask, “Find the earliest time greater than t at which we will have a minimum of n units of material on hand?”, where t is the earliest time at which a task might be scheduled (due to other constraints) and n is the number of units of material that the task will consume.
One approach to solving queries involving time-varying variables is to represent values of the variable with a “binary tree”. A binary tree is a type of data structure known in the art of algorithms, which arranges data hierarchically. The tree may be queried to obtain data about the variable.
One enterprise model, manufactured at one time by Optimax Corporation under the trademark OPTIFLEX, used a binary tree to represent a time varying function. At each node, certain values relative to the “subtree” of that node were stored.
SUMMARY OF THE INVENTION
One aspect of the invention is a method of storing values of a time-varying variable. The variable is represented as a time-varying function having time values and function values. The time-varying function is then represented as a balanced binary tree, each node of the tree associated with a change in value of the function. A node may store 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. The stored values at each node are a time value, a delta value, a maximum subtree value, and a minimum subtree value. The latter two “subtree values” are referred to as such because they represent a relative contribution from the subtree beginning with that node.
REFERENCES:
patent: 5434775 (1995-07-01), Sims et al.
patent: 11203372A (1999-07-01), None
patent: 9918278 (1999-03-01), None
E. Mäkinen, “A Survey on Binary Tree Codings”, The Computer Journal, vol. 34, No. 5, pp. 438-443, 1991.
Fenner, et al. “A Study of Binary Tree Traversal Algorithms and a Tag-free Threaded Representation”, International Journal of Computer Mathematics, vol. 20, pp. 171-185, 1986.
Cline Kevin A.
Joslin David E.
Morgado Laerte F.
Baker & Botts L.L.P.
i2 Technologies US, Inc.
Lintz Paul R.
LandOfFree
Binary tree with override nodes for representing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Binary tree with override nodes for representing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary tree with override nodes for representing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2618191