Web search is the quintessential large-data problem. Given an information

need expressed as a short query consisting of a few terms, the system s task

is to retrieve relevant web objects (web pages, PDF documents, PowerPoint

slides, etc.) and present them to the user. How large is the web? It is dicult

to compute exactly, but even a conservative estimate would place the size at

several tens of billions of pages, totaling hundreds of terabytes (considering

text alone). In real-world applications, users demand results quickly from a

search engine|query latencies longer than a few hundred milliseconds will try

a user s patience. Fullling these requirements is quite an engineering feat,

considering the amounts of data involved!