Elamur Research
☰
home / papers / 1998 / The Anatomy of a Large-Scale Hypertextual Web Search Engine

The Anatomy of a Large-Scale Hypertextual Web Search Engine

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "author's copy (Stanford InfoLab) — read only" does not allow redistributing the text itself. Original — infolab.stanford.edu/pub/papers/google.pdf

Summary

Brin and Page present Google, a Stanford prototype search engine that addresses two connected problems in late-1990s web search. The first is keeping pace with explosive growth in pages and queries. The second is returning useful results rather than floods of weak keyword matches, which advertisers often manipulate. Their central idea is to exploit hypertext structure. PageRank scores a page's importance from the link graph. It weights links from highly ranked pages more heavily and splits each page's vote across its outgoing links. Intuitively, the score is the likelihood that a surfer clicking links at random lands on that page. Anchor text is credited to the page a link points to, not only the page containing it, so images and other non-text content become findable. Proximity and font cues refine ranking further. The paper describes the full crawling, indexing and query architecture, which was rare in a field dominated by secretive commercial engines. The authors judge their results subjectively better than those of competitors. The work established link-based ranking and offered Google as an open platform for large-scale web research.

Key points

  • The prototype stores the complete text and link structure of no fewer than 24 million pages. It can build an index of that size in under a week, and the authors expect to reach 100 million pages in under a month.
  • The link maps contain up to 518 million hyperlinks. PageRank uses a damping factor d, usually 0.85, and takes a few hours to compute for 26 million pages on a mid-sized workstation.
  • The scaling context shows how fast the web grew. The World Wide Web Worm (WWWW) indexed 110,000 pages in 1994 and handled about 1,500 queries per day. By November 1997, AltaVista reported roughly 20 million queries per day.
  • Quality problems among competitors were serious. In November 1997, only one of the four leading commercial engines returned its own search page in the top ten results for a query on its own name.
  • Sample query times ranged from about 2 to 10 seconds on first run (e.g., "al gore" took 2.13 s). Repeated runs with cached IO dropped to roughly 0.06–1.8 s.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

279 papers of our library cite it (of the 140673 whose bibliographies we read); 5 of them have a page here, 274 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1016/s0169-7552(98)00110-x

@inproceedings{brin1998anatomy,
  title = {{The Anatomy of a Large-Scale Hypertextual Web Search Engine}},
  author = {Brin, Sergey and Page, Lawrence},
  booktitle = {WWW7 / Computer Networks and ISDN Systems 30},
  year = {1998},
  doi = {10.1016/s0169-7552(98)00110-x},
  url = {https://doi.org/10.1016/s0169-7552(98)00110-x}
}

References

13 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997. find
  2. Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557 find
  3. Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998. find
  4. Luis Gravano, Hector Garcia-Molina, and A. Tomasic. The Effectiveness of GlOSS for the Text-Database Discovery Problem. Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data, 1994. find
  5. Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998. find our card
  6. Massimo Marchiori. The Quest for Correct Information on the Web: Hyper Search Engines. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997. find
  7. Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps ↗
  8. Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. http://google.stanford.edu/~backrub/pageranksub.ps ↗ our card
  9. Brian Pinkerton, Finding What People Want: Experiences with the WebCrawler. The Second International WWW Conference Chicago, USA, October 17-20, 1994. http://info.webcrawler.com/bp/WWW94.html ↗
  10. Ellen Spertus. ParaSite: Mining Structural Information on the Web. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997. find
  11. Proceedings of the fifth Text REtrieval Conference (TREC-5). Gaithersburg, Maryland, November 20-22, 1996. Publisher: Department of Commerce, National Institute of Standards and Technology. Editors: D. K. Harman and E. M. Voorhees. Full text at: http://trec.nist.gov/ ↗
  12. Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994. find
  13. Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda, and David K. Gifford. HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering. Proceedings of the 7th ACM Conference on Hypertext. New York, 1996. Vitae Sergey Br… find