Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1996-09-24
2001-07-31
Fetting, Anton W. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06269363
ABSTRACT:
TECHNICAL FIELD
The invention relates to the area of data structures.
BACKGROUND OF THE INVENTION
Data structures are important tools in the design of compilers, operating systems, algorithms and data bases. As used herein, the term data structure means a collection of data items, the relationships between the data items (e.g. the organization or arrangement of the data items) and the functions (operations) that can be applied to, or operate on, the data items. One simple example of a data structure is an integer array where the data items are integers, typically stored or arranged in an array of sequential memory locations and where the functions available include “store” (i.e. given a data item and a subscript, then associate that item with the subscript) and “retrieve” (i.e. given a subscript, provide the data item associated with the subscript).
Data structures are created and manipulated by programs executed on a computer and are stored in the computer's memory. The memory representation of a data structure is generally influenced by the hardware capabilities of the computer in which the structure will be used, and the efficiency of a particular data structure is directly influenced by the way in which the elements (items) of the structure are accessed by the memory hardware.
Although data structures may be implemented in a variety of hardware configurations, the performance of a given data structure can be quantified independent of hardware configuration, as long as a model of the computer is specified, e.g., a Random Access Machine (RAM) model. See, e.g., A. V. Aho, J. E. Hopcroft and J. D. Ullman,
The Design and Analysis of Computer Programs
, Addison-Welsey Pub. Co. Inc., Reading, Mass. (1974). Then, given a model, the performance of the given data structure can usually be quantified as a function of the number of data items in the data structure.
SUMMARY OF THE INVENTION
In accordance with the present invention, it is recognized that it may be advantageous to approximate data structures by relaxing the operations which define a data structure so that error of approximation in the results of the operations may be traded for speed in executing the operations. In particular, when an operation is relaxed as function of an error parameter then typically the speed is improved as a function of the error parameter.
The inventive notion of approximate data structures may be illustrated by an example: consider an operation which is required to find the maximum value x of an item in a data structure. A relaxed operation may be used instead to find some item y such that (1−&egr;)x≦y≦(1+&egr;)x given that the parameter &egr; has been specified beforehand. The execution time will then depend on the value of &egr;. In extreme cases, &egr; can be very large resulting in high error and trivial execution time or alternatively, &egr; may be very small resulting in an almost exact data structure with minimal saving in execution time.
REFERENCES:
patent: 4068298 (1978-01-01), Dechant et al.
patent: 4422158 (1983-12-01), Galie
patent: 5014327 (1991-05-01), Potter et al.
patent: 5051947 (1991-09-01), Messenger et al.
patent: 5053991 (1991-10-01), Burrows
patent: 5390359 (1995-02-01), Damerau
patent: 5519840 (1996-05-01), Matias et al.
patent: 5739820 (1998-04-01), Lyon
patent: 5923837 (1999-07-01), Matia
Young et al., “Approximate data structure with application,” (chapter 22), proc. 5th ACM Symp. on discrete algorithms, pp. 187-194, Jan. 1994.*
Foley et al., “Fundamentals of Interactive Computer Graphics”, Addison-Wesley Systems Programming Series, pp. 578-583, Jul. 1984.
Kahaner et al., “Numerical Methods and Software” 1989, pp. 1-80.
M. W. Bern et al., “Fast Geometric Approximation Techniques and Geometric Embedding Problems,” 5th ACM Symp. on Computational Geometry, 292-301 (1989).
Y. Matias et al., “Approximate Data Structures with Applications,” (Chapter 22) Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, Arlington, Va 187-194 (Jan. 1994).
M.W. Bern et al., “Fast Geometric Approximation Techniques and Geometric Embedding Problems,” Theoretical Computer Science, 106: 265-281 (1992).
Y. M. Matias et al., “Dynamic Generation of Discrete Random Variates,” (Chapter 39) Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 361-370 (Jan. 1993).
Corrielus Jean M.
Donner Irah H.
Fetting Anton W.
Hale and Dorr LLP
LandOfFree
Method of accessing data using approximate data structures... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of accessing data using approximate data structures..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of accessing data using approximate data structures... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521209