Nearest Neighbor Search:: A Database Perspective Book

List of Figures List of Tables Preface Acknowledgments

Part I Fundamental Issues

1. SPATIAL DATABASE CONCEPTS
1 Introduction
2 Spatial Query Processing
3 Access Methods
4 Handling High-Dimensional Data
5 Spatial Data Support in Commercial Systems
6 Summary
7 Further Reading

2. THE R-TREE AND VARIATIONS
1 Introduction
2 The Original R-tree
3 Dynamic R-tree Variants
3.1 The R+-tree
3.2 The R*-tree
3.3 The Hilbert R-tree
4 Static R-tree Variants
4.1 The Packed R-tree
4.2 The Hilbert Packed R-tree
4.3 The STR Packed R-tree
5. Performance Issues
6. R-trees in Emerging Applications
7. Summary
8. Further Reading

Part II Nearest Neighbor Search in Spatial and Spatiotemporal Databases

3. NEAREST NEIGHBOR QUERIES
1 Introduction
2 The Nearest Neighbor Problem
3 Applications
4 Nearest Neighbor Queries in R-trees
5 Nearest Neighbor Queries in Multimedia Applications
6 Summary
7 Further Reading

4. ANALYSIS OF NEAREST NEIGHBOR QUERIES
1 Introduction
2 Analytical Considerations
2.1 Preliminaries
2.2 Estimation of dnn and dm
2.3 Performance Estimation
3 Performance Evaluation
3.1 Preliminaries
3.2 Experimental Results
4 Summary
5 Further Reading

5. NEAREST NEIGHBOR QUERIES IN MOVING OBJECTS
1 Introduction
2 Organizing Moving Objects
3 Nearest Neighbor Queries
3. 1 The NNS Algorithm
3.1 Algorithm NNS-a
3.1.2 Algorithm NNS-b
3.2 Query Processing with TPR-trees
4 Performance Evaluation
4.1 Preliminaries
4.2 Experimental Results
5 Summary
6 Further Reading

Part III Nearest Neighbor Search with Multiple Resources

6. PARALLEL AND DISTRIBUTED DATABASES
1 Introduction
2 Multidisk Systems
3 Multiprocessor Systems
4 Distributed Systems
5 Summary
6 Further Reading

7 MULTIDISK QUERY PROCESSING
1 Introduction
2 Algorithms
2.1 The Branch-and-Bound Algorithm
2.2 Full-Paral1el Similarity Search
2.3 Candidate Reduction Similarity Search
2.4 Optimal Similarity Search
3 Performance Evaluation
3.1 Preliminaries
3.2 Experimental Results
3.3 Interpretation of Results
4 Summary
5 Further Reading

8. MULTIPROCESSOR QUERY PROCESSING
1 Introduction
2 Performance Estimation
3 Parallel Algorithms
3.1 Adapting BB-NNF in Declustered R-trees
3.2 The Parallel Nearest Neighbor Finding (P-NNF) Method
3.3 When Statistics are not Available
3.4 Correctness of P-NNF Algorithms
4 Performance Evaluation
4.1 Preliminaries
4.2 The Cost Model
4.3 Experimental Results
4.4 Interpretation of Results
5 Summary
6 Further Reading

9. DISTRIBUTED QUERY PROCESSING
1 Introduction
2 Query Evaluation Strategies
2.1 Algorithms
2.2 Theoretical Study
2.3 Analytical Comparison
3 The Impact of Derived Data
4 Performance Evaluation
4.1 Preliminaries
4.2 Cost Model Evaluation
4.3 Experimental Results
5 Discussion
6 Summary
7 Further Reading Epilogue References