An Alternative Analysis of Linear Dynamic Hashing Algorithm

Ayad SOUFIANE; Tsuyoshi ITOKAWA; Ryozo NAKAMURA

An Alternative Analysis of Linear Dynamic Hashing Algorithm

Ayad SOUFIANE, Tsuyoshi ITOKAWA, Ryozo NAKAMURA

Full Text Views

0

Share
Cite this

Summary :

The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1075-1081

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Ayad SOUFIANE, Tsuyoshi ITOKAWA, Ryozo NAKAMURA, "An Alternative Analysis of Linear Dynamic Hashing Algorithm" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 5, pp. 1075-1081, May 2003, doi: .
Abstract: The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1075/_p

Copy

@ARTICLE{e86-a_5_1075,
author={Ayad SOUFIANE, Tsuyoshi ITOKAWA, Ryozo NAKAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Alternative Analysis of Linear Dynamic Hashing Algorithm},
year={2003},
volume={E86-A},
number={5},
pages={1075-1081},
abstract={The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - An Alternative Analysis of Linear Dynamic Hashing Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1075
EP - 1081
AU - Ayad SOUFIANE
AU - Tsuyoshi ITOKAWA
AU - Ryozo NAKAMURA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.
ER -