Speed up linear scan in high-dimensions by sorting one-dimensional projections

Jiangtao Cui, Bin Xiao, Gengdai Liu, Lian JiangInternational Journal of Intelligent Systems and Applications 2011 · DOI

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:

  1. Projection: The position of a point $P_i$ on the line defined by the first Principal Component (the axis of maximum variance).
  2. 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.
Pruning the search space using both projection and distance filters.

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.

The Partial Distortion Search (PDS) algorithm for efficient distance calculation.

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

Abstract

High-dimensional indexing is a pervasive challenge faced in multimedia retrieval. Existing indexing methods applying linear scan strategy, such as VA-file and its variations, are still efficient when the dimensionality is high. In this paper, we propose a new access idea implemented on linear scan based methods to speed up the nearest-neighbor queries. The idea is to map highdimensional points into two kinds of one-dimensional values using projection and distance computation. The projection values on the line determined by the first Principal Component are sorted and indexed using a B + -tree, and the distances of each point to a reference point are also embedded into leaf node of the B + -tree. When performing nearest neighbor search, the Partial Distortion Searching and triangular inequality are employed to prune search space. In the new search algorithm, only a small portion of data points need to be linearly accessed by computing the bounded distance on the one-dimensional line, which can reduce the I/O and processor time dramatically. Experiment results on large image databases show that the new access method provides a faster search speed than existing high-dimensional index methods.
BibTeX
@article{cui2011speed,
  author = {Jiangtao Cui and Bin Xiao and Gengdai Liu and Lian Jiang},
  title = {{Speed up linear scan in high-dimensions by sorting one-dimensional projections}},
  journal = {International Journal of Intelligent Systems and Applications},
  year = {2011},
  doi = {10.5815/ijisa.2011.04.06},
}
Figure