COMMERCIAL AND INDUSTRIAL MATHEMATICS

October 24, 2014

Seminar Series


October 25, 1999
Topic: Document Resemblance and Related Issues
Speaker: Andrei Broder, Chief Technology Officer at AltaVista

ABSTRACT:

People often claim that two web pages are "the same" or "roughly the same", even though classic distances on strings (Hamming, Levenshtein, etc.) might indicate that the two pages are far apart.

To formalize these intuitive ideas we defined the mathematical concept of document resemblance. The resemblance can be estimated using a fixed size "sketch" for each document. For a large collection of documents (say 200 million) the size of this sketch is of the order of a few hundred bytes per document. However, for efficient large scale web indexing it is not necessary to determine the actual resemblance value: it suffices to determine whether newly encountered documents are duplicates or near-duplicates of documents already indexed; In other words, it suffices to determine whether the resemblance is above a certain threshold. We show how this determination can be made using a "sample" of less than 50 bytes per document.

The basic approach for computing resemblance has two aspects: first, resemblance is expressed as a set intersection problem, and second, the relative size of intersections is evaluated by a process of random sampling that can be done independently for each document. The process of estimating the relative size of intersection of sets and the threshold test discussed above can be applied to arbitrary sets, and thus might be of independent interest.

The ideas for filtering near-duplicate documents discussed here have been successfully implemented and are in current use in the context of the AltaVista search engine. This talk is tilted towards "algorithm engineering" rather than "algorithm analysis" and very little mathematical background is required.

BIOGRAPHICAL SKETCH

Andrei Broder is chief technology officer of the AltaVista Search division in the AltaVista Company. Previously he was a senior member of the research staff at Compaq's Systems Research Center in Palo Alto, California. He graduated from Technion, Israel's Institute of Technology, and did his Ph.D. in Computer Science at Stanford University under Don Knuth. He has written and co-authored more than 60 scientific papers and numerous patents. His main research interests are the design, analysis, and implementation of probabilistic algorithms and supporting data structures, in particular in the context of web-scale applications.