Nearest Neighbor Search A Database Perspective SERIES IN COMPUTER SCIENCE Series Editor: Rami G. Melhem University of Pittsburgti Pittsburgli, Pennsylvania DYNAMIC RECONFIGURATION Architectures and Algorithms Ramachandran Vaidyanathan and Jerry L. Trahan ENGINEERING ELECTRONIC NEGOTIATIONS A Guide to Electronic Negotiation Technologies for the Design and Implementation of Next-Generation Electronic Markets—Future Silkroads of eCommerce Michael Strobel HIERARCHICAL SCHEDULING IN PARALLEL AND CLUSTER SYSTEMS Sivarama Dandamudi MOBILE IP Present State and Future Abdul Sakib Mondal NEAREST NEIGHBOR SEARCH A Database Perspective Apostolos N. Papadopoulos and Yannis Manolopoulos OBJECT-ORIENTED DISCRETE-EVENT SIMULATION WITH JAVA A Practical Introduction Jose M. Carrido A PARALLEL ALGORITHM SYNTHESIS PROCEDURE FOR HIGH- PERFORMANCE COMPUTER ARCHITECTURES Ian N. Dunn and Gerard G. L. Meyer PERFORMANCE MODELING OF OPERATING SYSTEMS USING OBJECT-ORIENTED SIMULATION A Practical Introduction Jose M. Garrido POWER AWARE COMPUTING Edited by Robert Graybill and Rami Melhem THE STRUCTURAL THEORY OF PROBABILITY New Ideas from Computer Science on the Ancient Problem of Probability Interpretation Paolo Rocchi Nearest Neighbor Search A Database Perspective Apostolos N. Papadopoulos and Yannis Manolopoulos Department of Informatics Aristotle University Thessaloniki, Greece ^ Sprin ger ISBN 0-387-22963-9 ©2005 Springer Science-H Business Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science-I-Business Media, Inc., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. (BS/DH) 9 8 7 6 5 4 3 21 springeronline.com Contents List of Figures ix List of Tables xiii Preface xvii Acknowledgments xxi Part I Fundamental Issues 1. SPATIAL DATABASE CONCEPTS 3 1 Introduction 3 2 Spatial Query Processing 4 3 Access Methods 6 4 Handling High-Dimensional Data 8 5 Spatial Data Support in Commercial Systems 9 6 Summary 10 7 Further Reading 11 2. THE R-TREE AND VARIATIONS 13 1 Introduction 13 2 The Original R-tree 13 3 Dynamic R-tree Variants 15 3.1 The R+-tree 15 3.2 The R*-tree 16 3.3 The Hilbert R-tree 16 4 Static R-tree Variants 17 4.1 The Packed R-tree 18 4.2 The Hilbert Packed R-tree 18 vi NEAREST NEIGHBOR SEARCH 4.3 The STR Packed R-tree 18 5 Performance Issues 18 6 R-trees in Emerging Applications 19 7 Summary 20 8 Further Reading 20 Part II Nearest Neighbor Search in Spatial and Spatiotemporal Databases 3. NEAREST NEIGHBOR QUERIES 25 1 Introduction 25 2 The Nearest Neighbor Problem 25 3 Applications 27 4 Nearest Neighbor Queries in R-trees 28 5 Nearest Neighbor Queries in Multimedia Applications 31 6 Summary 34 7 Further Reading 34 4. ANALYSIS OF NEAREST NEIGHBOR QUERIES 37 1 Introduction 37 2 Analytical Considerations 38 2.1 Preliminaries 38 2.2 Estimation of dnn and dm 40 2.3 Performance Estimation 42 3 Performance Evaluation 44 3.1 Preliminaries 44 3.2 Experimental Results 45 4 Summary 45 5 Further Reading 47 5. NEAREST NEIGHBOR QUERIES IN MOVING OBJECTS 49 1 Introduction 49 2 Organizing Moving Objects 50 3 Nearest Neighbor Queries 52 3.1 The NNS Algorithm 56 3.1.1 Algorithm NNS-a 57 3.1.2 Algorithm NNS-b 61 3.2 Query Processing with TPR-trees 62 Contents vii 4 Performance Evaluation 66 4.1 Preliminaries 66 4.2 Experimental Results 68 5 Summary 71 6 Further Reading 72 Part III Nearest Neighbor Search with Multiple Resources 6. PARALLEL AND DISTRIBUTED DATABASES 75 1 Introduction 75 2 Multidisk Systems 76 3 Multiprocessor Systems 80 4 Distributed Systems 83 5 Summary 84 6 Further Reading 85 7. MULTIDISK QUERY PROCESSING 87 1 Introduction 87 2 Algorithms 88 2.1 The Branch-and-Bound Algorithm 88 2.2 Full-Parallel Similarity Search 88 2.3 Candidate Reduction Similarity Search 91 2.4 Optimal Similarity Search 97 3 Performance Evaluation 98 3.1 Preliminaries 98 3.2 Experimental Results 102 3.3 Interpretation of Results 105 4 Summary 107 5 Further Reading 108 8. MULTIPROCESSOR QUERY PROCESSING 109 1 Introduction 109 2 Performance Estimation 110 3 Parallel Algorithms 111 3.1 Adapting BB-NNF in Declustered R-trees 111 3.2 The Parallel Nearest Neighbor Finding (P-NNF) Method 113 3.3 When Statistics are not Available 116 viii NEAREST NEIGHBOR SEARCH 3.4 Correctness of P-NNF Algorithms 117 4 Performance Evaluation 117 4.1 Preliminaries 117 4.2 The Cost Model 118 4.3 Experimental Results 120 4.4 Interpretation of Results 122 5 Summary 124 6 Further Reading 125 9. DISTRIBUTED QUERY PROCESSING 127 1 Introduction 127 2 Query Evaluation Strategies 129 2.1 Algorithms 129 2.2 Theoretical Study 130 2.3 Analytical Comparison 139 3 The Impact of Derived Data 142 4 Performance Evaluation 146 4.1 Preliminaries 146 4.2 Cost Model Evaluation 146 4.3 Experimental Results 147 5 Discussion 150 6 Summary 151 7 Further Reading 151 Epilogue 153 References 157 List of Figures 1.1 Examples of spatial datasets. 4 1.2 Examples of range and NN queries in 2-d space. 5 1.3 Examples of spatial join queries. 6 1.4 A set of polygons and their corresponding MBRs. 7 1.5 Filter-refinement query processing. 8 1.6 Intersection and containment queries. 8 1.7 Mapping time series to multidimensional vectors. 9 2.1 An R-tree example. 14 2.2 An R+-tree example. 16 2.3 Examples of space-filling curves in 2-d space. 17 2.4 MBRs of leaf nodes for R-tree, R* -tree and STR packed R-tree. 19 3.1 Examples of 2-NN and 4-NN queries using the L2 norm. 26 3.2 Answering a 3-NN query by using repetitive range queries. 27 3.3 MINDIST and MINMAXDIST betv^-een a point P and two rectangles R\ and R2- 30 3.4 NN search algorithm for R-trees. 31 4.1 Two equivalent query execution plans. 37 4.2 (a): exampleofProposition4.1, (b): example of Propo sition 4.2. 40 4.3 When the query point P coincides with a vertex of the MBR, then the maximum difference {a) between MINDIST and MINMAXDIST is obtained. 42 4.4 Example of an enlarged data page. 43 4.5 Datasets used in the experiments. 44 IX