Searching the Web

ABSTRACT

We offer an overview of current Web search engine design. After introducing a generic search engine architecture, we examine each engine component in turn. We cover crawling, local Web page storage, indexing, and the use of link analysis for boosting search performance. The most common design and implementation techniques for each of these components are presented. For this presentation we draw from the literature and from our own experimental search engine testbed. Emphasis is on introducing the fundamental concepts and the results of several performance analyses we conducted to compare different designs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	2	ALBERT, R., BARABASI, A.-L., AND JEONG, H. 1999. Diameter of the World Wide Web. Nature 401, 6749 (Sept.).
	3	Brian Amento , Loren Terveen , Will Hill, Does “authority” mean quality? predicting expert quality ratings of Web documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.296-303, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345603]
	4	Anh Ngoc Vo , Alistair Moffat, Compressed inverted files with reduced decoding overheads, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.290-297, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291011]
	5	Ziv Bar-Yossef , Alexander Berg , Steve Chien , Jittat Fakcharoenphol , Dror Weitz, Approximating Aggregate Queries about Web Pages via Random Walks, Proceedings of the 26th International Conference on Very Large Data Bases, p.535-544, September 10-14, 2000
	6	BARABASI, A.-L. AND ALBERT, R. 1999. Emergence of scaling in random networks. Science 286, 5439 (Oct.), 509-512.
	7	Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Proceeding of the eighth international conference on World Wide Web, p.1579-1590, May 1999, Toronto, Canada
	8	Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Computer Networks and ISDN Systems, v.30 n.1-7, p.469-477, April 1, 1998
	9	Sergey Brin, Extracting Patterns and Relations from the World Wide Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.172-183, March 27-28, 1998
	10	Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
	11	Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
	12	CHAKRABARTI, S., DOM, B., GIBSON, D., KUMAR,S.R.,RAGHAVAN, P., RAJAGOPALAN, S., AND TOMKINS, A. 1998a. Spectral filtering for resource discovery. In Proceedings of the ACM SIGIR Workshop on Hypertext Information Retrieval on the Web (Melbourne, Australia). ACM Press, New York, NY.
	13	Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, ACM SIGMOD Record, v.27 n.2, p.307-318, June 1998
	14	Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
	15	Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237577]
	16	Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceeding of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
	17	CHO,J.AND GARCIA-MOLINA, H. 2000a. Estimating frequency of change. Submitted for publication.
	18	Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
	19	Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
	20	Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Computer Networks and ISDN Systems, v.30 n.1-7, p.161-172, April 1, 1998
	21	COFFMAN,E.J.,LIU, Z., AND WEBER, R. R. 1997. Optimal robot scheduling for web search engines. Tech. Rep. INRIA, Rennes, France.
	22	Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
	23	Michelangelo Diligenti , Frans Coetzee , Steve Lawrence , C. Lee Giles , Marco Gori, Focused Crawling Using Context Graphs, Proceedings of the 26th International Conference on Very Large Data Bases, p.527-534, September 10-14, 2000
	24	DOUGLIS, F., FELDMANN, A., AND KRISHNAMURTHY,, B. 1999. Rate of change and other metrics: a live study of the world wide web. In Proceedings of the USENIX Symposium on Internetworking Technologies and Systems. USENIX Assoc., Berkeley, CA.
	25	S. T. Dumais , G. W. Furnas , T. K. Landauer , S. Deerwester , R. Harshman, Using latent semantic analysis to improve access to textual information, Proceedings of the SIGCHI conference on Human factors in computing systems, p.281-285, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57214]
	26	EGGHE,L.AND ROUSSEAU, R. 1990. Introduction to Informetrics. Elsevier Science Inc., New York, NY.
	27	Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
	28	Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
	29	GARFIELD, E. 1972. Citation analysis as a tool in journal evaluation. Science 178, 471-479.
	30	David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
	31	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	32	HAVELIWALA, T. 1999. Efficient computation of pagerank. Tech. Rep. 1999-31. Computer Systems Laboratory, Stanford University, Stanford, CA. http://dbpubs.stanford.edu/ pub/1999-31.
	33	HAWKING, D., CRASWELL, N., AND THISTLEWAITE, P. 1998. Overview of TREC-7 very large collection track. In Proceedings of the 7th Conference on Text Retrieval (TREC-7).
	34	Jun Hirai , Sriram Raghavan , Hector Garcia-Molina , Andreas Paepcke, WebBase: a repository of Web pages, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.277-293, June 2000, Amsterdam, The Netherlands
	35	HUBERMAN,B.A.AND ADAMIC, L. A. 1999. Growth dynamics of the world wide web. Nature 401, 6749 (Sept.).
	36	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
	37	KOSTER, M. 1995. Robots in the web: trick or treat? ConneXions 9, 4 (Apr.).
	38	Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceeding of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
	39	LAWRENCE,S.AND GILES, C. 1998. Searching the world wide web. Science 280, 98-100.
	40	LAWRENCE,S.AND GILES, C. 1999. Accessibility of information on the web. Nature 400, 107-109.
	41	Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
	42	Ian A. MacLeod , Patrick Martin , Brent Nordin, A design of a distributed full text retrieval system, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.131-137, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253197]
	43	MELNIK, S., RAGHAVAN, S., YANG, B., AND GARCIA-MOLINA, H. 2000. Building a distributed full-text index for the web. Tech. Rep. SIDL-WP-2000-0140, Stanford Digital Library Project. Computer Systems Laboratory, Stanford University, Stanford, CA. http://www-diglib.stanford.edu/cgi-bin/get/SIDL-WP-2000-0140.
	44	Sergey Melnik , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the Web, Proceedings of the 10th international conference on World Wide Web, p.396-406, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372095]
	45	Alistair Moffat , Timothy A. H. Bell, In situ generation of compressed inverted files, Journal of the American Society for Information Science, v.46 n.7, p.537-550, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<537::AID-ASI7>3.0.CO;2-P]
	46	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	47	PAGE, L., BRIN, S., MOTWANI, R., AND WINOGRAD, T. 1998. The pagerank citation ranking: Bringing order to the web. Tech. Rep.. Computer Systems Laboratory, Stanford University, Stanford, CA.
	48	PINSKI,G.AND NARIN, F. 1976. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Inf. Process. Manage. 12.
	49	James Pitkow , Peter Pirolli, Life, death, and lawfulness on the electronic frontier, Proceedings of the SIGCHI conference on Human factors in computing systems, p.383-390, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258805]
	50	Berthier A. Ribeiro-Neto , Ramurti A. Barbosa, Query performance for tightly coupled distributed digital libraries, Proceedings of the third ACM conference on Digital libraries, p.182-190, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276695]
	51	ROBOTS EXCLUSION PROTOCOL. 2000. Robots Exclusion Protocol. http://info.webcrawler.com/ mak/projects/robots/exclusion.html.
	52	Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	53	Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
	54	Charles L. Viles , James C. French, Dissemination of collection wide information in a distributed information retrieval system, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215327]
	55	Craig E. Wills , Mikhail Mikhailov, Towards a better understanding of Web resources and server responses for improved caching, Proceeding of the eighth international conference on World Wide Web, p.1231-1243, May 1999, Toronto, Canada
	56	Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

Collaborative Colleagues:

Arvind Arasu: colleagues

Junghoo Cho: colleagues

Hector Garcia-Molina: colleagues

Andreas Paepcke: colleagues

Sriram Raghavan: colleagues