Introduction / 1: |
High-Dimensional Applications / 1.1: |
Motivations / 1.2: |
The Objectives and Contributions / 1.3: |
Organization of the Monograph / 1.4: |
High-Dimensional Indexing / 2: |
Hierarchical Mu lti-dimensional Indexes / 2.1: |
The R-tree / 2.2.1: |
Use of Larger Fanouts / 2.2.2: |
Use of Bounding Spheres / 2.2.3: |
The kd-tree / 2.2.4: |
Dimensionality Reduction / 2.3: |
Indexing Based on Important Attributes / 2.3.1: |
Dimensionality Reduction Based on Clustering / 2.3.2: |
Mapping from Higher to Lower Dimension / 2.3.3: |
Indexing Based on Single Attribu te Values / 2.3.4: |
Filtering and Refining / 2.4: |
Multi-step Processing / 2.4.1: |
Quantization / 2.4.2: |
Indexing Based on Metric Distance / 2.5: |
Approximate Nearest Neighbor Search / 2.6: |
Summary / 2.7: |
Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Range Search / 3: |
Basic Concept of iMinMax / 3.1: |
Sequential Scan / 3.2.1: |
Indexing Based on Max/Min / 3.2.2: |
Indexing Based on iMax / 3.2.3: |
Preliminary Empirical Study / 3.2.4: |
The iMinMax Method / 3.3: |
Indexing Based on iMinMax / 3.4: |
The iMinMax(?) / 3.5: |
Processing of Range Queries / 3.6: |
iMinMax(?) Search Algorithms / 3.7: |
Point Search Algorithm / 3.7.1: |
Range Search Algorithm / 3.7.2: |
Discu ssion on Update Algorithms / 3.7.3: |
Generating the Index Key / 3.8: |
Performance Study of Window Queries / 3.9: |
Implementation / 4.1: |
Generation of Data Sets and Window Queries / 4.3: |
Experiment Setup / 4.4: |
Effect of the Number of Dimensions / 4.5: |
Effect of Data Size / 4.6: |
Effect of Skewed Data Distributions / 4.7: |
Effect of Buffer Space / 4.8: |
CPU Cost / 4.9: |
Effect of Quantization on Feature Vectors / 4.10: |
Indexing the Relative Distance - An Efficient Approach to KNN Search / 4.12: |
Background and Notations / 5.1: |
The iDistance / 5.3: |
The Big Picture / 5.3.1: |
The Data Structure / 5.3.2: |
KNN Search in iDistance / 5.3.3: |
Selection of Reference Points and Data Space Partitioning / 5.4: |
Space-Based Partitioning / 5.4.1: |
Data-Based Partitioning / 5.4.2: |
Exploiting iDistance in Similarity Joins / 5.5: |
Join Strategies / 5.5.1: |
Similarity Join Strategies Based on iDistance / 5.5.2: |
Similarity Range and Approximate KNN Searches with iMinMax / 5.6: |
A Quick Review of iMinMax(?) / 6.1: |
Approximate KNN Processing with iMinMax / 6.3: |
Qu ality of KNN Answers Using iMinMax / 6.4: |
Accu racy of KNN Search / 6.4.1: |
Bounding Box Vs. Bounding Sphere / 6.4.2: |
Effect of Search Radius / 6.4.3: |
Performance Study of Similarity Queries / 6.5: |
Effect of Search Radius on Query Accuracy / 7.1: |
Effect of Reference Points on Space-Based Partitioning Schemes / 7.4: |
Effect of Reference Points on Cluster-Based Partitioning Schemes / 7.5: |
Comparative Study of iDistance and iMinMax / 7.6: |
Comparative Stu dy of iDistance and A-tree / 7.8: |
Comparative Study of the iDistance and M-tree / 7.9: |
iDistance - A Good Candidate for Main Memory Indexing? / 7.10: |
Conclusions / 7.11: |
Contributions / 8.1: |
Single-Dimensional Attribute Value Based Indexing / 8.2: |
Metric-Based Indexing / 8.3: |
Discussion on Future Work / 8.4: |
References |
Introduction / 1: |
High-Dimensional Applications / 1.1: |
Motivations / 1.2: |
The Objectives and Contributions / 1.3: |
Organization of the Monograph / 1.4: |
High-Dimensional Indexing / 2: |