Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010340777 | QA76.9.F5 B43 2015 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Fundamentals of Database Indexing and Searching presents well-known database searching and indexing techniques. It focuses on similarity search queries, showing how to use distance functions to measure the notion of dissimilarity.
After defining database queries and similarity search queries, the book organizes the most common and representative index structures according to their characteristics. The author first describes low-dimensional index structures, memory-based index structures, and hierarchical disk-based index structures. He then outlines useful distance measures and index structures that use the distance information to efficiently solve similarity search queries. Focusing on the difficult dimensionality phenomenon, he also presents several indexing methods that specifically deal with high-dimensional spaces. In addition, the book covers data reduction techniques, including embedding, various data transforms, and histograms.
Through numerous real-world examples, this book explores how to effectively index and search for information in large collections of data. Requiring only a basic computer science background, it is accessible to practitioners and advanced undergraduate students.
Table of Contents
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 |