Similarity Search The Metric Space Approach ADVANCES IN DATABASE SYSTEMS Series Editor Ahmed K. Elmagarmid Purdue University West Lafayette, IN 47907 Other books in the Series: STREAM DATA MANAGEMENT, Nauman Chaudhry, Kevin Shaw, Mahdi Abdelguerfi, ISBN: 0-387-24393-3 FUZZY DATABASE MODELING WITH XML, Zongmin Ma, ISBN: 0 387 24248-1 MINING SEQUENTIAL PATTERNS FROM LARGE DATA SETS, Wei Wang andJiong Yang; ISBN: 0-387-24246-5 ADVANCED SIGNATURE INDEXING FOR MULTIMEDIA AND WEB APPLICATIONS, Yannis Manolopoulos, Alexandras Nanopoulos, Eleni Tousidou; ISBN: 1-4020-7425-5 ADVANCES IN DIGITAL GOVERNMENT, Technology, Human Factors, and Policy, edited by William J. Mclver, Jr. and Ahmed K. Elmagarmid; ISBN: 1- 4020-7067-5 INFORMATION AND DATABASE QUALITY, Mario Piattini, Coral Calero and Marcela Genero; ISBN: 0-7923- 7599-8 DATA QUALITY, Richard Y. Wang, Mostapha Ziad, Yang W. Lee: ISBN: 0-7923- 7215-8 THE FRACTAL STRUCTURE OF DATA REFERENCE: Applications to the Memory Hierarchy, Bruce McNutt; ISBN: 0-7923-7945-4 SEMANTIC MODELS FOR MULTIMEDIA DATABASE SEARCHING AND BROWSING, Shu-Ching Chen, R.L Kashyap, andArifGhafoor, ISBN: 0-7923- 7888-1 INFORMATION BROKERING ACROSS HETEROGENEOUS DIGITAL DATA: A Metadata-based Approach, Vipul Kashyap, AmitSheth', ISBN: 0-7923-7883-0 DATA DISSEMINATION IN WIRELESS COMPUTING ENVIRONMENTS, Kian-Lee Tan and Beng Chin Ooi\ ISBN: 0-7923-7866-0 MIDDLEWARE NETWORKS: Concept, Design and Deployment of Internet Infrastructure, Michah Lerner, George Vanecek, Nino Vidovic, Dad Vrsalovic; ISBN: 0-7923-7840-7 ADVANCED DATABASE INDEXING, Yannis Manolopoulos, Yannis Theodoridis, VassilisJ. Tsotras; ISBN: 0-7923-7716-8 MULTILEVEL SECURE TRANSACTION PROCESSING, Vijay Atluri, Sushil Jajodia, Binto George ISBN: 0-7923-7702-8 FUZZY LOGIC IN DATA MODELING, Guoqing Chen ISBN: 0-7923-8253-6 INTERCONNECTING HETEROGENEOUS INFORMATION SYSTEMS, A//zman Bouguettaya, Boualem Benatallah, Ahmed Elmagarmid ISBN: 0-7923-8216-1 For a complete listing of books in this series, go to http://www.springeronline.com Similarity Search The Metric Space Approach Pavel Zezula Masaryk University, Czech Republic Giuseppe Amato ISTI-CNR, Italy Vlastislav Dohnal Masaryk University, Czech Republic Michal Batko Masaryk University, Czech Republic Springer Pavel Zezula Masaryk University, Czech Republic Giuseppe Amato ISTI-CNR, Italy Vlastislav Dohnal Masaryk University, Czech Republic Michal Batko Masaryk University, Czech Republic Library of Congress Control Number: 2005933400 ISBN-10: 0-387-29146-6 e-ISBN-10: 0-387-29151-2 ISBN-13: 978-0387-29146-8 e-ISBN-13: 978-0387-29151-2 © 2006 by Springer Science+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 + 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 987654321 SPIN 11552659 e-SPIN 11560609 springeronline.com This book is dedicated to the 10th anniversary of the Faculty of Informatics, Masaryk University in Brno Contents Dedication v Foreword xiii Preface xv Acknowledgments xvii Part I Metric Searching in a Nutshell Overview 3 1. FOUNDATIONS OF METRIC SPACE SEARCHING 5 1 The Distance Searching Problem 6 2 The Metric Space 8 3 Distance Measures 9 3.1 Minkowski Distances 10 3.2 Quadratic Form Distance 11 3.3 Edit Distance 12 3.4 Tree Edit Distance 13 3.5 Jaccard's Coefficient 13 3.6 Hausdorff Distance 14 3.7 Time Complexity 14 4 Similarity Queries 15 4.1 Range Query 15 4.2 Nearest Neighbor Query 16 4.3 Reverse Nearest Neighbor Query 17 4.4 Similarity Join 17 4.5 Combinations of Queries 18 4.6 Complex Similarity Queries 18 viii SIMILARITY SEARCH 5 Basic Partitioning Principles 20 5.1 Ball Partitioning 20 5.2 Generalized Hyperplane Partitioning 21 5.3 Excluded Middle Partitioning 21 5.4 Extensions 21 6 Principles of Similarity Query Execution 22 6.1 Basic Strategies 22 6.2 Incremental Similarity Search 25 7 Policies for Avoiding Distance Computations 26 7.1 Explanatory Example 27 7.2 Object-Pivot Distance Constraint 28 7.3 Range-Pivot Distance Constraint 30 7.4 Pivot-Pivot Distance Constraint 31 7.5 Double-Pivot Distance Constraint 33 7.6 Pivot Filtering 34 8 Metric Space Transformations 35 8.1 Metric Hierarchies 3 6 8.1.1 Lower-Bounding Functions 36 8.2 User-Defined Metric Functions 38 8.2.1 Searching Using Lower-Bounding Functions 38 8.3 Embedding Metric Space 39 8.3.1 Embedding Examples 39 8.3.2 Reducing Dimensionality 40 9 Approximate Similarity Search 41 9.1 Principles 41 9.2 Generic Algorithms 44 9.3 Measures of Performance 46 9.3.1 Improvement in Efficiency 46 9.3.2 Precision and Recall 46 9.3.3 Relative Error on Distances 48 9.3.4 Position Error 49 10 Advanced Issues 50 10.1 Statistics on Metric Datasets 51 10.1.1 Distribution and Density Functions 51 10.1.2 Distance Distribution and Density 52 10.1.3 Homogeneity of Viewpoints 54 10.2 Proximity of Ball Regions 55 10.3 Performance Prediction 58 Contents ix 10.4 Tree Quality Measures 60 10.5 Choosing Reference Points 63 2. SURVEY OF EXISTING APPROACHES 67 1 Ball Partitioning Methods 67 1.1 Burkhard-Keller Tree 68 1.2 Fixed Queries Tree 69 1.3 Fixed Queries Array 70 1.4 Vantage Point Tree 72 1.4.1 Multi-Way Vantage Point Tree 74 1.5 Excluded Middle Vantage Point Forest 75 2 Generalized Hyperplane Partitioning Approaches 76 2.1 Bisector Tree 76 2.2 Generalized Hyperplane Tree 77 3 Exploiting Pre-Computed Distances 78 3.1 AESA 78 3.2 Linear AESA 79 3.3 Other Methods 80 4 Hybrid Indexing Approaches 81 4.1 Multi Vantage Point Tree 81 4.2 Geometric Near-neighbor Access Tree 82 4.3 Spatial Approximation Tree 85 4.4 M-tree 87 4.5 Similarity Hashing 88 5 Approximate Similarity Search 89 5.1 Exploiting Space Transformations 89 5.2 Approximate Nearest Neighbors with BBD Trees 90 5.3 Angle Property Technique 92 5.4 Clustering for Indexing 94 5.5 Vector Quantization Index 95 5.6 Buoy Indexing 97 5.7 Hierarchical Decomposition of Metric Spaces 97 5.7.1 Relative Error Approximation 98 5.7.2 Good Fraction Approximation 98 5.7.3 Small Chance Improvement Approximation 98 5.7.4 Proximity-Based Approximation 99 5.7.5 PAC Nearest Neighbor Search 99 X SIMILARITY SEARCH Part II Metric Searching in Large Collections of Data Overview 103 CEi NTRALIZED INDEX STRUCTURES 105 1 M-tree Family 105 1.1 The M-tree 105 1.2 Bulk-Loading Algorithm of M-tree 109 1.3 Multi-Way Insertion Algorithm 112 1.4 The Slim Tree 113 1.4.1 Slim-Down Algorithm 114 1.4.2 Generalized Slim-Down Algorithm 116 1.5 Pivoting M-tree 118 1.6 The M+-tree 121 1.7 The M^-tree 124 2 Hash-based metric indexing 125 2.1 TheD-index 126 2.1.1 Insertion and Search Strategies 129 2.2 The eD-index 131 2.2.1 Similarity Self-Join Algorithm with eD-index 133 3 Performance Trials 136 3.1 Datasets and Distance Measures 137 3.2 Performance Comparison 138 3.3 Different Query Types 140 3.4 Scalability 141 APPROXIMATE SIMILARITY SEARCH 145 1 Relative Error Approximation 145 2 Good Fraction Approximation 148 3 Small Chance Improvement Approximation 150 4 Proximity-Based Approximation 152 5 PAC Nearest Neighbor Searching 153 6 Performance Trials 154 6.1 Range Queries 155 6.2 Nearest Neighbors Queries 156 6.3 Global Considerations 159