Nearest Neighbor Search:: A Database Perspective

229,59 €*

Alle Preise inkl. MwSt.|Versandkostenfrei
ISBN-13:
9780387229638
Veröffentl:
2004
Erscheinungsdatum:
01.11.2004
Seiten:
170
Autor:
Apostolos N. Papadopoulos
Gewicht:
386 g
Format:
236x153x16 mm
Serie:
Computer Science
Sprache:
Englisch
Beschreibung:

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 efficient query processing techniques for nearest neighbor queries from a spatial database perspective. It provides basic concepts and an introduction to spatial databases and parallel processing research, then goes on to discuss numerous applications of nearest neighbor queries, such as query processing in a single-processor multi-disk system environment, and in systems composed of many disks and processors. Enriched by numerous illustrations and pointers for additional research, this book is an excellent reference for students, researchers and professionals interested in nearest neighbor search and related issues.
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

Kunden Rezensionen

Zu diesem Artikel ist noch keine Rezension vorhanden.
Helfen sie anderen Besuchern und verfassen Sie selbst eine Rezension.

Google Plus
Powered by Inooga