Nearest Neighbor Search:: A Database Perspective

ISBN-13: 9781441935649 / Angielski / Miękka / 2010 / 170 str.

Apostolos N. Papadopoulos

Opis

Modern applications are both data and computationally intensive and require the storage and manipulation of voluminous traditional (alphanumeric) and nontraditional data sets (images, text, geometric objects, time-series). Examples of such emerging application domains are: Geographical Information Systems (GIS), Multimedia Information Systems, CAD/CAM, Time-Series Analysis, Medical Information Sstems, On-Line Analytical Processing (OLAP), and Data Mining. These applications pose diverse requirements with respect to the information and the operations that need to be supported. From the database perspective, new techniques and tools therefore need to be developed towards increased processing efficiency. This monograph explores the way spatial database management systems aim at supporting queries that involve the space characteristics of the underlying data, and discusses query processing techniques for nearest neighbor queries. It provides both basic concepts and state-of-the-art results in spatial databases and parallel processing research, and studies numerous applications of nearest neighbor queries.

Recenzje

From the reviews of the first edition:

"This monograph explores the way spatial database management systems aim at supporting queries that involve the space characteristics of the underlying data, and discusses query processing techniques for nearest neighbor queries. It provides both basic concepts and state-of-the-art results in spatial databases and parallel processing research ... . It is an excellent reference for researchers, postgraduate students and practitioners in computer science concerned with nearest neighbor search and related issues." (Marie Duzí, Zentralblatt MATH, Vol. 1076, 2006)

Spis treści

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