|
List of Figures
List of Tables
Preface
Acknowledgments
Part I Fundamental Issues
1. SPATIAL DATABASE CONCEPTS
1.1 Introduction
1.2 Spatial Query Processing
1.3 Access Methods
1.4 Handling High-Dimensional Data
1.5 Spatial Data Support in Commercial Systems
1.6 Summary
1.7 Further Reading
2. THE R-TREE AND VARIATIONS
2.1 Introduction
2.2 The Original R-tree
2.3 Dynamic R-tree Variants
2.3.1 The R+-tree
2.3.2 The R*-tree
2.3.3 The Hilbert R-tree
2.4 Static R-tree Variants
2.4.1 The Packed R-tree
2.4.2 The Hilbert Packed R-tree
2.4.3 The STR Packed R-tree
2.5. Performance Issues
2.6. R-trees in Emerging Applications
2.7. Summary
2.8. Further Reading
Part II Nearest Neighbor Search in Spatial and Spatiotemporal Databases
3. NEAREST NEIGHBOR QUERIES
3.1 Introduction
3.2 The Nearest Neighbor Problem
3.3 Applications
3.4 Nearest Neighbor Queries in R-trees
3.5 Nearest Neighbor Queries in Multimedia Applications
3.6 Summary
3.7 Further Reading
|
4. ANALYSIS OF NEAREST NEIGHBOR QUERIES
4.1 Introduction
4.2 Analytical Considerations
4.2.1 Preliminaries
4.2.2 Estimation of dnn and dm
4.2.3 Performance Estimation
4.3 Performance Evaluation
4.3.1 Preliminaries
4.3.2 Experimental Results
4.4 Summary
4.5 Further Reading
5. NEAREST NEIGHBOR QUERIES IN MOVING OBJECTS
5.1 Introduction
5.2 Organizing Moving Objects
5.3 Nearest Neighbor Queries
5.3.1 The NNS Algorithm
5.3.1.1 Algorithm NNS-a
5.3.1.2 Algorithm NNS-b
5.3.2 Query Processing with TPR-trees
5.4 Performance Evaluation
5.4.1 Preliminaries
5.4.2 Experimental Results
5.5 Summary
5.6 Further Reading
Part III Nearest Neighbor Search with Multiple Resources
6. PARALLEL AND DISTRIBUTED DATABASES
6.1 Introduction
6.2 Multidisk Systems
6.3 Multiprocessor Systems
6.4 Distributed Systems
6.5 Summary
6.6 Further Reading
7 MULTIDISK QUERY PROCESSING
7.1 Introduction
7.2 Algorithms
7.2.1 The Branch-and-Bound Algorithm
7.2.2 Full-Paral1el Similarity Search
|
7.2.3 Candidate Reduction Similarity Search
7.2.4 Optimal Similarity Search
7.3 Performance Evaluation
7.3.1 Preliminaries
7.3.2 Experimental Results
7.3.3 Interpretation of Results
7.4 Summary
7.5 Further Reading
8. MULTIPROCESSOR QUERY PROCESSING
8.1 Introduction
8.2 Performance Estimation
8.3 Parallel Algorithms
8.3.1 Adapting BB-NNF in Declustered R-trees
8.3.2 The Parallel Nearest Neighbor Finding (P-NNF) Method
8.3.3 When Statistics are not Available
8.3.4 Correctness of P-NNF Algorithms
8.4 Performance Evaluation
8.4.1 Preliminaries
8.4.2 The Cost Model
8.4.3 Experimental Results
8.4.4 Interpretation of Results
8.5 Summary
8.6 Further Reading
9. DISTRIBUTED QUERY PROCESSING
9.1 Introduction
9.2 Query Evaluation Strategies
9.2.1 Algorithms
9.2.2 Theoretical Study
9.2.3 Analytical Comparison
9.3 The Impact of Derived Data
9.4 Performance Evaluation
9.4.1 Preliminaries
9.4.2 Cost Model Evaluation
9.4.3 Experimental Results
9.5 Discussion
9.6 Summary
9.7 Further Reading
Epilogue
References
|
