The Modern Algebra of Information Retrieval (eBook)

Sándor Dominich is the George Pólya Professor of Computer Science, Head of the Information Retrieval Research Group, and Deputy Dean of the Faculty of Information Technology of the University of Pannonia, Veszprém, Hungary. His research interests include retrieval models, formal aspects, foundations, effectiveness measurement, and applications. He authored three books, including „Mathematical Foundations of Information Retrieval" (Springer, 2001) and over seventy research papers. He is a founding co-organiser of the ACM SIGIR MF/IR Workshop series 2000-2005, and ICTIR International Conference 2007 (both together with C.J. van Rijsbergen). He has served as a programme committee member of major Information Retrieval conferences.

Acknowledgments 7
Contents 9
1 Introduction 15
1.1 Information Retrieval 16
1.2 Retrieval Methods 25
1.3 Modern Algebra 27
1.4 Lattice 33
1.5 Importance of Lattices 35
1.6 Lattices in Information Retrieval 36
1.7 Exercises and Problems 40
2 Mathematics Basics 41
2.1 Elements of Mathematical Logic 42
2.2 Elements of Set Theory 46
2.3 Elements of Relations Theory 52
2.4 Exercises and Problems 57
2.5 Bibliography 58
3 Elements of Lattice Theory 59
3.1 Lattice 60
3.2 Lattice and Poset 61
3.3 Duality 62
3.4 Hasse Diagram 62
3.5 Complete, Atomic Lattice 64
3.6 Modular Lattice 65
3.7 Sublattice 67
3.8 Distributive Lattice 67
3.9 Complemented, Orthomodular Lattice 70
3.10 Boolean Algebra 73
3.11 Important Lattices 73
3.12 Exercises and Problems 76
3.13 Bibliography 78
4 Basics of Information Retrieval Technology 79
4.1 Documents 80
4.2 Power Law 80
4.3 Stoplist 85
4.4 Stemming 87
4.5 Inverted File Structure 88
4.6 Term-Document Matrix 90
4.7 General Architecture of a Retrieval System 93
4.8 Elements of Web Retrieval Technology 94
4.9 Measurement of Relevance Effectiveness 101
4.10 Measurement of Search Engine Effectiveness 112
4.11 Exercises and Problems 117
5 Lattice-Based Retrieval Systems 119
5.1 Mooers’ Model 120
5.2 The FaIR System 124
5.3 Galois (Concept) Lattice-Based Models 126
5.4 Properties of the Lattices Applied 131
5.5 Exercises and Problems 137
6 Boolean Retrieval 139
6.1 Boolean Retrieval Method 140
6.2 Technology of Boolean Retrieval 142
6.3 Lattice-Based Boolean Retrieval 143
6.4 Exercises and Problems 146
7 Lattices of Subspaces and Projectors 149
7.1 Metric Space 150
7.2 Complete Metric Space 151
7.3 Linear Space 153
7.4 Subspace of Linear Space 155
7.5 Linear Operator 156
7.6 Banach Space 157
7.7 Hilbert Space 159
7.8 Euclidean Space 160
7.9 Projection Theorem 161
7.10 Projector 163
7.11 Basis of Subspace 165
7.12 Lattice of Subspaces 166
7.13 Exercises and Problems 167
7.14 Bibliography 168
8 Vector Space Retrieval 171
8.1 Introduction 172
8.2 Lattices in Vector Space Retrieval 173
8.3 Calculation of Meaning Using the Hilbert Lattice 179
8.4 Compatibility of Relevance Assessments 181
8.5 Vector Space Retrieval: Lattice-Lattice Mapping 182
8.6 Discussion 187
8.7 Exercises 191
9 Fuzzy Algebra-Based Retrieval 193
9.1 Elements of Tensor Algebra 194
9.2 Similarity Measure and Scalar Product 196
9.3 Latent Semantic Indexing Retrieval 200
9.4 Generalized Vector Space Retrieval 205
9.5 Principle of Invariance 206
9.6 Elements of Fuzzy Set Theory 207
9.7 Retrieval Using Linear Space 210
9.8 Fuzzy Algebra-Based Retrieval Methods 213
9.9 Discussion 221
9.10 Exercises and Problems 226
10 Probabilistic Retrieval 229
10.1 Elements of Probability Theory 230
10.2 Principles of Probabilistic Retrieval 232
10.3 Probabilistic Retrieval Method 234
10.4 Language Model Retrieval Method 238
10.5 Lattice Theoretical Framework for Probabilistic Retrieval 240
10.6 Bayesian Network Retrieval 245
10.7 Exercises 249
11 Web Retrieval and Ranking 251
11.1 Web Graph 252
11.2 Link Structure Analysis 260
11.3 The PageRank Method 263
11.4 The HITS Method 269
11.5 The SALSA Method 274
11.6 The Associative Interaction Method 277
11.7 Combined Methods 284
11.8 Lattice-Based View of Web Ranking 296
11.9 P2P Retrieval 306
11.10 Exercises and Problems 312
Solutions to Exercises and Problems 315
References 321
Index 335