Thumbnail
Access Restriction
Subscribed

Author Lum, V. Y.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Hashing methods ♦ Randomizing ♦ Information retrieval ♦ Key transformation ♦ Scatter storage ♦ Hashing techniques ♦ Randomization performance analysis ♦ Hashing ♦ Random access ♦ Hashing analysis ♦ Hash coding ♦ Key-to-address transformation ♦ Direct addressing
Abstract This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file are assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly.
Description Affiliation: IBM Research Lab, San Jose, CA (Lum, V. Y.)
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 16
Issue Number 10
Page Count 10
Starting Page 603
Ending Page 612


Open content in new tab

   Open content in new tab
Source: ACM Digital Library