The search functionality is under construction.

The search functionality is under construction.

Spiral hashing is a well known dynamic hashing algorithm. 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 in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.988-993

- Publication Date
- 2002/05/01

- Publicized

- Online ISSN

- DOI

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

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Ayad SOUFIANE, Tsuyoshi ITOKAWA, Ryozo NAKAMURA, "An Alternative Analysis of Spiral Hashing Algorithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 988-993, May 2002, doi: .

Abstract: Spiral hashing is a well known dynamic hashing algorithm. 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 in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_988/_p

Copy

@ARTICLE{e85-a_5_988,

author={Ayad SOUFIANE, Tsuyoshi ITOKAWA, Ryozo NAKAMURA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Alternative Analysis of Spiral Hashing Algorithm},

year={2002},

volume={E85-A},

number={5},

pages={988-993},

abstract={Spiral hashing is a well known dynamic hashing algorithm. 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 in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.},

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - An Alternative Analysis of Spiral Hashing Algorithm

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 988

EP - 993

AU - Ayad SOUFIANE

AU - Tsuyoshi ITOKAWA

AU - Ryozo NAKAMURA

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

AB - Spiral hashing is a well known dynamic hashing algorithm. 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 in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.

ER -