Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-30
2003-05-06
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06560599
ABSTRACT:
COPYRIGHT NOTICE AND PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice shall apply to this document: Copyright© 1999, Microsoft, Inc.
TECHNICAL FIELD OF THE INVENTION
The present invention pertains generally to hash tables, and more particularly to a system for determining the distribution of records in a hash table, and tuning the hash table in response to such determinations.
REFERENCE TO RELATED APPLICATIONS
This application is related to a co-pending application having attorney docket number 777.256US1 Method and Apparatus for Finding Nearest Logical Record in a Hash Table which is assigned to the same assignee as the present application, filed on the same day herewith and hereby incorporated by reference.
BACKGROUND OF THE INVENTION
Linear hash tables optimize access time by evenly distributing records across the underlying table. Ideally, records may be inserted into and accessed with a single hashing operation. Furthermore, it is desirable to use system memory efficiently, to, among other things, optimize the quantity of data that may be held in memory simultaneously. If the hashing function spreads data too sparsely across the hash table index, memory optimization may be diminished. On the other hand, if the data is too closely spaced or “clumped” together, multiple access operations may be required to insert or locate a record. Accordingly, tuning or adjusting the hashing function to achieve better performance is a major goal of hash table design and operation.
The hashing function for any given data structure is thus selected to achieve optimal distribution of records in the hash table. In actual operation, the selected function is often checked for its performance, which may be done as records are initially inserted into the hash table, or later by analysis of the spread of data. Obtaining statistics for this analysis, however, may be cumbersome and time consuming. For example, in the case of a threaded linear hash table, the entire table may need to be “walked” in order to assess the distribution of data across the table. In the case of large databases, this operation may be time prohibitive to perform with any degree of regularity. Accordingly, there is a need for improved or alternate ways to assess the efficiency of the distribution of records in a hash table.
SUMMARY OF THE INVENTION
According to various example embodiments of the invention, there is provided a system for analyzing the efficiency or performance of a hash function by insertion of marker data records with known keys in a hash table together with the actual data records threaded in the hash table, and using the marker data records to analyze the distribution of actual data records around a marker data record.
In one aspect of the invention, the hash table is entered at various markers. A desired number of records is then walked using pointers and recording the index number to the hash table for each record. The index numbers are then analyzed to determine an efficiency of distribution of logically consecutive records. The hashing function may then be tuned based on the distribution as compared to a desired distribution.
REFERENCES:
patent: 5379391 (1995-01-01), Belsan et al.
patent: 5463390 (1995-10-01), Whiting et al.
patent: 5692177 (1997-11-01), Miller
patent: 5757915 (1998-05-01), Aucsmith et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5897637 (1999-04-01), Guha
patent: 6058392 (2000-05-01), Sampson et al.
patent: 6212525 (2001-03-01), Guha
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6212521 (2001-04-01), Minami et al.
patent: 6480858 (2002-11-01), Boa et al.
Slot et al., On Tape Versus Core; An Application of Space Efficient Perfect Hash Fuctions To The Invariance of Space, 1994, ACM, pp. 391-400.
Boa Douglas S.
Meacham Simon M.
Nolte Barry M.
Coby Frantz
Hennings Mark R.
LandOfFree
Method and apparatus for marking a hash table and using the... 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 marking a hash table and using the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for marking a hash table and using the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3066000