Nearest Neighbor Search A Database Perspective
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 applic
- PDF / 8,280,012 Bytes
- 179 Pages / 432 x 648 pts Page_size
- 46 Downloads / 216 Views
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 A N D 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 HIGHPERFORMANCE 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
^ Springer
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. 9 8 7 6 5 4 3 2 1 springeronline.com
(BS/DH)
Contents
List of Figures List of Tables Preface Acknowledgments Part I
ix xiii xvii xxi
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 3.1 The R+-tree 3.2 The R*-tree 3.3 The Hilbert R-tree
15 15 16 16
4
Static R-tree Variants 4.1 The Packed R-tree 4.2 The Hilbert Packed R-tree
17 18 18
vi
NEAREST NEIGHBOR SEARCH 4.3
The STR Packed R-tree
18
5
Performance Issues
18
6 7
R-trees in Emerging Applications Summary
19 20
8
Further Reading
20
Part II
Nearest Neighbor Search in Spatial and Spatiotemp
Data Loading...
