Barbour, A D; Phatarfod, R (1997). Dimensioning a multiple hashing scheme. Journal of Applied Probability, 34(2):477-486.
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.
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.
| Item Type: | Journal Article, refereed, original work |
|---|---|
| Communities & Collections: | 07 Faculty of Science > Institute of Mathematics |
| Dewey Decimal Classification: | 510 Mathematics |
| Scopus Subject Areas: | Physical Sciences > Statistics and Probability
Physical Sciences > General Mathematics Social Sciences & Humanities > Statistics, Probability and Uncertainty |
| Language: | English |
| Date: | 1997 |
| Deposited On: | 08 Apr 2010 13:26 |
| Last Modified: | 03 Nov 2023 03:04 |
| Publisher: | Applied Probability Trust |
| ISSN: | 0021-9002 |
| OA Status: | Green |
| Publisher DOI: | https://doi.org/10.2307/3215386 |
| Related URLs: | http://www.jstor.org/stable/3215386 |
Barbour, A D