book

An Introduction to Search Engines and Web Navigation

by Mark Levene

October 2010

Intermediate to advanced

498 pages

17h 8m

English

Wiley

Read now

Unlock full access

MOTIVATIONAUDIENCE AND PREREQUISITESTIMELINESSACKNOWLEDGMENTS
1.1. BRIEF SUMMARY OF CHAPTERS1.2. BRIEF HISTORY OF HYPERTEXT AND THE WEB1.3. BRIEF HISTORY OF SEARCH ENGINES
2.1. CHAPTER OBJECTIVES2.2. SOME STATISTICS2.2.1. Web Size Statistics2.2.2. Web Usage Statistics2.3. TABULAR DATA VERSUS WEB DATA2.4. STRUCTURE OF THE WEB2.4.1. Bow-Tie Structure of the Web2.4.2. Small-World Structure of the Web2.5. INFORMATION SEEKING ON THE WEB2.5.1. Direct Navigation2.5.2. Navigation within a Directory2.5.3. Navigation using a Search Engine2.5.4. Problems with Web Information Seeking2.6. INFORMATIONAL, NAVIGATIONAL, AND TRANSACTIONAL QUERIES2.7. COMPARING WEB SEARCH TO TRADITIONAL INFORMATION RETRIEVAL2.7.1. Recall and Precision2.8. LOCAL SITE SEARCH VERSUS GLOBAL WEB SEARCH2.9. DIFFERENCE BETWEEN SEARCH AND NAVIGATION2.10. CHAPTER SUMMARY2.11. EXERCISES
3.1. CHAPTER OBJECTIVES3.2. GETTING LOST IN HYPERSPACE AND THE NAVIGATION PROBLEM3.3. HOW CAN THE MACHINE ASSIST IN USER SEARCH AND NAVIGATION3.3.1. The Potential Use of Machine Learning Algorithms3.3.2. The Naive Bayes Classifier for Categorizing Web Pages3.3.2.1. Bayes Rule3.3.2.2. Naive Bayes Assumption3.4. TRAILS SHOULD BE FIRST CLASS OBJECTS3.5. ENTER MARKOV CHAINS AND TWO INTERPRETATIONS OF ITS PROBABILITIES3.5.1. Markov Chains and the Markov Property3.5.1.1. Markov Property3.5.2. Markov Chains and the Probabilities of Following Links3.5.3. Markov Chains and the Relevance of Links3.6. CONFLICT BETWEEN WEB SITE OWNER AND VISITOR3.7. CONFLICT BETWEEN SEMANTICS OF WEB SITE AND THE BUSINESS MODEL3.8. CHAPTER SUMMARY3.9. EXERCISES
4.1. CHAPTER OBJECTIVES4.2. MECHANICS OF A TYPICAL SEARCH4.3. SEARCH ENGINES AS INFORMATION GATEKEEPERS OF THE WEB4.4. SEARCH ENGINE WARS, IS THE DUST SETTLING?4.4.1. Competitor Number One: Google4.4.2. Competitor Number Two: Yahoo4.4.3. Competitor Number Three: Bing4.4.4. Other Competitors4.5. STATISTICS FROM STUDIES OF SEARCH ENGINE QUERY LOGS4.5.1. Search Engine Query Logs4.5.2. Search Engine Query Syntax4.5.3. The Most Popular Search Keywords4.6. ARCHITECTURE OF A SEARCH ENGINE4.6.1. The Search Index4.6.2. The Query Engine4.6.3. The Search Interface4.7. CRAWLING THE WEB4.7.1. Crawling Algorithms4.7.2. Refreshing Web Pages4.7.3. The Robots Exclusion Protocol4.7.4. Spider Traps4.8. WHAT DOES IT TAKE TO DELIVER A GLOBAL SEARCH SERVICE?4.9. CHAPTER SUMMARY4.10. EXERCISES
5.1. CHAPTER OBJECTIVES5.2. CONTENT RELEVANCE5.2.1. Processing Web Pages5.2.2. Interpreting the Query5.2.3. Term Frequency5.2.4. Inverse Document Frequency5.2.5. Computing Keyword TF–IDF Values5.2.6. Caching Queries5.2.7. Phrase Matching5.2.8. Synonyms5.2.9. Link Text5.2.10. URL Analysis5.2.11. Date Last Updated5.2.12. HTML Structure Weighting5.2.13. Spell Checking5.2.14. Non-English Queries5.2.15. Home Page Detection5.2.16. Related Searches and Query Suggestions5.3. LINK-BASED METRICS5.3.1. Referential and Informational Links5.3.2. Combining Link Analysis with Content Relevance5.3.3. Are Links the Currency of the Web?5.3.4. PageRank Explained5.3.4.1. PageRank:5.3.5. Online Computation of PageRank5.3.6. Monte Carlo Methods in PageRank Computation5.3.7. Hyperlink-Induced Topic Search5.3.7.1. HITS:5.3.8. Stochastic Approach for Link-Structure Analysis5.3.8.1. SALSA:5.3.9. Counting Incoming Links5.3.10. The Bias of PageRank against New Pages5.3.11. PageRank within a Community5.3.12. Influence of Weblogs on PageRank5.3.13. Link Spam5.3.14. Citation Analysis5.3.15. The Wide Ranging Interest in PageRank5.4. POPULARITY-BASED METRICS5.4.1. Direct Hit's Popularity Metric5.4.2. Document Space Modification5.4.3. Using Query Log Data to Improve Search5.4.4. Learning to Rank5.4.5. BrowseRank5.5. EVALUATING SEARCH ENGINES5.5.1. Search Engine Awards5.5.2. Evaluation Metrics5.5.3. Performance Measures5.5.4. Eye Tracking Studies5.5.5. Test Collections5.5.6. Inferring Ranking Algorithms5.6. CHAPTER SUMMARY5.7. EXERCISES
6.1. CHAPTER OBJECTIVES6.2. DIRECTORIES AND CATEGORIZATION OF WEB CONTENT6.3. SEARCH ENGINE ADVERTISING6.3.1. Paid Inclusion6.3.2. Banner Ads6.3.3. Sponsored Search and Paid Placement6.3.4. Behavioral Targeting6.3.5. User Behavior6.3.6. The Trade-Off between Bias and Demand6.3.7. Sponsored Search Auctions6.3.8. Pay per Action6.3.9. Click Fraud and Other Forms of Advertising Fraud6.4. METASEARCH6.4.1. Fusion Algorithms6.4.2. Operational Metasearch Engines6.4.3. Clustering Search Results6.4.4. Classifying Search Results6.5. PERSONALIZATION6.5.1. Personalization versus Customization6.5.2. Personalized Results Tool6.5.3. Privacy and Scalability6.5.4. Relevance Feedback6.5.5. Personalized PageRank6.5.6. Outride's Personalized Search6.6. QUESTION ANSWERING (Q&A) ON THE WEB6.6.1. Natural Language Annotations6.6.2. Factual Queries6.6.3. Open Domain Question Answering6.6.4. Semantic Headers6.7. IMAGE SEARCH6.7.1. Text-Based Image Search6.7.2. Content-Based Image Search6.7.3. VisualRank6.7.4. CAPTCHA and reCAPTCHA6.7.5. Image Search for Finding Location-Based Information6.8. SPECIAL PURPOSE SEARCH ENGINES6.9. CHAPTER SUMMARY6.10. EXERCISES
7.1. CHAPTER OBJECTIVES7.2. FRUSTRATION IN WEB BROWSING AND NAVIGATION7.2.1. HTML and Web Site Design7.2.2. Hyperlinks and Surfing7.2.3. Web Site Design and Usability7.3. NAVIGATION TOOLS7.3.1. The Basic Browser Tools7.3.2. The Back and Forward Buttons7.3.3. Search Engine Toolbars7.3.4. The Bookmarks Tool7.3.5. The History List7.3.6. Identifying Web Pages7.3.7. Breadcrumb Navigation7.3.8. Quicklinks7.3.9. Hypertext Orientation Tools7.3.10. Hypercard Programming Environment7.4. NAVIGATIONAL METRICS7.4.1. The Potential Gain7.4.2. Structural Analysis of a Web Site7.4.3. Measuring the Usability of Web Sites7.5. WEB DATA MINING7.5.1. Three Perspectives on Data Mining7.5.2. Measuring the Success of a Web Site7.5.3. Web Analytics7.5.4. E-Metrics7.5.5. Web Analytics Tools7.5.6. Weblog File Analyzers7.5.7. Identifying the Surfer7.5.8. Sessionizing7.5.9. Supplementary Analyses7.5.10. Markov Chain Model of Web Site Navigation7.5.11. Applications of Web Usage Mining7.5.12. Information Extraction7.6. THE BEST TRAIL ALGORITHM7.6.1. Effective View Navigation7.6.2. Web Usage Mining for Personalization7.6.3. Developing a Trail Engine7.7. VISUALIZATION THAT AIDS NAVIGATION7.7.1. How to Visualize Navigation Patterns7.7.2. Overview Diagrams and Web Site Maps7.7.3. Fisheye Views7.7.4. Visualizing Trails within a Web Site7.7.5. Visual Search Engines7.7.6. Social Data Analysis7.7.7. Mapping Cyberspace7.8. NAVIGATION IN VIRTUAL AND PHYSICAL SPACES7.8.1. Real-World Web Usage Mining7.8.2. The Museum Experience Recorder7.8.3. Navigating in the Real World7.9. CHAPTER SUMMARY7.10. EXERCISES
8.1. CHAPTER OBJECTIVES8.2. THE PARADIGM OF MOBILE COMPUTING8.2.1. Wireless Markup Language8.2.2. The i-mode Service8.3. MOBILE WEB SERVICES8.3.1. M-Commerce8.3.2. Delivery of Personalized News8.3.3. Delivery of Learning Resources8.4. MOBILE DEVICE INTERFACES8.4.1. Mobile Web Browsers8.4.2. Information Seeking on Mobile Devices8.4.3. Text Entry on Mobile Devices8.4.4. Voice Recognition for Mobile Devices8.4.5. Presenting Information on a Mobile Device8.5. THE NAVIGATION PROBLEM IN MOBILE PORTALS8.5.1. Click-Distance8.5.2. Adaptive Mobile Portals8.5.3. Adaptive Web Navigation8.6. MOBILE SEARCH8.6.1. Mobile Search Interfaces8.6.2. Search Engine Support for Mobile Devices8.6.3. Focused Mobile Search8.6.4. Laid Back Mobile Search8.6.5. Mobile Query Log Analysis8.6.6. Personalization of Mobile Search8.6.7. Location-Aware Mobile Search8.7. CHAPTER SUMMARY8.8. EXERCISES

9.1. CHAPTER OBJECTIVES9.2. WHAT IS A SOCIAL NETWORK?9.2.1. Milgram's Small-World Experiment9.2.2. Collaboration Graphs9.2.3. Instant Messaging Social Network9.2.4. The Social Web9.2.5. Social Network Start-Ups9.3. SOCIAL NETWORK ANALYSIS9.3.1. Social Network Terminology9.3.2. The Strength of Weak Ties9.3.3. Centrality9.3.4. Web Communities9.3.5. Pajek: Large Network Analysis Software9.4. PEER-TO-PEER NETWORKS9.4.1. Centralized P2P Networks9.4.2. Decentralized P2P Networks9.4.3. Hybrid P2P Networks9.4.4. Distributed Hash Tables9.4.5. BitTorrent File Distribution9.4.6. JXTA P2P Search9.4.7. Incentives in P2P Systems9.5. COLLABORATIVE FILTERING9.5.1. Amazon.com9.5.2. Collaborative Filtering Explained9.5.3. User-Based Collaborative Filtering9.5.3.1. User-Based CF9.5.4. Item-Based Collaborative Filtering9.5.4.1. Item-Based CF:9.5.5. Model-Based Collaborative Filtering9.5.6. Content-Based Recommendation Systems9.5.7. Evaluation of Collaborative Filtering Systems9.5.8. Scalability of Collaborative Filtering Systems9.5.9. A Case Study of Amazon.co.uk9.5.10. The Netflix Prize9.5.11. Some Other Collaborative Filtering Systems9.6. WEBLOGS (BLOGS)9.6.1. Blogrolling9.6.2. Blogspace9.6.3. Blogs for Testing Machine Learning Algorithms9.6.4. Spreading Ideas via Blogs9.6.5. The Real-Time Web and Microblogging9.7. POWER-LAW DISTRIBUTIONS IN THE WEB9.7.1. Detecting Power-Law Distributions9.7.2. Power-Law Distributions in the Internet9.7.3. A Law of Surfing and a Law of Participation9.7.4. The Evolution of the Web via Preferential Attachment9.7.5. The Evolution of the Web as a Multiplicative Process9.7.6. The Evolution of the Web via HOT9.7.7. Small-World Networks9.7.8. The Robustness and Vulnerability of a Scale-Free Network9.8. SEARCHING IN SOCIAL NETWORKS9.8.1. Social Navigation9.8.2. Social Search Engines9.8.3. Navigation Within Social Networks9.8.4. Navigation Within Small-World Networks9.8.5. Testing Navigation Strategies in Social Networks9.9. SOCIAL TAGGING AND BOOKMARKING9.9.1. Flickr—Sharing Your Photos9.9.2. YouTube—Broadcast Yourself9.9.3. Delicious for Social Bookmarking9.9.4. Communities Within Content Sharing Sites9.9.5. Sharing Scholarly References9.9.6. Folksonomy9.9.7. Tag Clouds9.9.8. Tag Search and Browsing9.9.9. The Efficiency of Tagging9.9.10. Clustering and Classifying Tags9.10. OPINION MINING9.10.1. Feature-Based Opinion Mining9.10.2. Sentiment Classification9.10.3. Comparative Sentence and Relation Extraction9.11. WEB 2.0 AND COLLECTIVE INTELLIGENCE9.11.1. Ajax9.11.2. Syndication9.11.3. Open APIs, Mashups, and Widgets9.11.4. Software as a Service9.11.5. Collective Intelligence9.11.6. Algorithms for Collective Intelligence9.11.7. Wikipedia—The World's Largest Encyclopedia9.11.8. eBay—The World's Largest Online Trading Community9.12. CHAPTER SUMMARY9.13. EXERCISES

Content preview from An Introduction to Search Engines and Web Navigation

Preface

MOTIVATION

Searching and navigating the web have become part of our daily online lives. Web browsers and the standard navigation tools embedded in them provide a showcase of successful software technology with a global user-base, that has changed the way in which we search for and interact with information. Search engine technology has become ubiquitous, providing a standard interface to the endless amount of information that the web contains. Since the inception of the web, search engines have delivered a continuous stream of innovations, satisfying their users with increasingly accurate results through the implementation of advanced retrieval algorithms and scalable distributed architectures. Search and navigation technologies are central to the smooth operation of the web and it is hard to imagine finding information without them. Understanding the computational basis of these technologies and the models underlying them is of paramount importance both for IT students and practitioners.

There are several technical books on web search and navigation but the ones I have seen are either very academic in nature, that is, targeted at the postgraduate student or advanced researcher, and therefore have a limited audience, or they concentrate on the user interface and web site usability issues, ignoring the technicalities of what is happening behind the scenes. These books do not explain at an introductory level how the underlying computational tools work. This book answers the ...