Abstract
Indexing is an effective way to support efficient query processing in large databases. Recently the concept of learned index, which replaces or complements traditional index structures with machine learning models, has been actively explored to reduce storage and search costs. However, accurate and efficient similarity query processing in high-dimensional metric spaces remains to be an open challenge. In this paper, we propose a novel indexing approach called LIMS that uses data clustering, pivot-based data transformation techniques and learned indexes to support efficient similarity query processing in metric spaces. In LIMS, the underlying data is partitioned into clusters such that each cluster follows a relatively uniform data distribution. Data redistribution is achieved by utilizing a small number of pivots for each cluster. Similar data are mapped into compact regions and the mapped values are totally ordinal. Machine learning models are developed to approximate the position of each data record on disk. Efficient algorithms are designed for processing range queries and nearest neighbor queries based on LIMS, and for index maintenance with dynamic updates. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes and state-of-the-art learned indexes.
Introduction
Similarity search—the task of finding objects "close" to a query—is a fundamental operation in modern data science, underpinning applications ranging from image retrieval to protein sequence analysis. These searches typically occur in metric spaces, where objects lack fixed coordinates (like $x, y, z$) and are instead defined by a distance function (e.g., Edit distance or Jaccard similarity) that satisfies the triangle inequality.
Traditional indexing solutions, such as M-trees or R*-trees, face significant challenges. As data dimensionality increases, these tree-based structures often succumb to the "curse of dimensionality," where their performance degrades to that of a brute-force linear scan. While recent "learned indexes" have shown promise by replacing tree traversals with machine learning models to predict data locations, they are primarily designed for 1D data or vector spaces with fixed coordinates. They struggle with the abstract nature of metric spaces where no natural sort order exists.
To bridge this gap, we present LIMS (Learned Index for Metric Spaces), the first learned index designed for exact similarity search in generic metric spaces. LIMS bypasses traditional hurdles by combining data clustering, pivot-based distance transformations, and polynomial regression models.
The LIMS Framework
LIMS employs a three-stage framework to transform abstract metric data into a format suitable for machine learning models.
- Data Clustering: The dataset is first partitioned into clusters using the $k$-center algorithm. This step decomposes complex global data distributions into simpler, local ones. By ensuring each cluster follows a relatively uniform distribution, LIMS makes it significantly easier for subsequent models to learn the data patterns.
- Pivot-based Transformation: Within each cluster, LIMS selects a small set of "pivots" (reference points). It calculates the distance from every data point to these pivots. These distances are then used to map multi-dimensional data into a 1D "LIMS value," creating a total ordering of the data. This transformation is crucial as it provides the ordinality required for learned indexing.
- Rank Prediction Models: Instead of traversing a hierarchical tree, LIMS utilizes simple polynomial regression models to approximate the "rank"—the physical position on disk—of a data record based on its LIMS value. This effectively turns a $O(\log n)$ search into a $O(1)$ function calculation.
Query Processing
LIMS supports both Range Queries and k-Nearest Neighbor (kNN) Queries through specialized algorithms that ensure exact results (no false negatives).
The query process leverages the triangle inequality to prune irrelevant clusters early. For the remaining clusters, LIMS uses an "AreaLocate" strategy. By feeding the query's distance bounds into the rank prediction models, the system can precisely identify the range of disk pages that might contain relevant objects. This targeted scanning minimizes disk I/O, which is the primary bottleneck in large-scale similarity search.
Experimental Evaluation
LIMS was evaluated against a diverse set of benchmarks, including real-world datasets like Color Histogram (32D) and Forest Cover Type (6D), as well as synthetic GaussMix and Skewed datasets. Notably, a Signature dataset of 100,000 strings using Edit distance was used to test performance in non-vector metric spaces.
Key findings include:
- Performance: On the Signature dataset, LIMS outperformed traditional M-trees by approximately 20x.
- Scalability: Unlike coordinate-based learned indexes (e.g., LISA or ZM-index), LIMS maintains high performance in high-dimensional spaces (8D and above).
- Efficiency: LIMS is remarkably lean, with an index size only 1/3 that of an R-tree. Furthermore, it is 15.5x faster to build* than LISA on large datasets, making it highly practical for real-world deployment.
Conclusion
LIMS demonstrates that the efficiency of learned indexing can be successfully extended to abstract metric spaces. By using distances to pivots as a proxy for coordinates and simplifying local distributions through clustering, LIMS achieves significant speedups and storage savings over state-of-the-art methods. Future work includes exploring workload-aware optimizations to further refine the index based on specific query patterns.
Summary updated