Fundamentals of Database Indexing and Searching

Part I: Foundations Database Queries Basic Model of a Database Point Query Extended Model of a Database Similarity Search Queries Accuracy of Queries Memory and Disk Accesses Memory Access Disks Flash Memory Access Distance Functions Lp Norm Hamming Distance Quadratic Form Distance Statistical Distances Spatially Sensitive Distances Distance between Sets of Objects Part II: Low-Dimensional and Memory-Based Index Structures Hashing Index Structures Static Hashing Dynamic Hashing Locality Sensitive Hashing (LSH) Multi-Dimensional Hashing Geometric Hashing Space-Filling Curves Motivation Examples Memory-Based Index Structures Binary Trees Quadtree K-D-Tree Voronoi Diagram Range Tree Trie Suffix Tree Bitmap Index Indexing Extended Objects Interval Tree Segment Tree Priority Search Tree Part III: Disk-Based Index Structures Hierarchical Index Structures B-Tree and B+-Tree K-D-B Tree General Framework Minimum Bounding Rectangle R-Tree R-Tree-Based Structures Minimum Bounding Sphere Minimum Bounding Polygon Curse of Dimensionality Analysis of Search for High-Dimensional Data X-Tree Pyramid Technique Sequential Scan-Based Methods VA-File IQ-Tree Distance-Based Index Structures Motivation VP-Tree GNAT M-Tree Reference-Based Indexing Non-Metric Distances Part IV: Data Reduction Dimensionality Reduction Techniques Motivation and General Idea Distortion and Stress Singular Value Decomposition (SVD) Principal Component Analysis (PCA) Multi-Dimensional Scaling (MDS) FastMap Random Projection Tree Embedding Definition Lipschitz Embedding LLR Embedding Johnson-Lindenstrauss Lemma Non-Linear Dimensionality Reduction Bounds on Distortion for Non-Metric Distances Data Transformation Techniques Corner Transformation Discrete Data Transforms Histogram Part V: Special Topics Aggregation Queries over Multiple Attributes Problem Setting Fagin's Algorithm (FA) Threshold Algorithm (TA) Text, Sequence, and XML Data Trie-Based Structures Document Indexing Indexing Edit Distance Q-Grams XML Indexing Spatial and Spatio-Temporal Data Spatial Joins Temporal Index Structures Spatial Indexing TPR-Tree Appendix A: Probability and Statistics Appendix B: Linear Algebra Appendix C: Vector and Metric Spaces Bibliography Index