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

Chapter 2. THE WEB AND THE PROBLEM OF SEARCH

"Basically, our goal is to organise the world's information and make it universally accessible and useful."

—Larry Page, cofounder of Google

To understand the magnitude of the search problem we present some statistics regarding the size of the Web, its structure, and usage, and describe the important user activity of information seeking. We also discuss the specific challenges web search poses and compare local site search within an individual web site to global search over the entire web.

CHAPTER OBJECTIVES

Give an indication of the size of the Web, and how it can be measured.
Give an indication of the relative usage of search engines.
Highlight the differences between structured data organized in tables, and traditional web data that does not have a fixed structure.
Explain the bow-tie structure of the Web.
Introduce the notion of a small-world network (or graph) in the context of the Web.
Discuss different kinds of information-seeking strategies on the Web: direct navigation, navigating within a directory and using a search engine.
Discuss the problems inherent in web information seeking.
Introduce a taxonomy of web searches.
Present the differences between web search and traditional information retrieval.
Introduce the notions of precision and recall used to evaluate the quality of an information retrieval system, and discuss these in the context of web search.
Discuss the differences between search within a local web site and global web search. ...