Data processing: database and file management or data structures – Database and file access – Preparing data for information retrieval
Reexamination Certificate
2004-06-02
2010-11-02
Cottingham, John R. (Department: 2167)
Data processing: database and file management or data structures
Database and file access
Preparing data for information retrieval
C709S238000
Reexamination Certificate
active
07827182
ABSTRACT:
Entries are arranged in hash tables with storage for multiple entries per bucket with entries being shifted among hash tables to make room for entries being added. A path is determined through a search of the hash tables to identify where to move entries during insert operations among the hash tables to make room for a data item being added. Entries are moved and a data item added according to the identified path. Many different types of searches may be used, such as breadth-first, depth-first, random walk, etc. Also, a free position at the end of the path may be identified by being a bucket having a lowest occupancy level in a first predetermined number of levels of the search, a first bucket encountered having space available or an occupancy level less than a predetermined threshold level, with the predetermined threshold level typically being less than that of a full bucket, etc.
REFERENCES:
patent: 5893086 (1999-04-01), Schmuck et al.
patent: 6615336 (2003-09-01), Chen et al.
patent: 6819339 (2004-11-01), Dowling
patent: 2004/0153957 (2004-08-01), Feldman et al.
Pagh et al.,Cuckoo Hashing, Lecture Notes in Computer Science, Springer-Verlang GmbH, 26 pages, 2001.
Devroye et al.,Cuckoo Hashing: Further Analysis, Information Processing Letters, vol. 86, pp. 215-219, May 2003.
Fotakis et al.,Space Efficient Hash Tables with Worst Case Constant Access Time, 20th Annual Symposium on Theoretical Aspects of Computer Science, Feb. 2003.
Azar et al.,Balance Allocations(Extended Abstract), Annual ACM Symposium on Theory of Computing, Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pp. 593-602, 1994.
Andrei Broder and Michael Mitzenmacher,Using Multiple Hash Functions to Improve IP Lookups, INFOCOM 2001, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1454-1463, 2001.
Berenbrink et al.,Balanced Allocations: The Heavily Loaded Case, Annual ACM Symposium on Theory of Computing archive, Proceedings of The Thirty-Second Annual ACM Symposium on Theory of Computing Table of Contents, pp. 745-754, 2000.
Czumaj et al.,Randomized Allocation Processes, Foundations of Computer Science, Proceedings IEEE 38th Annual Symposium on, pp. 194-203, Oct. 1997.
Dietzfelbinger et al.,Dynamic Perfect Hashing: Upper and Lower Bounds, Foundations of Computer Science, 1988., 29th Annual Symposium on, pp. 524-531, Oct. 1988.
Fredman et al.,Storing a Sparse Table with O(1)Worst Case Access Time, Journal of the ACM (JACM), vol. 31, Issue 3, pp. 538 544, Jul. 1984.
Cisco Technology, Inc
Cottingham John R.
Lovel Kimberly
The Law Office of Kirk D. Williams
LandOfFree
Searching for a path to identify where to move entries among... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Searching for a path to identify where to move entries among..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching for a path to identify where to move entries among... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4157968