Search Engines: Information Retrieval in Practice

1 Search Engines and Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . 1    1.1 What is Information Retrieval? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1    1.2 Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6     1.3 Search Engineers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9     1.4 Book Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Architecture of a Search Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15     2.1 What is an Architecture? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15     2.2 Basic Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16     2.3 Breaking It Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19         2.3.1 Text Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19         2.3.2 Text Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21         2.3.3 Index Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24             2.3.4 User Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25         2.3.5 Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27         2.3.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29     2.4 How Does It Really Work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Crawls and Feeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33     3.1 Deciding what to search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33     3.2 Crawling the Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33     3.3 Directory Crawling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34     3.4 Document Feeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34     3.5 The Conversion Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34     3.6 Storing the Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35     3.7 Detecting Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36     3.8 Removing Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Processing Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47     4.1 From Words to Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47     4.2 Text Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49         4.2.1 Vocabulary Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54         4.2.2 Estimating Database and Result Set Sizes . . . . . . . . . . . . . . . 57     4.3 Document Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60         4.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60         4.3.2 Tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61         4.3.3 Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64         4.3.4 Stemming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65         4.3.5 Phrases and N-grams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71     4.4 Document Structure and Markup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75     4.5 Link Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78         4.5.1 Anchor Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79         4.5.2 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79         4.5.3 Link Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85     4.6 Information Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87     4.7 Internationalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5 Ranking with Indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99     5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99     5.2 Abstract Model of Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100     5.3 Inverted indexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103         5.3.1 Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105         5.3.2 Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107         5.3.3 Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108         5.3.4 Fields and Extents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110         5.3.5 Scores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112        5.3.6 Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113     5.4 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114         5.4.1 Entropy and Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116         5.4.2 Delta Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118         5.4.3 Bit-aligned codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119         5.4.4 Byte-aligned codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122         5.4.5 Looking ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123         5.4.6 Skipping and Skip Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . 124     5.5 Auxiliary Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126     5.6 Index Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128         5.6.1 Simple Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128         5.6.2 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130         5.6.3 Parallelism and Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . 131         5.6.4 Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136     5.7 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138         5.7.1 Document-at-a-time evaluation . . . . . . . . . . . . . . . . . . . . . . . 138         5.7.2 Term-at-a-time evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140         5.7.3 Optimization techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142         5.7.4 Structured queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150         5.7.5 Distributed evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152         5.7.6 Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 6 Queries and Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159     6.1 Information Needs and Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159     6.2 Query Transformation and Refinement . . . . . . . . . . . . . . . . . . . . . . . 162         6.2.1 Stopping and Stemming Revisited . . . . . . . . . . . . . . . . . . . . . 162         6.2.2 Spell Checking and Suggestions . . . . . . . . . . . . . . . . . . . . . . . 165         6.2.3 Query Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171         6.2.4 Relevance Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179         6.2.5 Context and Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . 183     6.3 Showing the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186         6.3.1 Result Pages and Snippets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186         6.3.2 Advertising and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189         6.3.3 Clustering the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193     6.4 Cross-Language Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 7 Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205     7.1 Overview of Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205         7.1.1 Boolean Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207         7.1.2 The Vector Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209     7.2 Probabilistic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215         7.2.1 Information Retrieval as Classification . . . . . . . . . . . . . . . . . 216         7.2.2 The BM25 Ranking Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 221     7.3 Ranking based on Language Models . . . . . . . . . . . . . . . . . . . . . . . . . 224         7.3.1 Query Likelihood Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . 226         7.3.2 Relevance Models and Pseudo-Relevance Feedback . . . . . . 232     7.4 Complex Queries and Combining Evidence . . . . . . . . . . . . . . . . . . . 238         7.4.1 The Inference Network Model . . . . . . . . . . . . . . . . . . . . . . . . 239         7.4.2 The Galago Query Language . . . . . . . . . . . . . . . . . . . . . . . . . . 245     7.5 Web Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250     7.6 Machine Learning and Information Retrieval . . . . . . . . . . . . . . . . . . 255         7.6.1 Learning to Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256         7.6.2 Topic Models and Vocabulary Mismatch . . . . . . . . . . . . . . . . 259     7.7 Application-Based Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 8 Evaluating Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269     8.1 Why Evaluate? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269     8.2 The Evaluation Corpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271     8.3 Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277     8.4 Effectiveness Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280         8.4.1 Recall and Precision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280         8.4.2 Averaging and Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 285         8.4.3 Focusing On The Top Documents . . . . . . . . . . . . . . . . . . . . . 290         8.4.4 Using Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293     8.5 Efficiency Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294     8.6 Training, Testing, and Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297         8.6.1 Significance Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297         8.6.2 Setting Parameter Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302     8.7 The Bottom Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 9 Classification and Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309     9.1 Classification and Categorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310         9.1.1 Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312         9.1.2 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320         9.1.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328         9.1.4 Classifier and Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . 329         9.1.5 Spam, Sentiment, and Online Advertising . . . . . . . . . . . . . . 333     9.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343         9.2.1 Hierarchical and K-Means Clustering . . . . . . . . . . . . . . . . . . 344         9.2.2 K Nearest Neighbor Clustering . . . . . . . . . . . . . . . . . . . . . . . 354         9.2.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356         9.2.4 How to Choose K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357         9.2.5 Clustering and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 10 Social Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365     10.1 What is Social Search? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365     10.2 User Tags and Manual Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366     10.3 Searching With Communities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366     10.4 Filtering and Recommending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366         10.4.1 Document Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366         10.4.2 Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375     10.5 Personalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380     10.6 Peer-to-Peer and Metasearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380         10.6.1 Distributed search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380         10.6.2 P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 11 Beyond Bag of Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391     11.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391     11.2 Feature-Based Retrieval Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392     11.3 Term Dependence Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394     11.4 Structure Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399         11.4.1 XML Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401     11.5 Longer Questions, Better Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . 404     11.6 Words, Pictures, and Music . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408     11.7 One Search Fits All? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445