PaperlayerView exact revision on arXiv

Source-linked AI summary

STABLE: Efficient Hybrid Nearest Neighbor Search via Magnitude-Uniformity and Cardinality-Robustness

Qianyun Yang, Zhiwei Chen, Yupeng Hu, Zixu Li, Zhiheng Fu, Liqiang Nie

arXiv:2604.01617v1cs.IR

TL;DR

Hybrid ANNS must jointly handle feature similarity and exact attribute constraints, but existing methods overlook heterogeneous similarity magnitudes and changing attribute cardinalities. STABLE addresses these issues with AUTO, HELP, and Dynamic Heterogeneity Routing. Experiments across five feature-vector benchmarks report superior accuracy, efficiency, and robustness, while the framework remains limited in semantic understanding of attribute values and complex compound logic.

  • Problem

    Existing hybrid ANNS methods overlook heterogeneous data distributions, creating challenges in balancing feature similarity with attribute consistency and tolerating changing attribute cardinalities.

  • Method

    STABLE combines the statistically adaptive AUTO metric, the HELP heterogeneous semantic relation graph, and Dynamic Heterogeneity Routing for hybrid ANNS.

  • Results

    Experiments on five feature-vector benchmarks with varied attribute cardinalities demonstrate STABLE’s superior search accuracy, computational efficiency, and robustness.

  • Takeaways & Limitations

    STABLE provides a heterogeneity-aware framework for organizing and navigating hybrid search under varied feature and attribute distributions.

  • Takeaways & Limitations

    STABLE has coarse-grained attribute semantics and constrained expressiveness for complex compound logical queries.

Abstract

from arXiv · show

Hybrid Approximate Nearest Neighbor Search (Hybrid ANNS) is a foundational search technology for large-scale heterogeneous data and has gained significant attention in both academia and industry. However, current approaches overlook the heterogeneity in data distribution, thus ignoring two major challenges: the Compatibility Barrier for Similarity Magnitude Heterogeneity and the Tolerance Bottleneck to Attribute Cardinality. To overcome these issues, we propose the robuSt heTerogeneity-Aware hyBrid retrievaL framEwork, STABLE, designed for accurate, efficient, and robust hybrid ANNS under datasets with various distributions. Specifically, we introduce an enhAnced heterogeneoUs semanTic perceptiOn (AUTO) metric to achieve a joint measurement of feature similarity and attribute consistency, addressing similarity magnitude heterogeneity and improving robustness to datasets with various attribute cardinalities. Thereafter, we construct our Heterogeneous sEmantic reLation graPh (HELP) index based on AUTO to organize heterogeneous semantic relations. Finally, we employ a novel Dynamic Heterogeneity Routing method to ensure an efficient search. Extensive experiments on five feature vector benchmarks with various attribute cardinalities demonstrate the superior performance of STABLE.

I. INTRODUCTION

Hybrid ANNS extends feature-based nearest-neighbor search with structured-attribute constraints, but existing methods struggle with heterogeneous similarity magnitudes and changing attribute cardinalities. STABLE addresses these challenges with AUTO, HELP, and Dynamic Heterogeneity Routing, and experiments across five feature-vector datasets report improved accuracy, efficiency, and robustness.

  • Motivation: Conventional ANNS retrieves similar feature vectors efficiently but cannot simultaneously enforce structured-attribute constraints for targeted retrieval.Hybrid ANNS combines feature retrieval with attribute filtering, supporting scenarios such as product search by image, brand, color, style, or material.
  • Challenges: Existing hybrid ANNS methods face a Compatibility Barrier from mismatched feature-similarity and attribute-consistency magnitudes, limiting collaborative semantic evaluation.The introduction identifies heterogeneous data distributions as a central source of difficulty for current approaches.
  • Challenges: Attribute-cardinality changes create a Tolerance Bottleneck because state-of-the-art methods degrade markedly as the number of distinct attributes varies.The paper frames robustness to changing attribute cardinalities as a critical unresolved challenge.
  • STABLE: STABLE uses the AUTO metric to reconcile feature similarity and attribute consistency, then builds the HELP index and applies Dynamic Heterogeneity Routing for efficient, robust search.AUTO incorporates dataset statistics for automatic adjustment; HELP organizes heterogeneous semantic relations while pruning redundant connections.
  • Evaluation: Experiments on five feature-vector datasets with varied attribute cardinalities report STABLE’s superiority across search accuracy, computational efficiency, and robustness.The paper also presents systematic investigation of search robustness under attribute-cardinality variation as a contribution.

B. Hybrid ANNS

Hybrid ANNS searches for feature-similar items that also satisfy exact attribute constraints, while existing pruning strategies trade off efficiency, recall, memory, or robustness. STABLE combines statistically calibrated semantic measurement with graph-based organization and dynamic routing to address these limitations.

  • Existing Strategies: Disjoint pruning separates attribute filtering from vector search: pre-filtering is costly on large subsets, while post-filtering depends critically on estimating the search depth K′.Insufficient K′ reduces valid-result recall, whereas excessive K′ harms efficiency.
  • Existing Strategies: Joint-pruning methods organize indices around scalar or vector information, but scalar-centric approaches can incur high memory costs and vector-centric methods face magnitude-heterogeneity and robustness challenges.The cited methods include partitioned or attribute-specific graphs, fusion spaces, and predicate-subgraph traversal.
  • STABLE: STABLE introduces AUTO, HELP, and Dynamic Heterogeneity Routing to adaptively balance heterogeneous semantics, organize cross-attribute relations, and navigate efficiently.Its routing uses a dynamic pioneer set and a coarse-to-fine strategy to escape local optima in heterogeneous spaces.
  • Hybrid ANNS: Hybrid ANNS retrieves feature-near data nodes while requiring exact agreement with the query’s attribute constraints.The paper focuses on the Attribute-Equality scenario, where both feature proximity and attribute congruence must hold.
  • AUTO: AUTO redefines distance by jointly measuring feature similarity and attribute consistency after mapping attribute values into numerical vectors.The mapping supports numerical and categorical attribute types while preserving full-match evaluation.

2) Calculation of the AUTO Metric:

AUTO fuses feature similarity and attribute consistency into a joint distance, using Manhattan attribute distance and Euclidean feature distance. Its adaptive trade-off parameter accommodates heterogeneous data distributions and similarity magnitudes.

  • AUTO combines feature similarity and attribute consistency to measure similarity between data nodes.
  • Manhattan distance quantifies attribute inconsistency, while Euclidean distance measures feature-vector similarity.
  • The metric weights feature distance by attribute consistency rather than simply summing them, preventing either magnitude from dominating.
  • A smaller AUTO value indicates greater similarity between a data node and the query.
  • α is calibrated from sampled average feature and attribute distances and dataset statistics to accommodate diverse distributions.

3) Rationale Analysis and Justification:

The rationale analysis presents AUTO as a soft alternative to hard attribute filtering and explains how its scaling preserves useful heterogeneous connections. It also contrasts AUTO with static summation and standard normalization.

  • Soft attribute penalties preserve navigational paths that hard filtering could sever into isolated subgraphs.
  • AUTO selects a mismatched node only when its feature similarity exceeds that of a matching node by the attribute-dependent factor 1 + λ.
  • Within an attribute-uniform subspace, AUTO reduces to a scaled Euclidean distance and preserves the triangle inequality.
  • Across differing attributes, AUTO relaxes the triangle inequality to enable traversal between subspaces and preserve bridge nodes.
  • α is derived from feature-space density and attribute-space scale as an objective, dataset-dependent alignment factor.
  • Unlike static summation or Min-Max normalization, AUTO dynamically compensates for unequal metric scales and skewed distance distributions.

C. Heterogeneous Semantic Relation Graph (HELP)

HELP organizes AUTO-based heterogeneous semantic relations into a navigable graph through iterative neighbor updates and semantic pruning. Its construction preserves bridge connections and protects graph connectivity while reducing redundant edges.

  • HELP is an AUTO-based graph index designed to organize heterogeneous semantic relations for efficient hybrid ANNS.
  • Initialization and iterative updates: Construction initializes random neighbors, then iteratively updates approximate-semantic and reverse-neighbor relations.
  • Initialization and iterative updates: Bidirectional insertion updates neighbor sets while limiting each node to at most Γ neighbors.
  • Initialization and iterative updates: Iterations monitor graph quality ψ against threshold Ψ=0.8 and stop when the target quality is reached.
  • Heterogeneous semantic pruning: Heterogeneous semantic pruning removes redundant same-attribute connections while retaining connections across varying attributes.
  • Heterogeneous semantic pruning: In-degree checks prevent pruning the sole incoming edge of a node, avoiding isolated graph islands.
  • Heterogeneous semantic pruning: HELP preserves high-feature-similarity bridge nodes across attribute clusters, improving navigability under non-uniform attribute distributions.

D. Dynamic Heterogeneity Routing

Dynamic Heterogeneity Routing accelerates hybrid ANNS through coarse exploration followed by greedy refinement. Its pioneer set skips part of the graph path, reducing search complexity while retaining top-K retrieval.

  • Routing Procedure: The overall procedure combines initialization, dynamic coarse routing, and greedy refinement routing.Algorithm 3 summarizes these three operations.
  • Initialization: The routing procedure initializes a result set R with K randomly selected nodes and a pioneer set P containing the closest initial nodes to query Q.R stores candidate top-K results, while P supplies seed nodes for routing.
  • Dynamic Coarse Routing: Dynamic Coarse Routing inspects half of each pioneer node’s neighbors to rapidly identify more promising seed nodes.Candidates more similar to Q than the least similar pioneer are inserted into R and P in sorted order.
  • Greedy Refinement Routing: Greedy Refinement Routing evaluates all neighbors of nodes in R and inserts neighbors that are more similar to Q until the remaining nodes form the top-K results.This stage follows coarse routing and performs precise convergence.
  • Efficiency: Routing achieves search complexity O(Γ(log N −lP)), where lP is the path length skipped by the pioneer set.The paper contrasts this dynamic strategy with redundant computations in NHQ and backtracking-induced degradation in ACORN under high attribute cardinality.

E. Extension to Subset Attribute Queries

STABLE extends hybrid ANNS to subset queries and incomplete data through a masking mechanism. The mask causes unspecified or missing attributes to be ignored without changing the index structure.

  • Masking Mechanism: A mask vector m marks wildcard query attributes and missing data attributes with m_l = 0.The same mechanism represents unspecified query dimensions and absent node values.
  • Masked Evaluation: STABLE adapts attribute consistency using the mask so unspecified or missing attributes do not affect evaluation.This supports subset queries and incomplete attribute data within the existing index.
  • Practical Adaptability: A single unified index supports flexible queries and incomplete data, demonstrating practical adaptability compared with partition-based methods.

IV. EXPERIMENTS AND EVALUATION

The evaluation examines STABLE’s retrieval performance, robustness, module effectiveness, index construction, parameter choices, hyperparameters, and SIMD compatibility. These experiments are organized around seven research questions.

  • RQ1: The experiments evaluate whether STABLE improves Recall@10 and QPS over state-of-the-art competitors.
  • RQ2: The study tests robustness to changes in data volume, attribute cardinality, and query selectivity.
  • RQ3–RQ7: Additional questions examine major modules, index construction, AUTO’s α computation, hyperparameter effects, index size, and SIMD acceleration.

A. Experimental settings

The experiments use benchmark feature-vector datasets at 1M and 10M scales, augmented with attribute constraints of varying cardinality. They compare STABLE with several hybrid ANNS baselines using QPS, Recall@10, and build time.

  • Dataset Construction: Attribute constraints produce nine 1M-scale and six 10M-scale datasets across three attribute-cardinality levels.
  • Dataset Statistics: Table III reports feature-vector dimension M, attribute-vector dimension L, node number N, and attribute cardinality Θ.
  • Attribute Cardinality: For CRAWL-5-3, five attribute dimensions with three labels each yield cardinality Θ = 3^5 = 243.
  • Baselines: The comparisons include STABLE, UNG, ACORN, StitchedVamana, FilteredVamana, Milvus, NHQ-K, NHQ-N, and Vearch.
  • Evaluation Metrics: Figure 3 compares hybrid ANNS methods using Recall@10 on the x-axis and QPS on the y-axis across nine 1M-scale datasets.
  • Implementation Setup: Average build time in seconds measures index-construction efficiency, while K is set to 10 for retrieval evaluation.

B. Retrieval Performance Comparison (RQ1)

STABLE is evaluated against hybrid ANNS baselines using QPS–Recall@10 comparisons across 1M- and 10M-scale datasets. The reported results indicate stronger retrieval performance and later degradation as attribute cardinality increases.

  • STABLE is compared with seven baseline methods on 1M-scale datasets using QPS versus Recall@10 curves.The evaluation covers nine datasets and jointly examines retrieval accuracy and efficiency.
  • Figure 4 compares QPS and Recall@10 for hybrid ANNS methods across six 10M-scale datasets.
  • STABLE, UNG, ACORN, StitchedVamana, and FilteredVamana achieve higher Recall@10 and QPS than the other five baselines in the reported comparisons.The cited passage attributes the advantage of the semantic connection index and entry-node routing for the relevant methods.
  • STABLE’s performance bottleneck occurs later than competing methods as attribute cardinality increases, indicating more robust retrieval across larger Θ values.The comparison links earlier bottlenecks in other methods to faster degradation of semantic comprehension.

C. Analysis on Robustness for Data Volume and Attribute Cardinality (RQ2)

STABLE is tested for robustness to dataset scale, attribute cardinality, query selectivity, and component removal. It maintains high recall across cardinalities and filter settings, while ablations reveal the roles of AUTO, pruning, and dynamic routing.

  • Attribute cardinality: At fixed QPS=3000, STABLE achieves Recall@10 above 0.997 across all evaluated attribute cardinalities.As Θ changes from 3000 to 50, STABLE’s recall declines, but it remains higher than the reported baselines.
  • Attribute cardinality: STABLE maintains Recall@10=1.0000 until Θ=1000, and its recall decreases by only 0.00298 when Θ reaches 50.
  • Query selectivity: Across filter settings, STABLE consistently maintains Recall@10 near 1.0, including high-selectivity queries.The reported explanation is that AUTO heavily penalizes attribute mismatches, functioning as an effective hard constraint mechanism.
  • Ablation analysis: Removing AttributeDis or FeatureDis prevents correct retrieval, with w/o AttributeDis reaching a highest recall of only 0.022 on SIFT-7-3.
  • Ablation analysis: Removing AUTO provides little improvement because feature distance can be hundreds of times larger than attribute distance on SIFT-7-3.
  • Ablation analysis: Removing Heterogeneous Semantic Prune or dynamic routing reduces retrieval performance or routing efficiency in the reported ablations.The w/o DCR variant also performs worse because routing degenerates into a traditional greedy algorithm.

E. Analysis on Index Construction Time (RQ4)

The paper compares average index build time across nine datasets grouped into three categories and examines how AUTO’s parameter calibration behaves across heterogeneous distributions. The reported results emphasize efficient construction and distribution-adaptive α values.

  • Index construction time: Average index build time is measured for STABLE and baselines across nine datasets grouped into three categories.
  • Index construction time: UNG achieves the best index-construction efficiency, while STABLE, ACORN, FilteredVamana, and StitchedVamana also show high construction efficiency.
  • Index construction time: STABLE maintains robust retrieval performance across datasets while providing high index-construction efficiency.The conclusion follows the reported construction-efficiency comparison and retrieval analyses.
  • α calculation: AUTO’s α is calibrated from sampled average feature distance and attribute consistency before index construction.The calibration uses 1,000 randomly sampled nodes and dataset statistics.
  • α calculation: The empirically optimal α varies from 0.8 on SIFT to 1.6 on CRAWL, while the calculated values align with optimal performance peaks across nine scenarios.

G. Parameter Sensitivity Analysis (RQ6)

The sensitivity analysis examines pruning threshold σ, maximum neighbors Γ, SIMD acceleration, and throughput. Results identify a stable σ range, a non-monotonic index-size trade-off, and substantial AVX2 speedup with low overhead relative to Pure L2.

  • Pruning threshold σ: When σ<0.4, valid semantic connections are pruned, while σ>0.6 creates redundant edges and can reduce recall below 0.99 on CRAWL at σ=0.8.
  • Pruning threshold σ: Recall@10 is stable within σ∈[0.4,0.5], with fine-grained fluctuations below 0.1%.STABLE therefore adopts σ within this interval across diverse data distributions.
  • Maximum neighbors Γ: Increasing Γ enlarges the index while retrieval performance first improves and then declines.The analysis attributes the trend to poor connectivity at small Γ and excessive index size at large Γ.
  • SIMD optimization: Enabling AVX2 produces a 2.32× STABLE speedup, while STABLE’s QPS overhead relative to Pure L2 is only 4.4%.The throughput comparison fixes Recall@10=0.999 on SIFT-7-3.
  • Efficiency: STABLE maintains robust retrieval capabilities with low latency for large-scale deployment.
Loading 2604.01617v1…