The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
나선형 해싱은 잘 알려진 동적 해싱 알고리즘입니다. 이 검색 알고리즘에 대한 전통적인 분석은 모든 키가 균일하게 액세스된다는 가정 하에 제안되었습니다. 본 논문에서는 나선형 해싱 알고리즘에 대해 각 키에 대한 접근 빈도를 고려한 평균 검색 비용의 이산적 분석을 제시한다. 제안된 이산분석에서는 프로브의 수 자체를 확률변수로 간주하여 확률분포를 구체적으로 도출한다. 제안된 분석을 통해 도출된 평가식은 접속빈도의 확률분포에 따라 검색비용의 평균과 분산을 정확하게 평가할 수 있다.
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.
부
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
부
@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},}
부
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 -