Basics of Search Engines and their History

Basics of search engine algorithms (web crawling, building indexes, etc.). How has the field evolved? How have the services that search engines provide changed through the years? From WebCrawler to Inktomi to Yahoo!. How does Google's PageRank work? The use of WWW link structure to identify authoritative sources for user queries.

Presented by Mike Cafarella homepage

Before Class:

• Read (suggested in this order)

• A useful history of search engines: http://www.wiley.com/legacy/compbooks/sonnenreich/history.html
• Wikipedia's article on search engines: http://en.wikipedia.org/wiki/Search_engines
• (~4 pages) The introduction to Jon Kleinberg. Authoritative sources in a hyperlinked environment. 1999. Journal of the ACM v. 46(5). http://www.cs.cornell.edu/home/kleinber/auth.pdf.
• (2 pages) Addresses the overall structure of the web: J. Kleinberg, and S. Lawrence. The structure of the Web, Science 294, 1849-1850, November 2001. http://www.cs.washington.edu/education/courses/cse522/CurrentQtr/kleinberg_structure_of_the_web.pdf

• If you're a CSE student OR technically brave then read

• The original paper describing PageRank: Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems v. 30. http://www-db.stanford.edu/pub/papers/google.pdf.

OR

• Finish the Kleinberg article

• Otherwise, read...

• http://www.google.com/technology/
• http://www.iprcom.com/papers/pagerank/

Other Resources:

• A. Altman and M. Tennenholtz. Ranking Systems: The PageRank Axioms, ACM Conference on Electronic Commerce, 1-8, 2005. A paper which shows that under certain assumptions PageRank is the only ranking allowed. http://www.cs.washington.edu/education/courses/cse522/CurrentQtr/pagerankaxioms.pdf
• "A History of Online Information Services, 1963-1976" by Bourne and Hahn. I (Mike Cafarella) have this book and can lend it out if you're interested in primordial search engines.
• PageRank patent.