Abstract
High-dimensional indexing is a critical challenge in multimedia retrieval. While linear scan strategies like the VA-file remain efficient in high dimensions, they often require exhaustive data access. This paper presents a novel indexing structure based on an extended $B^+$-tree that maps high-dimensional data into two one-dimensional metrics: projections onto the first Principal Component (PC) and distances to a reference point. By leveraging these mappings alongside Partial Distortion Searching and the triangle inequality, the proposed method significantly prunes the search space, achieving up to a 10x I/O speedup over existing methods like iDistance.
Introduction
In multimedia retrieval, data is typically represented as high-dimensional vectors. Traditional spatial indexing structures, such as R-trees, often fail due to the "curse of dimensionality," where the search process degenerates into a slow, random-access linear scan. While sequential linear scans can be faster than random disk seeks, they still necessitate reading the entire dataset. The goal of this research is to develop a "partial linear scan" that maintains the efficiency of sequential access while reducing the volume of data read.
Methodology
The proposed approach transforms the high-dimensional search problem into a filtered one-dimensional search using a hybrid indexing structure.
One-Dimensional Mapping and the Extended $B^+$-tree
Data points are mapped to two 1D values:
- Projection: The position of a point $P_i$ on the line defined by the first Principal Component (the axis of maximum variance).
- Distance: The Euclidean distance from $P_i$ to a central reference point $O$ (the dataset center).
These values are stored in an extended $B^+$-tree. The projection value serves as the primary search key for sorting, while the distance to the reference point is embedded directly into the leaf nodes to facilitate rapid filtering during the scan.
Pruning Strategies
When a query $Q$ is executed, the system performs a bidirectional scan starting from $Q$'s projection in the $B^+$-tree. Three primary filters are used to prune candidates:
- Projection Filter: If the 1D distance between the projections of a point and the query exceeds the current $k$-NN radius, the search in that direction is terminated.
- Triangle Inequality Filter: Using the pre-calculated distances to the reference point $O$, the system applies the triangle inequality ($|dist(P_i, O) - dist(Q, O)| \leq dist(P_i, Q)$) to reject points without calculating their full high-dimensional distance.
- Partial Distortion Search (PDS): For points that pass the initial filters, the Euclidean distance is calculated dimension-by-dimension. The process stops as soon as the partial sum exceeds the current $k$-NN threshold.
The combination of these filters ensures that only a small fraction of the dataset requires full distance computation. By sorting along the first PC, the system maximizes the likelihood that points physically near each other in the tree are also near each other in high-dimensional space.
Performance Evaluation
The method was evaluated using two benchmarks: COLHIST (32D color histograms) and LANDSAT (60D texture features).
Key Results
- Filtering Efficiency: For a 10-NN search, the combined filters successfully rejected over 70% of data points in both 32D and 60D spaces.
- I/O and Execution Time: The proposed method (eBVA) demonstrated a 10x improvement in I/O costs compared to iDistance. By prioritizing sequential I/O and reducing computational overhead via PDS, the system significantly outperformed standard VA-files and linear scans in total execution time.
Conclusion
By sorting high-dimensional data along the first Principal Component and embedding secondary distance metrics within a $B^+$-tree, this research provides a robust framework for accelerating nearest-neighbor queries. The approach balances the benefits of sequential disk access with aggressive mathematical pruning, offering a scalable solution for large-scale multimedia retrieval systems.
Summary updated