Thumbnail
Access Restriction
Subscribed

Author Lyon, Gordon
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Assignment problem ♦ Scatter table rearrangements ♦ Hashing ♦ Backtrack programming ♦ Recursion ♦ Open addressing
Abstract Scatter tables for open addressing benefit from recursive entry displacements, cutoffs for unsuccessful searches, and auxiliary cost functions. Compared with conventional methods, the new techniques provide substantially improved tables that resemble exact-solution optimal packings. The displacements are depth-limited approximations to an enumerative (exhaustive) optimization, although packing costs remain linear—O(n)—with table size n. The techniques are primarily suited for important fixed (but possibly quite large) tables for which reference frequencies may be known: op-code tables, spelling dictionaries, access arrays. Introduction of frequency weights further improves retrievals, but the enhancement may degrade cutoffs.
Description Affiliation: National Bureau of Standards, Washington, DC (Lyon, Gordon)
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 21
Issue Number 10
Page Count 9
Starting Page 857
Ending Page 865


Open content in new tab

   Open content in new tab
Source: ACM Digital Library