Efficient metric indexing for similarity search
Authors:
Open Access
- 1 April 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 591-602
Abstract
The goal in similarity search is to find objects similar to a specified query object given a certain similarity criterion. Although useful in many areas, such as multimedia retrieval, pattern recognition, and computational biology, to name but a few, similarity search is not yet supported well by commercial DBMS. This may be due to the complex data types involved and the needs for flexible similarity criteria seen in real applications. We propose an efficient disk-based metric access method, the Space-filling curve and Pivot-based B+-tree (SPB-tree), to support a wide range of data types and similarity metrics. The SPB-tree uses a small set of so-called pivots to reduce significantly the number of distance computations, uses a space-filling curve to cluster the data into compact regions, thus improving storage efficiency, and utilizes a B+-tree with minimum bounding box information as the underlying index. The SPB-tree also employs a separate random access file to efficiently manage a large and complex data. By design, it is easy to integrate the SPB-tree into an existing DBMS. We present efficient similarity search algorithms and corresponding cost models based on the SPB-tree. Extensive experiments using real and synthetic data show that the SPB-tree has much lower construction cost, smaller storage size, and can support more efficient similarity queries with high accuracy cost models than is the case for competing techniques. Moreover, the SPB-tree scales sublinearly with growing dataset size.Keywords
This publication has 30 references indexed in Scilit:
- Extreme Pivots for Faster Metric Indexes2013
- Fully dynamic metric access methods based on hyperplane partitioningInformation Systems, 2011
- Metric Index: An efficient and scalable solution for precise and approximate similarity searchInformation Systems, 2011
- Dynamic Spatial Approximation Trees for Massive Data2009
- Reference-based indexing for metric spaces with costly distance measuresThe VLDB Journal, 2007
- Reverse Nearest Neighbor Search in Metric SpacesIEEE Transactions on Knowledge and Data Engineering, 2006
- Pivot selection techniques for proximity searching in metric spacesPattern Recognition Letters, 2003
- Monotonous Bisector* Trees — a tool for efficient partitioning of complex scenes of geometric objects1992
- Satisfying general proximity / similarity queries with metric treesInformation Processing Letters, 1991
- An algorithm for finding nearest neighbours in (approximately) constant average timePattern Recognition Letters, 1986