Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-27T07:03:31.802Z Has data issue: false hasContentIssue false
  • English
  • Français

Dimensioning a multiple hashing scheme

Part of: Distribution theory Theory of data Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

A. D. Barbour  and
R. M. Phatarfod
A. D. Barbour*
Affiliation:
Universität Zurich
R. M. Phatarfod*
Affiliation:
Monash University
*
∗Postal address: Institut für Angewandte Mathematik, Universität Zurich, Winterthurerstrasse 190, CH-8057, Switzerland.
∗∗Postal address: Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

The number of items of data which are irretrievable without additional effort after hashing can be greatly reduced if several hash tables are used simultaneously. Here we show that, in a multiple hashing scheme, this number has a distribution very close to Poisson. Thus choosing the number and sizes of the tables to minimize the expected number of irretrievable items is the right way to dimension a scheme.

Keywords

DATA STORAGEMULTIPLE HASHING SCHEME

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 62E17: Approximations to distributions (nonasymptotic) 68P20: Information storage and retrieval
Type
Research Article
Information
Journal of Applied Probability , Volume 34 , Issue 2 , June 1997 , pp. 477 - 486
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation. Clarendon Press, Oxford.CrossRefGoogle Scholar
Kruse, R. L. (1987) Data Structures and Program Design. 2nd edn. Prentice Hall, New Jersey.Google Scholar
Srinivasan, B., Kulkarni, S. and Phatarfod, R. M. (1995) A storage efficient structure for dictionary coding. Tech. Report 95/05. Dept Computer Technology, Monash University.Google Scholar