Nearest Neighbor Search:: A Database Perspective (Hardcover, 2005)

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