An Alternative Analysis of Spiral Hashing Algorithm(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2002-05-01

著者

• Nakamura R

  Department Of Computer Science Faculty Of Engineering Kumamoto University

• Itokawa T

  Department Of Computer Science Faculty Of Engineering Kumamoto University

• SOUFIANE Ayad

  The author is with the Graduate School of Science and Technology, Kumamoto University

• ITOKAWA Tsuyoshi

  The authors are with the Department of Computer Science, Faculty of Engineering, Kumamoto University

• NAKAMURA Ryozo

  The authors are with the Department of Computer Science, Faculty of Engineering, Kumamoto University

• Soufiane A

  Graduate School Of Science And Technology Kumamoto University

関連論文

• An Approximate Analysis of the AVL Balanced Tree Insertion Algorithm(Special Issue on Generation Database Technology for Internet, Multimedia and Mobile computing)
• A New Analysis of Hashing Algorithm for External Searching
• An Alternative Analysis of Dynamic Hashing Algorithms
• An Alternative Analysis of Spiral Hashing Algorithm(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク