Logo IMG
HOME > PAST ISSUE > Article Detail


The Britney Spears Problem

Tracking who's hot and who's not presents an algorithmic challenge

Brian Hayes

Making A Hash of It

Hashing—one of the more aptly named techniques of computer science—is a way of scrambling data so that the result looks random. Oddly enough, this turns out to be a good way of making sense of the data.

A completely random stream might seem hard to analyze, but in fact randomness opens the door to some simple but powerful statistical methods. Imagine a stream composed of numbers chosen at random from some fixed range of integers, say 1 through n . For this stream the number of distinct elements observed follows a highly predictable course; in particular, all n distinct elements should have appeared at least once by the time the stream reaches length n log n.

This kind of analysis won't work for most streams of real data because the elements are not drawn from a convenient fixed range, and they are not random—unless you compose search-engine queries by blindly pecking at the keyboard. This is where hashing comes in. A hash function transforms a data item into a more-or-less random value uniformly distributed over some interval. Think of hashing as the action of a mad postal clerk sorting letters into bins. The clerk's rule says that if two letters have the same address, they go into the same bin, but in all other respects the sorting might as well be random.

By randomly distributing all the elements of a stream into a fixed number of bins, hashing allows for easy statistical analysis of the stream's elements. For example, the number of distinct elements can be estimated from the probability that a given bin remains empty, or from the minimum number of elements found in any bin. A recent paper by Ahmed Metwally and Divya­kant Agrawal of and Amr El Abbadi of the University of California, Santa Barbara, evaluates a dozen of these algorithms.

» Post Comment



Of Possible Interest

Letters to the Editors: Getting Personal

Letters to the Editors: Global Changes

Letters to the Editors: Powerful Questions


Other Related Links


Subscribe to American Scientist