Swipe to navigate through the chapters of this book
This chapter overviews Google web-search, one of the most ubiquitous and influential information systems available today: it stores and processes huge volumes of diverse information, scales to cope with huge numbers of users, yet produces high-quality results for each search query they type.
Aside from being so useful on a day-to-day basis, and easy to grasp, it represents an excellent example because the techniques used are based on fairly introductory Mathematics. Moving step-by-step through the application of basic graph and probability theory, the chapter acts as an introduction to both the data structures and algorithms that underpin the system as a whole.
Please log in to get access to this content
To get access to this content you need the following product:
The chapter assumes you have at least some exposure to these topics, and focuses on explaining how they are used. However, we include a number of fairly lengthy introductions in case you need a refresher or even a place to start learning about them from scratch.
A copy of the video is preserved at http://www.dougengelbart.org/firsts/dougs-1968-demo.html.
A copy of the post is preserved at http://groups.google.com/groups?selm=6487%40cernvax.cern.ch.
A copy of the web-page is preserved at http://www.w3.org/History/19921103-hypertext/hypertext/DataSources/WWW/Servers.html.
Why search? This terminology relates to how BFS and DFS are often used, namely to search for a target vertex within the graph: once the target vertex v is visited, the traversal usually stops rather than continuing to visit all vertices.
This also explains why in various descriptions, including the original research paper, p is termed a damping factor (or damping ratio); this term stems from description of a similar feature of physical systems [ 6].
go back to reference Wikipedia: Hyperlink-Induced Topic Search (HITS). http://en.wikipedia.org/wiki/HITS_algorithm Wikipedia: Hyperlink-Induced Topic Search (HITS). http://en.wikipedia.org/wiki/HITS_algorithm
go back to reference Wikipedia: HyperText Mark-up Language (HTML). http://en.wikipedia.org/wiki/HTML Wikipedia: HyperText Mark-up Language (HTML). http://en.wikipedia.org/wiki/HTML
go back to reference Wikipedia: World Wide Web Virtual Library (WWWVL). http://en.wikipedia.org/wiki/World_Wide_Web_Virtual_Library Wikipedia: World Wide Web Virtual Library (WWWVL). http://en.wikipedia.org/wiki/World_Wide_Web_Virtual_Library
- Demystifying Web-Search: the Mathematics of PageRank
- Springer International Publishing
- Sequence number
- Chapter number