Lecture Notes on Bucket Algorithms by Luc Devroye


Lecture Notes on Bucket Algorithms by Luc Devroye

Hashing algorithms scramble data and create pseudo-uniform data distribu- tions. Bucket algorithms operate on raw untransformed data which are parti- tioned Into groups according to membership In equl-slzed d-dlmenslonal hyperrec- tangles, 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 dis- tribution 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. The notes grew partially from a graduate course on probability theory In computer science. I wish to thank Elizabeth Van Gulick for her help with the manuscript, and David Avis, Hanna AYukawa, Vasek Chvatal, Beatrice Devroye, Hossam EI Glndy, Duncan McCallum, Magda McCallum, Godfrled Toussaint and Sue Whltesldes for making the School of Computer Science at McGill University such an enjoyable place. The work was supported by NSERC Grant A3456 and by FCAC Grant EQ-1679. INTRODUCTION 1 INTRODUCTION It Is not a secret that methods based upon the truncation of data have good expected time performance. For example, for nice distributions of the data, searching Is often better done via a hashing data structure Instead of via a search tree. The speed one observes In practice Is due to the fact that the truncation operation Is a constant time operation.

About the Author

Other Formats

Book Info


155 pages


Luc Devroye
More books by Luc Devroye



Publication date

1st January 1985



We love Lovereading4kids because it promotes reading choices, new authors and a sense of community for children of all ages!

Rachel Bridgeman

I am so pleased to have signed my kids up as they are reading a much wider range of books and even choosing books out of their comfort zone.

Angela East

Writing reviews help the children with their literacy skills and we always read the books together which gives us good quality family time!

Cat Bisland (on behalf of the Bi

I think Lovereading4kids is an amazing company because of the friendly staff and the fabulous chance to read great books before publication.

Adam Graham

LoveReading4Kids is a modern and creative way of emphasising the value and importance of books in this digital age #booksforlife

Amrit Bunet – Teen

It is THE website to use for narrowing down your search for any book. Definitely knocks the socks off any other book review website.

Nickey and Tomasz Hawryszczuk

I have told all my friends, family & teachers to see for themselves just how great the site is. Without fail, they are hugely impressed.

Alexander Boxall – age 11

Lovereading is just a convenient way to find new books and hear others opinions on them.

Sarah Murray – age 15

Lovereading 4 schools