List of Figures

1. Results from Shakespeare for the query Brutus AND Caesar AND NOT Calpurnia.
2. Intersecting the postings lists for Brutus and Calpurnia from Figure 1.3 .
3. Algorithm for the intersection of two postings lists $p_1$ and $p_2$.
4. Algorithm for conjunctive queries that returns the set of documents containing each term in the input list of terms.
5. A stop list of 25 semantically non-selective words which are common in Reuters-RCV1.
6. An example of how asymmetric expansion of query terms can usefully model users' expectations.
7. A comparison of three stemming algorithms on a sample text.
8. Postings lists intersection with skip pointers.
9. A portion of a permuterm index.
10. Dynamic programming algorithm for computing the edit distance between strings $s_1$ and $s_2$.
11. Matching at least two of the three 2-grams in the query bord.
12. Document from the Reuters newswire.
13. Inversion of a block in single-pass in-memory indexing
14. An example of distributed indexing with MapReduce. Adapted from Dean and Ghemawat (2004).
15. Logarithmic merging. Each token (termID,docID) is initially added to in-memory index $Z_0$ by LMERGEADDTOKEN. LOGARITHMICMERGE initializes $Z_0$ and $indexes$.
16. A user-document matrix for access control lists. Element $(i,j)$ is 1 if user $i$ has access to document $j$ and 0 otherwise. During query processing, a user's access postings list is intersected with the results list returned by the text part of the index.
17. Storing the dictionary as an array of fixed-width entries.
18. Search of the uncompressed dictionary (a) and a dictionary compressed by blocking with $k=4$ (b).
19. Entropy $H(P)$ as a function of $P(x_1)$ for a sample space with two outcomes $x_1$ and $x_2$.
20. Stratification of terms for estimating the size of a $\gamma$ encoded inverted index.
21. Zone index in which the zone is encoded in the postings rather than the dictionary.
22. An illustration of training examples.
23. The four possible combinations of $s_T$ and $s_B$.
24. Collection frequency (cf) and document frequency (df) behave differently, as in this example from the Reuters collection.
25. Table of tf values for Exercise 6.2.2.
26. Euclidean normalized tf values for documents in Figure 6.9 .
27. The basic algorithm for computing vector space scores.
28. Pivoted document length normalization.
29. Implementing pivoted document length normalization by linear scaling.
30. A faster algorithm for vector space scores.
31. Cluster pruning.
32. Precision/recall graph.
33. The ROC curve corresponding to the precision-recall curve in Figure 8.2 .
34. The Rocchio optimal query for separating relevant and nonrelevant documents.
35. An XML document.
36. The XML document in Figure 10.1 as a simplified DOM object.
37. An XML query in NEXI format and its partial representation as a tree.
38. Tree representation of XML documents and queries.
39. Partitioning an XML document into non-overlapping indexing units.
40. Schema heterogeneity: intervening nodes and mismatched names.
41. A structural mismatch between two queries and a document.
42. A mapping of an XML document (left) to a set of lexicalized subtrees (right).
43. The algorithm for scoring documents with SIMNOMERGE.
44. Scoring of a query with one structural term in SIMNOMERGE.
45. Simplified schema of the documents in the INEX collection.
46. Partial specification of two unigram language models.
47. Three ways of developing the language modeling approach: (a) query likelihood, (b) document likelihood, and (c) model comparison.
48. Classes, training set, and test set in text classification .
49. Naive Bayes algorithm (multinomial model): Training and testing.
50. The multinomial NB model.
51. The Bernoulli NB model.
52. Basic feature selection algorithm for selecting the $\ktopk$ best features.
53. Features with high mutual information scores for six Reuters-RCV1 classes.
54. Effect of feature set size on accuracy for multinomial and Bernoulli models.
55. A sample document from the Reuters-21578 collection.
56. Vector space classification into three classes.
57. Rocchio classification.
58. Rocchio classification: Training and testing.
59. There are an infinite number of hyperplanes that separate two linearly separable classes.
60. Linear classification algorithm.
61. A nonlinear problem.
62. $J$ hyperplanes do not divide space into $J$ disjoint regions.
63. A simple non-separable set of points.
64. The support vectors are the 5 points right up against the margin of the classifier.
65. The geometric margin of a point ($r$) and a decision boundary ($\rho$).
66. A tiny 3 data point training set for an SVM.
67. Large margin classification with slack variables.
68. Projecting data that is not linearly separable into a higher dimensional space can make it linearly separable.
69. An example of a data set with a clear cluster structure.
70. A simple, but inefficient HAC algorithm.
71. The documents of Example 18.4 reduced to two dimensions in $(V^\prime )^T$.
72. Documents for Exercise 18.5.
73. Glossary for Exercise 18.5.
74. Two nodes of the web graph joined by a link.
75. Cloaking as used by spammers.
76. The various components of a web search engine.
77. Two sets $S_{j_1}$ and $S_{j_2}$; their Jaccard coefficient is $2/5$.
78. The basic crawler architecture.
79. Distributing the basic crawl architecture.
80. Example of an auxiliary hosts-to-back queues table.
81. A lexicographically ordered set of URLs.
82. A four-row segment of the table of links.
83. The random surfer at node A proceeds with probability 1/3 to each of B, C and D.
84. A simple Markov chain with three states; the numbers on the links indicate the transition probabilities.
85. The sequence of probability vectors.
86. A sample run of HITS on the query japan elementary schools.
87. Web graph for Exercise 21.3.1 .