Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-08-11
2002-04-16
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06374249
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to computer data structures and algorithms, and more particularly to a data structure for representing a time-varying variable and to algorithms that use the data structure.
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.
An enterprise model typically models time-varying quantities, such as inventory. The enterprise model often further models scheduling type processes, where resources and their availability are represented.
Enterprise software typically permits the user to enter 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?”. In this example, 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 commercially available enterprise model, manufactured 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 binary tree, each node of the tree associated with a change in value of the function. The tree is balanced such that each child node having a value less than that of its parent node is to the left of the parent node and each child node having a time value greater than that of its parent node is to the right of the parent node. 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. The tree has an associated bounding box function callable from any node, which is operable to use that node's subtree values to calculate one or more bounds of values of the function within the subtree. These bounds may be time bounds or quantity bounds.
An advantage of the invention is that the tree provides solutions to “earliest” and “latest” type queries. Morever, these queries may specify time limits, such as “earliest after time t” or “latest before time t”.
REFERENCES:
patent: 5434775 (1995-07-01), Sims et al.
patent: 5778223 (1998-07-01), Velissaropoulos et al.
patent: 5778370 (1998-07-01), Emerson
patent: 5787274 (1998-07-01), Agrawal et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5884300 (1999-03-01), Brockman
patent: 5890166 (1999-03-01), Eisenberg et al.
patent: 5893100 (1999-04-01), Chui et al.
patent: 6003033 (1999-12-01), Amano et al.
patent: 6006196 (1999-12-01), Feigin et al.
patent: 6052688 (2000-04-01), Thorsen
patent: 6081814 (2000-06-01), Mangat et al.
patent: 6115716 (2000-09-01), Tikkanen
patent: 6289349 (2001-09-01), Woodrum
patent: 6292797 (2001-09-01), Tuzhilin et al.
patent: 6292810 (2001-09-01), Richards
patent: 11203372 (1999-07-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.
PCT International Preliminary Examination Report, Aug. 9, 2000.
Jie et al. “A Translation-invarian Wavelet Representation Algorithm and Applications,”IEEE Transactions on Signal Processing, vol. 44, issue 2, pp. 225-232, Feb. 1996.
Joslin David E.
Morgado Laerte F.
Baker & Botts L.L.P.
Choules Jack
i2 Technologies US, Inc.
Pham Linh M
LandOfFree
Data structure and operations for time-varying variable in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure and operations for time-varying variable in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure and operations for time-varying variable in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2919969