Search Engines: Information Retrieval in Practice

1 Search Engines and Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . 11.1 What is Information Retrieval? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Search Engineers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Book Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Architecture of a Search Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1 What is an Architecture? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Basic Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Breaking It Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3.1 Text Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3.2 Text Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.3.3 Index Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.3.4 User Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.5 Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 How Does It Really Work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 Crawls and Feeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.1 Deciding what to search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.2 Crawling the Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.3 Directory Crawling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4 Document Feeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.5 The Conversion Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6 Storing the Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.7 Detecting Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.8 Removing Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 Processing Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1 From Words to Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.2 Text Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2.1 Vocabulary Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2.2 Estimating Database and Result Set Sizes . . . . . . . . . . . . . . . 574.3 Document Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.3.2 Tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.3.3 Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.3.4 Stemming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.3.5 Phrases and N-grams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.4 Document Structure and Markup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.5 Link Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.5.1 Anchor Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.5.2 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.5.3 Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.6 Information Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874.7 Internationalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925 Ranking with Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995.2 Abstract Model of Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.3 Inverted indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.3.1 Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.3.2 Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075.3.3 Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.3.4 Fields and Extents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.3.5 Scores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1125.3.6 Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135.4 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1145.4.1 Entropy and Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165.4.2 Delta Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185.4.3 Bit-aligned codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1195.4.4 Byte-aligned codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1225.4.5 Looking ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1235.4.6 Skipping and Skip Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1245.5 Auxiliary Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1265.6 Index Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.6.1 Simple Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.6.2 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1305.6.3 Parallelism and Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . 1315.6.4 Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365.7 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1385.7.1 Document-at-a-time evaluation . . . . . . . . . . . . . . . . . . . . . . . 1385.7.2 Term-at-a-time evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1405.7.3 Optimization techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1425.7.4 Structured queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1505.7.5 Distributed evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1525.7.6 Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1536 Queries and Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1596.1 Information Needs and Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1596.2 Query Transformation and Refinement . . . . . . . . . . . . . . . . . . . . . . . 1626.2.1 Stopping and Stemming Revisited . . . . . . . . . . . . . . . . . . . . . 1626.2.2 Spell Checking and Suggestions . . . . . . . . . . . . . . . . . . . . . . . 1656.2.3 Query Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1716.2.4 Relevance Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1796.2.5 Context and Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . 1836.3 Showing the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1866.3.1 Result Pages and Snippets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1866.3.2 Advertising and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1896.3.3 Clustering the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1936.4 Cross-Language Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1967 Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2057.1 Overview of Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2057.1.1 Boolean Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2077.1.2 The Vector Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2097.2 Probabilistic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.2.1 Information Retrieval as Classification . . . . . . . . . . . . . . . . . 2167.2.2 The BM25 Ranking Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 2217.3 Ranking based on Language Models . . . . . . . . . . . . . . . . . . . . . . . . . 2247.3.1 Query Likelihood Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . 2267.3.2 Relevance Models and Pseudo-Relevance Feedback . . . . . . 2327.4 Complex Queries and Combining Evidence . . . . . . . . . . . . . . . . . . . 2387.4.1 The Inference Network Model . . . . . . . . . . . . . . . . . . . . . . . . 2397.4.2 The Galago Query Language . . . . . . . . . . . . . . . . . . . . . . . . . . 2457.5 Web Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2507.6 Machine Learning and Information Retrieval . . . . . . . . . . . . . . . . . . 2557.6.1 Learning to Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2567.6.2 Topic Models and Vocabulary Mismatch . . . . . . . . . . . . . . . . 2597.7 Application-Based Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2628 Evaluating Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2698.1 Why Evaluate? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2698.2 The Evaluation Corpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2718.3 Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2778.4 Effectiveness Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2808.4.1 Recall and Precision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2808.4.2 Averaging and Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 2858.4.3 Focusing On The Top Documents . . . . . . . . . . . . . . . . . . . . . 2908.4.4 Using Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2938.5 Efficiency Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2948.6 Training, Testing, and Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2978.6.1 Significance Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2978.6.2 Setting Parameter Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3028.7 The Bottom Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3049 Classification and Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3099.1 Classification and Categorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3109.1.1 Naïve Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3129.1.2 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3209.1.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3289.1.4 Classifier and Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . 3299.1.5 Spam, Sentiment, and Online Advertising . . . . . . . . . . . . . . 3339.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3439.2.1 Hierarchical and K-Means Clustering . . . . . . . . . . . . . . . . . . 3449.2.2 K Nearest Neighbor Clustering . . . . . . . . . . . . . . . . . . . . . . . 3549.2.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3569.2.4 How to Choose K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3579.2.5 Clustering and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35910 Social Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36510.1 What is Social Search? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36510.2 User Tags and Manual Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36610.3 Searching With Communities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36610.4 Filtering and Recommending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36610.4.1 Document Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36610.4.2 Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37510.5 Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38010.6 Peer-to-Peer and Metasearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38010.6.1 Distributed search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38010.6.2 P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38411 Beyond Bag of Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39111.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39111.2 Feature-Based Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39211.3 Term Dependence Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39411.4 Structure Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39911.4.111.5 Longer Questions, Better Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 40411.6 Words, Pictures, and Music . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40811.7 One Search Fits All? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445