Devroye L. Lecture Notes on Bucket Algorithms

Springer, 1986. — 157 p.Hashing algorithms scramble data and create pseudo-uniform data distributions. Bucket algorithms operate on raw untransformed data which are partitioned Into groups according to membership In equal-slzed d-dlmenslonal hyperrectangles, called cells or buckets. The bucket data structure Is rather sensitive to the distribution of the data. In these lecture notes, we attempt to explain the connection between the expected time of various bucket algorithms and the distribution of the data. The results are Illustrated on standard searching, sorting and selection problems, as well as on a variety of problems In computational geometry and operations research.Analysis of Bucket Sorting and Searching
Densities with Unbounded Support
Multidimensional Bucketing
The Maximal Cardinality
Auxiliary Results from Probability Theory