|
|
|
@inproceedings{DBLP:conf/sigmod/DeutscherST75,
author = {R. F. Deutscher and
Paul G. Sorenson and
J. Paul Tremblay},
editor = {W. Frank King},
title = {Distribution-Dependent Hashing Functions and Their Characteristics},
booktitle = {Proceedings of the 1975 ACM SIGMOD International Conference on
Management of Data, San Jose, California, May 14-16, 1975},
publisher = {ACM},
year = {1975},
pages = {224-236},
ee = {http://doi.acm.org/10.1145/500080.500111, db/conf/sigmod/DeutscherST75.html},
crossref = {DBLP:conf/sigmod/75},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
In this paper procedures are studied for storing, accessing, updating, and reorganizing data in large files whose organization is direct, an organization used when a fast response time is required. "Distribution-dependent" hashing functions and the division method are compared as methods of indirect addressing.
"Distribution-dependent" hashing functions are characterized. These hashing functions generate addresses from a set of keys by using knowledge of the distribution of that key set within the key space or range of keys. A study of the performance measures obtained during tests of these functions on several key sets indicates that in certain cases, perform better than the division method. This result is extended by a demonstration that distribution-dependent hashing functions can accommodate a change in the distribution of keys without being redefined. A number of insertions to and deletions from the key set can be made before a distribution-dependent hashing function gives poorer performance than the division method under identical circumstances.
If many additions are made to a set of keys, it becomes necessary to reorganize, in a larger storage area, the direct file of records identified by that key set. Although processor time must be sacrificed in order to redefine a distribution-dependent hashing function, the division method requires substantially greater access time in a reorganizational situation.
Copyright © 1975 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...