Pivot Selection Methods Based on Covariance and Correlation for Metric-space Indexing

Kewei Ma, Yuanjun Liu, Honglong Xu, Yue Pang, Fuli Lei, Liu Sheng, Rui Mao, Jiaxin Han2012 · DOI

Abstract

Metric-space indexing is a general method for similarity queries of complex data. The quality of the index tree is a critical factor of the query performance. Bulkloading a metricspace indexing tree can be represented by two recursive steps, pivot selection and data partition, while pivot selection dominants the quality of the index tree. Two heuristics, based on covariance and correlation, for pivot selection are proposed. Empirical results show that their performance is superior or comparable to existing methods.

Introduction

In the era of big data, similarity search—the process of finding objects "close" to a query—is a fundamental operation in fields ranging from bioinformatics to multimedia retrieval. While traditional indexing methods rely on Euclidean coordinates, many complex data types, such as genetic sequences or high-dimensional feature vectors, lack a natural coordinate system.

Metric-space indexing addresses this by utilizing only the distances between objects. A prevalent approach is the Pivot Space Model. This model selects a subset of data points as "pivots" and represents every other object by its distance to these pivots, effectively mapping the data into a coordinate-based vector space. The efficiency of this index is highly sensitive to the choice of pivots; poor selection leads to significant information loss and necessitates expensive linear scans during search operations.

The Pivot Space Model and Indexing Workflow

The process of metric space indexing involves several stages, from the initial metric space to the final search result. The quality of the mapping from the original metric space to a lower-dimensional pivot space is paramount for reducing the computational cost of queries.

Workflow of metric space indexing, illustrating the transition from metric space to pivot space and finally to search results.

As shown in the indexing workflow, pivot selection is a core component that determines how data is partitioned and searched. The goal is to select pivots that capture the maximum amount of information about the data distribution with minimal redundancy.

Proposed Heuristic Methods

This paper proposes two new heuristic methods for pivot selection that leverage statistical properties of the distance matrix rather than simple geometric distance:

Covariance-Based Selection

  1. Initial Pivot: The first pivot is selected as the point with the maximum variance, representing the highest data fluctuation.
  2. Iterative Selection: For subsequent pivots, the covariance between candidate points and existing pivots is calculated.
  3. Optimization: The point that minimizes the "upper limit" of covariance with the current pivot set is chosen. This ensures that each new pivot provides fresh, non-redundant information.

Correlation-Based Selection

  1. Initial Pivot: Similar to the covariance method, it begins with the point of maximum variance.
  2. Optimization: It seeks points with the minimum absolute correlation to existing pivots. Low correlation indicates that two points are "distinguishable" and capture different aspects of the data distribution, optimizing the resulting index tree.

These methods are compared against standard techniques: Farthest-First Traversal (FFT), which picks points at maximum distance from each other, and Principal Component Analysis (PCA).

Experimental Evaluation

The proposed methods were evaluated using the MoBIoS test suite across four diverse datasets: DNA 18-mer fragments (Hamming distance), Protein 6-mer fragments (weighted edit distance), Uniform 8-dimensional vectors (Euclidean distance), and an image dataset (mixed feature vectors). Performance was measured by the average number of distance calculations required per query.

Comparison of distance calculations across four datasets (DNA, Uniform Vector, Protein, and Image) for FFT, PCA, and the proposed Correlation and Covariance methods.

Key Results

  • Biological Data: The Correlation and Covariance methods significantly outperformed FFT and PCA. For DNA fragments, the Correlation method reduced calculations to ~48,729 compared to FFT’s ~53,179.
  • Vector and Image Data: The new methods performed comparably to PCA and were significantly more efficient than FFT.
  • Overall Performance: The Correlation-based method emerged as the most consistent top performer across all data types, effectively acting as a statistical "distance oracle" to structure the index.

Conclusion

The proposed statistical heuristics for pivot selection offer a robust way to improve metric-space indexing, particularly for non-vector spaces like biological sequences. By treating pivots as dimensions and minimizing correlation between them, these methods reduce redundancy and improve search performance. While these methods involve higher computational overhead during index construction compared to FFT, the gains in query efficiency make them highly valuable for large-scale similarity search applications.

Summary updated

Abstract

Metric-space indexing is a general method for similarity queries of complex data. The quality of the index tree is a critical factor of the query performance. Bulkloading a metricspace indexing tree can be represented by two recursive steps, pivot selection and data partition, while pivot selection dominants the quality of the index tree. Two heuristics, based on covariance and correlation, for pivot selection are proposed. Empirical results show that their performance is superior or comparable to existing methods.
BibTeX
@misc{ma2012pivot,
  author = {Kewei Ma and Yuanjun Liu and Honglong Xu and Yue Pang and Fuli Lei and Liu Sheng and Rui Mao and Jiaxin Han},
  title = {{Pivot Selection Methods Based on Covariance and Correlation for Metric-space Indexing}},
  year = {2012},
  doi = {10.2991/citcs.2012.258},
}
Figure