A MONTE CARLO STUDY OF CICHELLI HASH-FUNCTION SOLVABILITY.

Saved in:

Bibliographic Details
Title:	A MONTE CARLO STUDY OF CICHELLI HASH-FUNCTION SOLVABILITY.
Authors:	Bell, R. Charles¹, Floyd, Bryan², Horowitz, Ellis
Source:	Communications of the ACM. Nov83, Vol. 26 Issue 11, p924-925. 2p. 5 Charts.
Subjects:	Hashing, Electronic file management, Monte Carlo method, Games of chance, Mathematical models, Numerical analysis
Abstract:	Cichelli hash functions were investigated statistically by a Monte Carlo procedure to examine the Iikelihood of their existence with token sets of various sizes, chosen with natural-language probabilities. It was found that the solvability of the Cichelli scheme became increasingly unlikely as the token set increased in size, even when the minimality condition was relaxed. With 30 tokens, the probability of a quick solution was about 50 percent. This is a seven limitation when applied to dynamic systems of tokens. However, it is anticipated that some similar technique may be developed, based on perfect but nonminimal hashing, which will effectively allow perfect minimal hashing (through a contraction table) in most cases of practical value. [ABSTRACT FROM AUTHOR]
	Copyright of Communications of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Cichelli hash functions were investigated statistically by a Monte Carlo procedure to examine the Iikelihood of their existence with token sets of various sizes, chosen with natural-language probabilities. It was found that the solvability of the Cichelli scheme became increasingly unlikely as the token set increased in size, even when the minimality condition was relaxed. With 30 tokens, the probability of a quick solution was about 50 percent. This is a seven limitation when applied to dynamic systems of tokens. However, it is anticipated that some similar technique may be developed, based on perfect but nonminimal hashing, which will effectively allow perfect minimal hashing (through a contraction table) in most cases of practical value. [ABSTRACT FROM AUTHOR]
ISSN:	00010782
DOI:	10.1145/182.358446