news2004213232529.htm

92google生成HTML新闻系统.rar

<P>　</P>
<P><BR>　 </P>
<P>　 <BR>　<BR>　 <BR>　 </P>
<P>　 Web Page Statistics </P>
<P>　 </P>
<P>　 Number of Web Pages Fetched </P>
<P>　 24 million </P>
<P>　 </P>
<P>　 Number of Urls Seen </P>
<P>　 76.5 million </P>
<P>　 </P>
<P>　 Number of Email Addresses </P>
<P>　 1.7 million </P>
<P>　 </P>
<P>　 Number of 404's </P>
<P>　 1.6 million <BR>　</P>
<P><BR>　 </P>
<P>　 <BR>　<BR>Table 1. Statistics</P>
<P><BR>　</P>
<P>5.2 System Performance<BR>It is important for a search engine to crawl and index efficiently. This way information can be kept up to date and major changes to the system can be tested relatively quickly. For Google, the major operations are Crawling, Indexing, and Sorting. It is difficult to measure how long crawling took overall because disks filled up, name servers crashed, or any number of other problems which stopped the system. In total it took roughly 9 days to download the 26 million pages (including errors). However, once the system was running smoothly, it ran much faster, downloading the last 11 million pages in just 63 hours, averaging just over 4 million pages per day or 48.5 pages per second. We ran the indexer and the crawler simultaneously. The indexer ran just faster than the crawlers. This is largely because we spent just enough time optimizing the indexer so that it would not be a bottleneck. These optimizations included bulk updates to the document index and placement of critical data structures on the local disk. The indexer runs at roughly 54 pages per second. The sorters can be run completely in parallel; using four machines, the whole process of sorting takes about 24 hours. <BR>　</P>
<P>5.3 Search Performance<BR>Improving the performance of search was not the major focus of our research up to this point. The current version of Google answers most queries in between 1 and 10 seconds. This time is mostly dominated by disk IO over NFS (since disks are spread over a number of machines). Furthermore, Google does not have any optimizations such as query caching, subindices on common terms, and other common optimizations. We intend to speed up Google considerably through distribution and hardware, software, and algorithmic improvements. Our target is to be able to handle several hundred queries per second. Table 2 has some sample query times from the current version of Google. They are repeated to show the speedups resulting from cached IO. <BR>　</P>
<P><BR>　<BR>　 <BR>　 </P>
<P>　 <BR>　</P>
<P>　</P>
<P><BR>　 <BR>　 </P>
<P>　 　 </P>
<P>　 Initial Query </P>
<P>　 Same Query Repeated (IO mostly cached) </P>
<P>　 </P>
<P>　 Query </P>
<P>　 CPU Time(s) </P>
<P>　 Total Time(s) </P>
<P>　 CPU Time(s) </P>
<P>　 Total Time(s) </P>
<P>　 </P>
<P>　 al gore </P>
<P>　 0.09 </P>
<P>　 2.13 </P>
<P>　 0.06 </P>
<P>　 0.06 </P>
<P>　 </P>
<P>　 vice president </P>
<P>　 1.77 </P>
<P>　 3.84 </P>
<P>　 1.66 </P>
<P>　 1.80 </P>
<P>　 </P>
<P>　 hard disks </P>
<P>　 0.25 </P>
<P>　 4.86 </P>
<P>　 0.20 </P>
<P>　 0.24 </P>
<P>　 </P>
<P>　 search engines </P>
<P>　 1.31 </P>
<P>　 9.63 </P>
<P>　 1.16 </P>
<P>　 1.16 <BR>　</P>
<P><BR>　 </P>
<P>　 <BR>　<BR>Table 2. Search Times</P>
<P><BR>　</P>
<P>6 Conclusions<BR>Google is designed to be a scalable search engine. The primary goal is to provide high quality search results over a rapidly growing World Wide Web. Google employs a number of techniques to improve search quality including page rank, anchor text, and proximity information. Furthermore, Google is a complete architecture for gathering web pages, indexing them, and performing search queries over them. <BR>　</P>
<P>6.1 Future Work<BR>A large-scale web search engine is a complex system and much remains to be done. Our immediate goals are to improve search efficiency and to scale to approximately 100 million web pages. Some simple improvements to efficiency include query caching, smart disk allocation, and subindices. Another area which requires much research is updates. We must have smart algorithms to decide what old web pages should be recrawled and what new ones should be crawled. Work toward this goal has been done in [Cho 98]. One promising area of research is using proxy caches to build search databases, since they are demand driven. We are planning to add simple features supported by commercial search engines like boolean operators, negation, and stemming. However, other features are just starting to be explored such as relevance feedback and clustering (Google currently supports a simple hostname based clustering). We also plan to support user context (like the user's location), and result summarization. We are also working to extend the use of link structure and link text. Simple experiments indicate PageRank can be personalized by increasing the weight of a user's home page or bookmarks. As for link text, we are experimenting with using text surrounding links in addition to the link text itself. A Web search engine is a very rich environment for research ideas. We have far too many to list here so we do not expect this Future Work section to become much shorter in the near future. <BR>　</P>
<P>6.2 High Quality Search<BR>The biggest problem facing users of web search engines today is the quality of the results they get back. While the results are often amusing and expand users' horizons, they are often frustrating and consume precious time. For example, the top result for a search for "Bill Clinton" on one of the most popular commercial search engines was the Bill Clinton Joke of the Day: April 14, 1997. Google is designed to provide higher quality search so as the Web continues to grow rapidly, information can be found easily. In order to accomplish this Google makes heavy use of hypertextual information consisting of link structure and link (anchor) text. Google also uses proximity and font information. While evaluation of a search engine is difficult, we have subjectively found that Google returns higher quality search results than current commercial search engines. The analysis of link structure via PageRank allows Google to evaluate the quality of web pages. The use of link text as a description of what the link points to helps the search engine return relevant (and to some degree high quality) results. Finally, the use of proximity information helps increase relevance a great deal for many queries. <BR>　</P>
<P>6.3 Scalable Architecture<BR>Aside from the quality of search, Google is designed to scale. It must be efficient in both space and time, and constant factors are very important when dealing with the entire Web. In implementing Google, we have seen bottlenecks in CPU, memory access, memory capacity, disk seeks, disk throughput, disk capacity, and network IO. Google has evolved to overcome a number of these bottlenecks during various operations. Google's major data structures make efficient use of available storage space. Furthermore, the crawling, indexing, and sorting operations are efficient enough to be able to build an index of a substantial portion of the web -- 24 million pages, in less than one week. We expect to be able to build an index of 100 million pages in less than a month. <BR>　</P>
<P>6.4 A Research Tool<BR>In addition to being a high quality search engine, Google is a research tool. The data Google has collected has already resulted in many other papers submitted to conferences and many more on the way. Recent research such as [Abiteboul 97] has shown a number of limitations to queries about the Web that may be answered without having the Web available locally. This means that Google (or a similar system) is not only a valuable research tool but a necessary one for a wide range of applications. We hope Google will be a resource for searchers and researchers all around the world and will spark the next generation of search engine technology. <BR>　</P>
<P>7 Acknowledgments<BR>Scott Hassan and Alan Steremberg have been critical to the development of Google. Their talented contributions are irreplaceable, and the authors owe them much gratitude. We would also like to thank Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd and the whole WebBase group for their support and insightful discussions. Finally we would like to recognize the generous support of our equipment donors IBM, Intel, and Sun and our funders. The research described here was conducted as part of the Stanford Integrated Digital Library Project, supported by the National Science Foundation under Cooperative Agreement IRI-9411306. Funding for this cooperative agreement is also provided by DARPA and NASA, and by Interval Research, and the industrial partners of the Stanford Digital Libraries Project. <BR>　</P>
<P>References</P>
<P>　</P>
<P><BR>　</P>
<P>Best of the Web 1994 -- Navigators http://botw.org/1994/awards/navigators.html <BR>　 <BR>Bill Clinton Joke of the Day: April 14, 1997. http://www.io.com/~cjburke/clinton/970414.html. <BR>　 <BR>Bzip2 Homepage http://www.muraroa.demon.co.uk/ <BR>　 <BR>Google Search Engine http://google.stanford.edu/ <BR>　 <BR>Harvest http://harvest.transarc.com/ <BR>　 <BR>Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm <BR>　 <BR>The Effect of Cellular Phone Use Upon Driver Attention http://www.webfirst.com/aaa/text/cell/cell0toc.htm <BR>　 <BR>Search Engine Watch http://www.searchenginewatch.com/ <BR>　 <BR>RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html <BR>　 <BR>Robots Exclusion Protocol: http://info.webcrawler.com/mak/projects/robots/exclusion.htm <BR>　 <BR>Web Growth Summary: http://www.mit.edu/people/mkgray/net/web-growth-summary.html <BR>　 <BR>Yahoo! http://www.yahoo.com/ </P>
<P>　</P>
<P><BR>　</P>
<P>[Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997. <BR>　 <BR>[Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557 <BR>　 <BR>[Chakrabarti 98] S.Chakrabarti, B.Dom, D.Gibson, J.Kleinberg, P. Raghavan and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998. <BR>　 <BR>[Cho 98] Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998. <BR>　 <BR>[Gravano 94] 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. <BR>　 <BR>[Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998. <BR>　 <BR>[Marchiori 97] 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. <BR>　 <BR>[McBryan 94] 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 <BR>　 <BR>[Page 98] 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 <BR>　 <BR>[Pinkerton 94] 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 <BR>　 <BR>[Spertus 97] Ellen Spertus. ParaSite: Mining Structural Information on the Web. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997. <BR>　 <BR>[TREC 96] 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/ <BR>　 <BR>[Witten 94] Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994. <BR>　 <BR>[Weiss 96] 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