Fundamentals of Database Indexing and Searching

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.

BasicsDatabase QueriesBasic SettingExact SearchSimilarity SearchJoinErrors Low-Dimensional Index StructuresHashingStatic HashingDynamic HashingLocality Sensitive Hashing (LSH)Multi-Dimensional HashingSpace-Filling Curves Memory-Based Index StructuresIndex StructuresBinary Search Tree (BST)QuadtreeK-D-TreeRange TreeVoronoi DiagramTriesSuffix TreeBitmap Index Disk-Based Index StructuresHierarchical StructuresB-Tree and B+-TreeK-D-B-TreeGeneral FrameworkR-TreeR*-TreeR+-TreeHilbert R-TreeSS-TreeSR-TreeP-TreeBulk-Loading DistancesDistance FunctionsMetric SpacesLp NormQuadratic Form DistanceCosine SimilarityStatistical Distance MeasuresDistances between Sets of ObjectsEarth Mover’s DistanceEdit Distance Distance-Based StructuresTriangular InequalityVP-TreeGH-TreeGNATM-TreeSA-TreeAESALinear AESA (LAESA)AESA for Vector Spaces High-Dimensional SpacesCurse of DimensionalityAnalysis of Search for High-Dimensional DataExpected Nearest Neighbor DistanceExpected Number of Page AccessesCurse of Dimensionality High-Dimensionality StructuresX-TreePyramid TechniqueIMinMaxVA-FileA-TreeIQ-Tree Data Reduction TechniquesDimensionality Reduction TechniquesProperties Useful for Similarity SearchQuality MeasuresEmbeddingSingular Value Decomposition (SVD)Principal Component Analysis (PCA)Multi-Dimensional Scaling (MDS)IsoMapFastMapEmbedding MethodsBounds on Distortion Data Representation TechniquesDiscrete Fourier Transform (DFT)Discrete Cosine Transform (DCT)Discrete Wavelet Transform (DWT)V-Optimal Histogram AppendicesA Memory and Disk AccessesMemory AccessDisksFlash B Distances of Bounding BoxesDistance of a Point from a RectangleDistance of a Point from a SphereDistance of a Sphere from a RectangleDistance of a Sphere from a SphereDistance of a Rectangle from a Rectangle C Vectors and MatricesVector SpacesMatricesProperties of MatricesDimensionality D Probability and StatisticsRandom VariableProbability DistributionStatistical Parameters

Arnab Bhattacharya