Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-07-05
2005-07-05
Picard, Leo (Department: 2125)
Data processing: database and file management or data structures
Database design
Data structure types
C700S090000
Reexamination Certificate
active
06915296
ABSTRACT:
Incremental reorganization of hash tables includes a copy phase and a clean phase. In the copy phase, used entries from an alternate hash table (AHT) are copied to a current hash table (CHT). During copying, hash table operations are allowed to access both tables. In the clean phase, entries in the AHT are marked as empty, and hash table operations are allowed to access only the CHT. Once all used entries have been copied from the AHT to the CHT, the clean phase begins. Once all entries in the AHT have been marked as empty during the clean phase, the two tables are switched and the copy phase begins. The copying or cleaning occurs with every hash table operation, a number of hash table operations, or a number based on analysis of recent hash table operations. Copying also occurs by avoiding copying of deleted or expired entries in the AHT. The present invention is suited to use in multithreaded real-time systems.
REFERENCES:
patent: 4996663 (1991-02-01), Nemes
patent: 5371499 (1994-12-01), Graybill et al.
patent: 5555405 (1996-09-01), Griesmer et al.
patent: 5701432 (1997-12-01), Wong et al.
patent: 6018526 (2000-01-01), Liu et al.
patent: 6067547 (2000-05-01), Douceur
patent: 6115802 (2000-09-01), Tock et al.
patent: 6134546 (2000-10-01), Bestgen et al.
patent: 6201755 (2001-03-01), Pillar et al.
patent: 6418422 (2002-07-01), Guenther et al.
patent: 6567817 (2003-05-01), VanLeer
B. Carlson, “Packets Challenge Next-Gen Nets,” EETimes, downloaded from http://www.eetimes.com/story/OEG20020802S0033 (Aug. 2002).
Friedman et al., “Hashtables for Embedded and Real-Time Systems,” IEEE Real-Time Embedded System Workshop (Dec. 2001).
Szymanski, T.G., “Hash Table Reorganization,” Journal of Algorithms, 6(3), 322-335 (1985).
Agere Systems Inc.
Picard Leo
Rodriguez Carlos Ortiz
LandOfFree
Incremental reorganization for hash tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incremental reorganization for hash tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental reorganization for hash tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3367861