Introduction to information retrieval

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Table of Notation......Page 13
Preface......Page 17
1 Boolean retrieval......Page 25
1.1 An example information retrieval problem......Page 27
1.2 A first take at building an inverted index......Page 30
1.3 Processing Boolean queries......Page 33
1.4 The extended Boolean model versus ranked retrieval......Page 37
1.5 References and further reading......Page 40
2.1.1 Obtaining the character sequence in a document......Page 42
2.1.2 Choosing a document unit......Page 44
2.2.1 Tokenization......Page 45
2.2.2 Dropping common terms: stop words......Page 49
2.2.3 Normalization (equivalence classing of terms)......Page 50
2.2.4 Stemming and lemmatization......Page 54
2.3 Faster postings list intersection via skip pointers......Page 57
2.4.1 Biword indexes......Page 60
2.4.2 Positional indexes......Page 62
2.4.3 Combination schemes......Page 64
2.5 References and further reading......Page 67
3.1 Search structures for dictionaries......Page 69
3.2.1 General wildcard queries......Page 72
3.2.2 k-gram indexes for wildcard queries......Page 74
3.3.1 Implementing spelling correction......Page 76
3.3.3 Edit distance......Page 77
3.3.4 k-gram indexes for spelling correction......Page 79
3.3.5 Context-sensitive spelling correction......Page 81
3.4 Phonetic correction......Page 82
3.5 References and further reading......Page 83
4 Index construction......Page 85
4.1 Hardware basics......Page 86
4.2 Blocked sort-based indexing......Page 87
4.3 Single-pass in-memory indexing......Page 90
4.4 Distributed indexing......Page 92
4.5 Dynamic indexing......Page 95
4.6 Other types of indexes......Page 97
4.7 References and further reading......Page 100
5 Index compression......Page 102
5.1 Statistical properties of terms in information retrieval......Page 103
5.1.1 Heaps' law: Estimating the number of terms......Page 105
5.2 Dictionary compression......Page 106
5.2.1 Dictionary as a string......Page 107
5.2.2 Blocked storage......Page 109
5.3 Postings file compression......Page 111
5.3.1 Variable byte codes......Page 112
5.3.2 Gamma codes......Page 114
5.4 References and further reading......Page 121
6 Scoring, term weighting, and the vector space model......Page 124
6.1 Parametric and zone indexes......Page 125
6.1.1 Weighted zone scoring......Page 126
6.1.2 Learning weights......Page 128
6.1.3 The optimal weight g......Page 130
6.2 Term frequency and weighting......Page 131
6.2.1 Inverse document frequency......Page 132
6.2.2 Tf--idf weighting......Page 133
6.3.1 Dot products......Page 134
6.3.2 Queries as vectors......Page 137
6.3.3 Computing vector scores......Page 138
6.4.1 Sublinear tf scaling......Page 140
6.4.2 Maximum tf normalization......Page 141
6.4.4 Pivoted normalized document length......Page 142
6.5 References and further reading......Page 146
7.1 Efficient scoring and ranking......Page 148
7.1.1 Inexact top K document retrieval......Page 149
7.1.2 Index elimination......Page 150
7.1.4 Static quality scores and ordering......Page 151
7.1.5 Impact ordering......Page 153
7.1.6 Cluster pruning......Page 154
7.2.2 Query term proximity......Page 156
7.2.3 Designing parsing and scoring functions......Page 157
7.2.4 Putting it all together......Page 159
7.3 Vector space scoring and query operator interaction......Page 160
7.4 References and further reading......Page 161
8 Evaluation in information retrieval......Page 163
8.1 Information retrieval system evaluation......Page 164
8.2 Standard test collections......Page 165
8.3 Evaluation of unranked retrieval sets......Page 166
8.4 Evaluation of ranked retrieval results......Page 169
8.5 Assessing relevance......Page 175
8.5.1 Critiques and justifications of the concept of relevance......Page 177
8.6 A broader perspective: System quality and user utility......Page 178
8.6.2 User utility......Page 179
8.6.3 Refining a deployed system......Page 180
8.7 Results snippets......Page 181
8.8 References and further reading......Page 183
9 Relevance feedback and query expansion......Page 186
9.1.1 The Rocchio algorithm for relevance feedback......Page 187
9.1.2 Probabilistic relevance feedback......Page 192
9.1.3 When does relevance feedback work?......Page 193
9.1.5 Evaluation of relevance feedback strategies......Page 194
9.1.6 Pseudo relevance feedback......Page 195
9.1.8 Summary......Page 196
9.2.2 Query expansion......Page 197
9.2.3 Automatic thesaurus generation......Page 199
9.3 References and further reading......Page 201
10 XML retrieval......Page 202
10.1 Basic XML concepts......Page 204
10.2 Challenges in XML retrieval......Page 207
10.3 A vector space model for XML retrieval......Page 212
10.4 Evaluation of XML retrieval......Page 216
10.5 Text-centric versus data-centric XML retrieval......Page 220
10.6 References and further reading......Page 222
11 Probabilistic information retrieval......Page 225
11.1 Review of basic probability theory......Page 226
11.2.1 The 1/0 loss case......Page 227
11.3 The binary independence model......Page 228
11.3.1 Deriving a ranking function for query terms......Page 229
11.3.2 Probability estimates in theory......Page 231
11.3.4 Probabilistic approaches to relevance feedback......Page 233
11.4.1 An appraisal of probabilistic models......Page 236
11.4.3 Okapi BM25: A nonbinary model......Page 237
11.4.4 Bayesian network approaches to information retrieval......Page 239
11.5 References and further reading......Page 240
12.1.1 Finite automata and language models......Page 242
12.1.2 Types of language models......Page 245
12.1.3 Multinomial distributions over words......Page 246
12.2.1 Using query likelihood language models in IR......Page 247
12.2.2 Estimating the query generation probability......Page 248
12.2.3 Ponte and Croft's experiments......Page 251
12.3 Language modeling versus other approachesin information retrieval......Page 253
12.4 Extended language modeling approaches......Page 254
12.5 References and further reading......Page 256
13 Text classification and Naive Bayes......Page 258
13.1 The text classification problem......Page 261
13.2 Naive Bayes text classification......Page 262
13.2.1 Relation to multinomial unigram language model......Page 266
13.3 The Bernoulli model......Page 267
13.4 Properties of Naive Bayes......Page 269
13.4.1 A variant of the multinomial model......Page 274
13.5 Feature selection......Page 275
13.5.1 Mutual information......Page 276
13.5.2 Chi2 Feature selection......Page 279
13.5.5 Comparison of feature selection methods......Page 281
13.6 Evaluation of text classification......Page 282
13.7 References and further reading......Page 288
14 Vector space classification......Page 290
14.1 Document representations and measures of relatedness in vector spaces......Page 291
14.2 Rocchio classification......Page 293
14.3 k nearest neighbor......Page 297
14.3.1 Time complexity and optimality of k nearest neighbor......Page 299
14.4 Linear versus nonlinear classifiers......Page 301
14.5 Classification with more than two classes......Page 305
14.6 The bias--variance tradeoff......Page 308
14.7 References and further reading......Page 315
15 Support vector machines and machine learning on documents......Page 317
15.1 Support vector machines: The linearly separable case......Page 318
15.2.1 Soft margin classification......Page 324
15.2.3 Nonlinear support vector machines......Page 327
15.2.4 Experimental results......Page 330
15.3 Issues in the classification of text documents......Page 331
15.3.1 Choosing what kind of classifier to use......Page 332
15.3.2 Improving classifier performance......Page 333
15.4.1 A simple example of machine-learned scoring......Page 338
15.4.2 Result ranking by machine learning......Page 340
15.5 References and further reading......Page 342
16 Flat clustering......Page 345
16.1 Clustering in information retrieval......Page 346
16.2 Problem statement......Page 350
16.3 Evaluation of clustering......Page 351
16.4 K-means......Page 355
16.4.1 Cluster cardinality in K-means......Page 360
16.5 Model-based clustering......Page 362
16.6 References and further reading......Page 367
17 Hierarchical clustering......Page 370
17.1 Hierarchical agglomerative clustering......Page 371
17.2 Single-link and complete-link clustering......Page 374
17.2.1 Time complexity......Page 377
17.3 Group-average agglomerative clustering......Page 380
17.4 Centroid clustering......Page 382
17.5 Optimality of hierarchical agglomerative clustering......Page 384
17.6 Divisive clustering......Page 386
17.7 Cluster labeling......Page 387
17.8 Implementation notes......Page 389
17.9 References and further reading......Page 391
18.1 Linear algebra review......Page 393
18.1.1 Matrix decompositions......Page 396
18.2 Term--document matrices and singular value decompositions......Page 397
18.3 Low-rank approximations......Page 400
18.4 Latent semantic indexing......Page 402
18.5 References and further reading......Page 407
19.1 Background and history......Page 409
19.2 Web characteristics......Page 411
19.2.1 The web graph......Page 413
19.2.2 Spam......Page 414
19.3 Advertising as the economic model......Page 416
19.4.1 User query needs......Page 419
19.5 Index size and estimation......Page 420
19.6 Near-duplicates and shingling......Page 424
19.7 References and further reading......Page 428
20.1.1 Features a crawler must provide......Page 429
20.2 Crawling......Page 430
20.2.1 Crawler architecture......Page 431
20.2.2 DNS resolution......Page 435
20.2.3 The URL frontier......Page 436
20.3 Distributing indexes......Page 439
20.4 Connectivity servers......Page 440
20.5 References and further reading......Page 443
21 Link analysis......Page 445
21.1.1 Anchor text and the web graph......Page 446
21.2 PageRank......Page 448
21.2.1 Markov chains......Page 449
21.2.2 The PageRank computation......Page 451
21.2.3 Topic-specific PageRank......Page 454
21.3 Hubs and authorities......Page 457
21.3.1 Choosing the subset of the Web......Page 460
21.4 References and further reading......Page 463
Bibliography......Page 465
Index......Page 493