Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-12-16
2001-01-23
Alam, Hosain T. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S250000, C370S338000
Reexamination Certificate
active
06178414
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of database and memory resource maintenance. More specifically, the present invention relates to the updating of an ordered list of values within a memory resource, either by the insertion of a value into, or the removal of a value from, the ordered list while maintaining accessibility of the ordered list for search purposes.
BACKGROUND OF THE INVENTION
A number of algorithms or methods for locating a particular element within a list of elements are well known in the prior art. Such algorithms include the binary search algorithm, the hash search algorithm and the linear search algorithm. A list which is searched using a linear search algorithm need not be ordered, but linear searches suffer from an inherent inefficiency as a key value must be compared to each and every potential target value in the list until the target value is located. A binary search (also termed a “binary chop” or “dichotomizing” search) is more efficient than a linear search, but requires that the list of elements being searched be ordered. Specifically, a binary search may involve comparing a key value against values in a list of values which are arranged in a known sequence, such as an ascending or descending order. The binary search begins by comparing the key value against a value in the middle of the list. If the key value is found to be greater than that middle value, half of the list can be discarded, and the search algorithm is then performed on the remaining half of the list. The key value is then again compared to a value in the middle of the remaining half-list, which may then again be divided into a discarded quarter-list and a remaining quarter-list. By iteratively performing this process, the key value is compared against a value in the middle of succeedingly smaller lists, and the target value is located in this manner. It will be appreciated that, as the key value is not compared against each and every value in the list, a binary search achieves a higher degree of efficiency than a linear search.
The maintenance of an ordered list of elements on which a binary search may be conducted presents a number of potential inefficiencies when elements are routinely added to or subtracted from the list which is searched. Specifically, a value being added to an ordered list must be entered into a location within the list so as to preserve the ordered nature thereof. Similarly, the removal of a value from the list must be done in a manner so as to preserve the ordered nature thereof. Accordingly, the addition of a value into an ordered list typically requires that all values greater (or less) than the inserted value be displaced within a memory resource, and shifted by a location within the memory resource, to thereby expand the list to accommodate the inserted value. Where the relevant list is of a substantial length, this displacement of values above (or below) an insertion point to accommodate an inserted value can be particularly time consuming.
It may occur that a search of a list is requested very soon after an update operation (i.e. either a value insertion or removal operation) is commenced. In one prior art methodology, access to the ordered list for search purposes is blocked during an update operation. As stated above, where a list is of a substantial length, an update operation may be time consuming, and a requested search operation will thus be forced to wait until the list has been updated prior to being serviced. Causing the search operation to wait for completion of an update operation reduces the efficiency of the entity performing the search.
In an attempt to address the above identified inefficiency, a prior art solution proposes maintaining two copies of a searchable list. An update operation is performed on a first copy of the list, while the second copy is made available to search operations. On conclusion of the update operation, the updated list is then brought “on-line” and made searchable, while the second list is taken “off-line” and updated to correspond to the first list. However, this solution suffers from the drawback of requiring that capacity be provided in a memory resource for the maintenance of two lists. Again, where a list is of considerable length, the occupation of storage capacity by the second ordered list may be undesirable.
The above difficulties with the maintenance of an ordered list have resulted in the binary search methodology being abandoned in many time-sensitive applications in favor of other search methodologies, such as the hashing methodology. However, such alternative search methodologies present their own inherent problems.
SUMMARY OF THE INVENTION
According to the invention, there is provided a method of managing an ordered list of elements stored within a memory resource. The method comprises the step of copying an element stored at a first location to a second location within the memory resource. Prior to the copying of the element stored in the first location to the second location, the second location stores a copy of a further element also stored at a third location in the memory resource. A search of the ordered list is conducted after the copying step.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 3611316 (1971-10-01), Woodrum
patent: 3916387 (1975-10-01), Woodrum
patent: 4536857 (1985-08-01), Schoenmakers
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4809158 (1989-02-01), McCauley
patent: 5121493 (1992-06-01), Ferguson
patent: 5247620 (1993-09-01), Fukuzawa et al.
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5317730 (1994-05-01), Moore et al.
patent: 5333318 (1994-07-01), Wolf
patent: 5551018 (1996-08-01), Hansen
patent: 5555405 (1996-09-01), Griesmer et al.
patent: 5560006 (1996-09-01), Layden et al.
patent: 5570084 (1996-10-01), Ritter et al.
patent: 5615366 (1997-03-01), Hansen
patent: 5649109 (1997-07-01), Griesmer et al.
patent: 5659739 (1997-08-01), Lubbers et al.
patent: 5671406 (1997-09-01), Lubbers et al.
patent: 5748905 (1998-05-01), Hauser et al.
patent: 5796944 (1998-08-01), Hill et al.
patent: 5860136 (1999-01-01), Fenner
patent: 5920854 (1999-07-01), Kirsch et al.
patent: 5926815 (1999-07-01), James, III
patent: 5953335 (1999-09-01), Erimli et al.
patent: 6009423 (1999-12-01), Moran
Horowitz, Ellis and Sahni, Sartaj; “Fundmentals of Data Structures in Turbo Pascal,” Computer Science Press; pp. 60-63 and 415-442, 1982.
Amsbury, Wayne; “Data Structures From Arrays to Priorty Queue,” Wadsworth Publishing Company; pp. 20-29, 183-186, 199-214 and 222-224, 1985.
Stone, John David, “Workshop on Scheme: Insertion Sorting,” http://www.math.grin.edu/-stone/events/scheme-workshop/insertion.htm, Jun. 25, 1996.
Kawas, EM, Computer Science 111, Lab 9, p. 3, “Further Exploration of Sorting,” http://www.cs.princeton.edu/courses/archiv/fall97/cs111/labs/sorting/3.htm, 1997.
DISCS Foundation Modules Course Ware, “Insertion Sort,” http://www.iscs.nus.sg/-p372773/ic101/content/chop11.htm, Nov. 1997.
Computer Science Department at Rensselaer, “Insert an element into a sorted range,” “Move a range backward traversal,” “Sort a range by insertions (insertion sort),” and Overview, http://www.cs.rpi.edu/-kennyz/www/ads/Algor
ode23.htm, 1997.
Beckmann Curt Eugene
Sumarsono Alex
Alam Hosain T.
Blakely , Sokoloff, Taylor & Zafman LLP
Colbert Ella
Nortel Networks Limited
LandOfFree
Method and apparatus for updating and searching an ordered... 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 and apparatus for updating and searching an ordered..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for updating and searching an ordered... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2512706