E-Book, Englisch, 280 Seiten
Bhattacharya Fundamentals of Database Indexing and Searching
Erscheinungsjahr 2014
ISBN: 978-1-4665-8255-2
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
E-Book, Englisch, 280 Seiten
ISBN: 978-1-4665-8255-2
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
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.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
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
