Thumbnail
Access Restriction
Subscribed

Author Clapson, Philip
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Hashing methods ♦ Randomizing ♦ Key transformation ♦ Buckets ♦ Scatter storage ♦ Search method ♦ Collisions ♦ File structures ♦ Direct access method ♦ Combinatorics ♦ Key-to-address transformation ♦ File organizations ♦ Synonyms ♦ Information retrieval ♦ Buckets size ♦ File addressing ♦ Open chaining ♦ Clustering ♦ Open addressing ♦ Shadow buckets ♦ Direct access ♦ Hashing techniques ♦ Keys ♦ Hashing ♦ Random access ♦ Hash coding ♦ Direct addressing
Abstract Clustering in the key set is decreased by smoothing the key-to-address transformation, and by adding shadow buckets to an open chaining file. The keys are pre-hashed before the address division, to remove the effect of sequential properties in the key set. Shadow buckets in the key search sequence reduce the effect of nonuniformity in file loading, and decrease the number of maximum probes needed to locate a record. The combined effects of these techniques lead to improved file performance for secondary storage devices, as shown by empirical studies.
Description Affiliation: IBM United Kingdom Limited, Feltham, Middlesex, England (Clapson, Philip)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 3
Page Count 9
Starting Page 127
Ending Page 135


Open content in new tab

   Open content in new tab
Source: ACM Digital Library