Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-03-08
2005-03-08
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06865577
ABSTRACT:
A method for fast and efficient record retrieval in large databases using cyclical redundancy check (CRC) computations as hash functions. Two hash values are computed for each record's key using the CRC-CCITT and CRC-16 generator polynomials. The two CRC values then are combined into a four-byte composite hash value that represents a binary signature of the record's key. Alternately, a single CRC-32 value can be used as a four-byte hash value. In most cases, this four-byte hash value uniquely identifies the record's key. An index file is constructed using a hybrid search method, part hash table and part linear search. The index file is searched to find a match for the four-byte hash value and the record's offset is obtained. The record's offset is used to retrieve the record from the database.
REFERENCES:
patent: 4945475 (1990-07-01), Bruffey et al.
patent: 5440732 (1995-08-01), Lomet et al.
patent: 5511190 (1996-04-01), Sharma et al.
patent: 5694569 (1997-12-01), Fischer
patent: 5802521 (1998-09-01), Ziauddin et al.
patent: 5809494 (1998-09-01), Nguyen
patent: 5819291 (1998-10-01), Haimowitz et al.
patent: 5956509 (1999-09-01), Kevner
patent: 6076084 (2000-06-01), Harlan
patent: 6535869 (2003-03-01), Housel, III
patent: 6553372 (2003-04-01), Brassell et al.
Raj Jain, A Comparison of Hashing Schemes for Address Lookup in Computer Networks, IEEE Transactions on Communications, Oct. 1992, vol. 40 issue 10, p. 1570-1573.*
Algorithms, by Robert Sedgewick, 2d ed., 1988, pp. 231-243.
Database Design, by Gio Wiederhold, 1977, pp. 1-3, 213-216.
C Programmer's Guide to Serial Communications, by Joe Campbell, 1sted., 1987, pp. 53-74, 538-550.
AT&T Corp.
Robinson Greta
LandOfFree
Method and system for efficiently retrieving information... 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 system for efficiently retrieving information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for efficiently retrieving information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3374353