PaperlayerView exact revision on arXiv

Source-linked AI summary

ACTIVE: A Dynamic Pareto-Frontier-Based Unified Index for Dual-Vector Query

Shengyuan Lin, Shufeng Gong, Zheng Wang, Feng Yao, Shifu Li, Yanfeng Zhang, Ge Yu

arXiv:2610.35751v1cs.DB

TL;DR

Dual-vector retrieval must support query-dependent preferences across two attributes, yet existing Pareto-frontier approaches face construction and update inefficiencies. ACTIVE combines angle-constrained active-range computation with connectivity-loss-driven adaptive repair; experiments report a competitive accuracy-efficiency trade-off and higher update throughput than state-of-the-art baselines.

  • Problem

    Dual-vector retrieval must accommodate query-specific preferences across two attributes, while existing Pareto-frontier approaches have inefficient construction and substantial update overhead.

    Source: §1 · pp. 1–2

  • Method

    ACTIVE uses angle-constrained active-range computation for construction and insertion, and connectivity-loss-driven adaptive repair for updates.

    Source: §1 · p. 2, §8 · p. 12

  • Results

    Experiments across datasets report a strong trade-off between retrieval quality and update throughput, with higher update throughput than state-of-the-art baselines.

    Source: §1 · p. 2, §8 · p. 12

  • Takeaways & Limitations

    ACTIVE supports dynamic updates while maintaining comparable retrieval quality under arbitrary query preferences.

    Source: §8 · p. 12

    ACAR is designed specifically for DVQ with exactly two attribute vectors, and its distance-computation reduction depends on Pareto-angle distribution.

    Source: §4.3 · pp. 5–6

Abstract

from arXiv · show

Existing approximate nearest neighbor search (ANNS) methods generally assume that each entity has a single vector. In many real-world applications, however, an entity is associated with more than one vector, and queries may jointly consider two attributes. With different queries assigning different weights to each attribute, Pareto-frontier-based indices provide an effective solution for dual-vector retrieval by connecting to approximate nearest neighbors under all possible query preferences. However, existing Pareto-frontier-based approaches suffer from substantial inefficiencies in both index construction and dynamic updates, limiting their practical applicability. To address these issues, we propose ACTIVE, a dynamic Pareto-frontier-based DVQ index that supports efficient construction and updates while maintaining high retrieval performance under varying query preferences. It employs angle-constrained active-range computation and connectivity-loss-driven adaptive repair strategies to accelerate node insertion and deletion, respectively. Extensive experiments show that, at comparable (or slightly below) search accuracy, ACTIVE improves insertion throughput by $1.20$--$1.43\times$ over DEG, and deletion throughput by $1.64$--$2.06\times$ over neighbor-reconnection-based repair and by $22.64$--$39.51\times$ over reinsertion-based repair.

1 INTRODUCTION

Dual-vector retrieval must handle query-dependent preferences and dynamic data, while existing Pareto-frontier approaches face costly construction and deletion repair. ACTIVE addresses these challenges with angle-constrained active-range computation and connectivity-loss-driven adaptive repair.

1 INTRODUCTION

  • Dual-vector queries jointly rank entities by two vector attributes whose weights vary with query-specific preferences, while real-world entities are also inserted and deleted.Different preferences can produce different results even for the same image and text query.Source: §1 · p. 1, Figure 1 · p. 1
  • Pareto-frontier indices cover varying preferences, but their active-range computation adds substantial overhead and existing deletion repair remains inefficient.Reinsertion-based repair incurs many distance computations, while directly applying single-vector local repair cannot guarantee Pareto-frontier identification in local neighborhoods.Source: §1 · p. 2
  • ACTIVE combines angle-constrained active-range computation with connectivity-loss-driven adaptive repair to support efficient construction and dynamic updates under varying query preferences.The repair strategy locally repairs approximate Pareto frontiers according to affected nodes’ connectivity degradation.Source: §1 · p. 2
  • ACAR uses Pareto-angle locality to restrict neighbor comparisons under angle constraints, reducing construction overhead while preserving navigation quality across query preferences.Each neighbor is compared only with other neighbors satisfying the angle constraint under the triangle inequality.Source: §1 · p. 2
  • CA-PFR selects historical-frontier, affected-layer, or multi-layer repair according to connectivity degradation, using neighbor overlap to avoid full reinsertion.The approach reduces distance computations and improves update throughput.Source: §1 · p. 2
  • Experiments report higher update throughput than state-of-the-art baselines while ACTIVE maintains a competitive trade-off between query accuracy and efficiency.The reported comparisons cover diverse datasets.Source: §1 · p. 2

2 BACKGROUND AND MOTIVATION

The background defines dual-vector queries and explains why preference-agnostic Pareto-frontier indices suit them. It then reviews the construction and deletion-update costs that motivate ACTIVE.

2 BACKGROUND AND MOTIVATION

  • The section frames dual-vector retrieval as a setting where query preferences vary across two attributes and index updates must accommodate a changing dataset.The background introduces the DVQ problem and reviews Pareto-frontier-based construction and update methods.Source: §2 · p. 2, §2.1 · p. 2

2.1 Dual-Vector Query

  • A dual-vector query retrieves approximate nearest objects using two query vectors and a preference weight, aiming to maximize recall while remaining efficient.A larger α favors the x attribute and a smaller α favors y.Source: §2.1 · pp. 2–3

2.2 Pareto-Frontier-Based Index Construction

  • Pareto-frontier neighbors cover approximate nearest neighbors across preferences, while approximate frontiers avoid the expense of computing exact multi-layer frontiers against every dataset node.Existing active-range computation compares candidate neighbors against retained neighbors and adds substantial construction overhead.Source: §2.2 · p. 3

2.3 Pareto-Frontier-Based Index Updates

  • Deletion repair must restore connectivity around affected nodes; reinsertion incurs global-search overhead, while neighbor reconnection may compromise Pareto-frontier quality.The background notes that efficient deletion repair preserving high index quality remains challenging.Source: §2.3 · pp. 3–4

3 OVERVIEW

ACTIVE combines angle-constrained active-range computation for construction with connectivity-loss-driven adaptive repair for deletion updates. It also supports dual-vector queries through greedy search over edges whose active ranges include the query preference.

3 OVERVIEW

  • ACTIVE accelerates construction with angle-constrained active-range computation and updates with connectivity-loss-driven local repair of affected nodes.Deletion repair selects among historical-Pareto-frontier, affected-layer, and multi-layer methods according to connectivity degradation.Source: §3 · p. 4
  • For each inserted object, ACTIVE searches the current index for candidates, computes active ranges with ACAR, and selects unpruned neighbors for the new node.It adds reverse edges from those neighbors to support reachability in subsequent searches.Source: §3 · p. 4
  • At query time, ACTIVE uses greedy search with candidate and result queues, expanding edges whose active ranges contain the query preference α.The result queue is bounded by ef_search.Source: §3 · p. 4

4 ANGLE-CONSTRAINED ACTIVE RANGE COMPUTATION

ACTIVE reduces active-range computation overhead by using Pareto-angle constraints to limit comparisons among candidate neighbors. Its approach relies on retrieved nodes exhibiting locality in Pareto-angle space, and its acceleration depends on the distribution of those angles.

4 ANGLE-CONSTRAINED ACTIVE RANGE COMPUTATION

  • ACTIVE introduces angle-constrained active-range computation to avoid redundant distance computations during index construction and updates.The existing nested-loop approach compares each candidate against all previously retained nodes, including candidates unlikely to be retrieved together.Source: §4 · p. 4, §4.1 · p. 4

4.1 Pareto Angle

  • At α=0.1, retrieved nodes are concentrated in contiguous Pareto-angle regions, with higher retrieval frequency mainly at cos(φ) ∈ [0.2, 0.4].The observation comes from searches on OI, HM, and CM indices.Source: §4.1 · pp. 4–5

4.2 Active Range Computation Based on Pareto Angle Difference

  • ACAR restricts comparisons to candidate neighbors whose Pareto-angle difference is within a threshold, skipping pruning-range computations for other pairs.For the first Pareto-frontier layer, it uses a forward scan followed by a reverse scan to refine active ranges; remaining layers use the angular threshold to reduce comparisons.Source: §4.2 · p. 5

4.3 Discussion

  • ACAR is designed for dual-vector retrieval; extending it to more than two attribute vectors is substantially more complex.Its comparison reduction also depends on Pareto-angle distribution: concentrated angles can make it degenerate to the baseline, while a more uniform distribution allows greater acceleration.Source: §4.3 · pp. 5–6

5 CONNECTIVITY-LOSS-DRIVEN INCREMENTAL PARETO FRONTIER REPAIR

CA-PFR repairs affected nodes locally, scaling repair intensity to connectivity loss rather than reinserting nodes through a global search. Its three strategies use progressively broader Pareto-frontier neighborhoods as connectivity degradation increases.

5.1 Observation & Intuition

  • At least 72% of original out-neighbors remain after reinsertion, with 87% preserved in low layers versus 52% in high layers.The overlap supports incremental repair and selective updates across layers.Source: §5.1 · p. 6, Figure 7 · p. 6

5.2 Pareto Frontier Repair Based on Connectivity Loss

  • CA-PFR selects historical-frontier, affected-layer, or multi-layer repair according to whether connectivity loss is mild, moderate, or severe.For mild loss, it reuses active in-neighbors; moderate loss expands candidates from affected layers, while severe loss expands across high layers.Source: §5.2 · pp. 6–7
  • For severe loss, multi-layer repair also targets connectivity deficiencies inherited from index construction, and can shorten paths in the illustrated example from three hops to two.The example triggers multi-layer repair at CL(v7) = 3/4, above CL2 = 1/2.Source: §5.2 · p. 7
  • After 30 batches of deletions, graph connectivity does not degrade; instead, the number of nodes with connectivity loss below CL2 decreases by 3.82×.Source: §5.2 · p. 7

5.3 Computational Overhead Analysis

  • Candidate-repair cost is O(|ΔC|); mild repair adds no distance computations, while moderate and severe repair scale approximately as O(n·R) and O(h·n·R).Severe repair is triggered infrequently, and the expected complexity is simplified to the moderate-repair term.Source: §5.3 · pp. 7–8

6 EVALUATION

The evaluation compares ACTIVE with static-search and update baselines on real-world dual-vector datasets. In static search, ACTIVE generally improves on multi-index retrieval while remaining comparable to DEG, with dataset and preference-distribution qualifications.

6.1 Experimental Setup

  • Experiments use five real-world datasets, compare ACTIVE with MR and DEG for static search and RBR and NRBR for updates, and measure recall, latency, and update throughput.Caselaw is constructed from text embeddings and court-location metadata; workloads sample query preferences from [0, 1] unless otherwise specified.Source: §6.1 · p. 8

6.2 Static Search

  • At Recall@k = 0.95, ACTIVE’s latency advantage over MR generally grows with k, while latency remains comparable to DEG; at k = 1000, MR/ACTIVE ratios are 2.13–4.63 and DEG/ACTIVE ratios are 0.67–1.29.The evaluation varies k across 10, 100, 500, and 1000.Source: §6.2 · p. 8, Figure 9 · p. 9
  • On HM, ACTIVE incurs higher search latency than DEG because its neighbors are more dispersed in Pareto-angle space, averaging 16.07° versus 8.73° for OI and 10.38° for CM.When θth exceeds π/6, ACTIVE achieves search performance competitive with DEG.Source: §6.2 · p. 9
  • Pareto-frontier indices remain stable across three tested α distributions, whereas MR degrades sharply when α concentrates around 0.5.The distributions favor the second attribute, weight both attributes equally, or favor the first.Source: §6.2 · p. 9, Figure 12 · p. 9

6.3 Update Performance

ACTIVE improves update throughput over the tested baselines while maintaining index quality close to the baselines. The evaluation reports these results for deletions and insertions and examines distance computations, recall, and search latency.

6.4 Index Quality

  • Under deletions, ACTIVE’s Recall@10 gap versus RBR ranges from −1.23% to +0.49% across most datasets, while it improves Recall@10 by 0.21%–2.03% over NRBR.On HM, RBR has higher accuracy but 30.28× slower deletion throughput.Source: §6.4 · p. 9, Figure 13 · p. 10
  • Under insertions, ACTIVE’s Recall@10 gap versus DEG ranges from −0.13% to +0.04%; on the largest dataset, its search latency remains comparable and stable under both update types.The authors conclude that ACAR and CA-PFR improve update performance while keeping index quality comparable to the baselines.Source: §6.4 · pp. 9–10

6.3 Update Performance

  • Deletion throughput improves by 22.64–39.51× over RBR and 1.64–2.06× over NRBR, while insertion throughput improves by 1.20–1.43× over DEG.The reported throughput gaps exceed run-to-run variability; first-batch deletion throughput is lower because the reverse graph must be initialized.Source: §6.3 · p. 9, Figure 13 · p. 10, Figure 14 · p. 10
  • Under 1% deletions, ACTIVE reduces distance computations by 8.72×–38.70× over RBR and 1.70×–2.53× over NRBR; under 1% insertions, it reduces them by 1.23×–1.43× versus DEG.The deletion strategy adapts repair to each affected node’s connectivity loss; ACAR reduces computations during insertion.Source: §6.3 · p. 9, Figure 15 · p. 10

6.5 Update Stability

ACTIVE maintains stable update performance and comparable search accuracy in a 50-step sliding-window evaluation, and has lower query latency than the baselines under concurrent updates. Across batch sizes, it retains throughput and accuracy advantages, with parameter studies supporting its defaults.

6.6 Scalability

  • As batch size grows from 0.1% to 10% of the dataset, all methods gain throughput, and ACTIVE consistently outperforms baselines for both deletions and insertions.ACTIVE’s recall is comparable to RBR under deletions and to DEG under insertions across batch sizes.Source: §6.6 · p. 10

6.7 Parameter Sensitivity

  • On OI, θth = π/18 gives the highest throughput for insertion and deletion, with a small Recall@10 loss relative to larger thresholds.The paper uses π/18 as the default Pareto-angle threshold.Source: §6.7 · p. 10
  • The default CL1 = 1/3 and CL2 = 1/2 setting improves deletion throughput by 10.28% over the highest-recall setting with 0.07% lower Recall@10, and improves Recall@10 by 1.07% over the highest-throughput setting.The authors recommend the defaults as a first choice and suggest workload-specific experiments for fine-tuning.Source: §6.7 · pp. 10–11

6.5 Update Stability

  • Across 50 sliding-window updates that replace the entire index, ACTIVE retains a throughput advantage while all methods remain stable, and its search accuracy is comparable to the baselines.The window advances by 1% of the dataset per update batch.Source: §6.5 · p. 10, Figure 19 · p. 11
  • Under continuous batch updates with 16 query and 16 update threads, ACTIVE achieves lower query latency than the other baselines.The reported trace covers the first 300 seconds; periodic latency drops coincide with brief releases of read–write lock contention.Source: §6.5 · p. 10, Figure 20 · p. 11

6.8 Performance Gain

ACTIVE’s performance gains are supported by component ablations and update-time profiling. The results highlight both the contributions of its repair and active-range methods and the small overhead of reverse-graph maintenance.

6.8 Performance Gain

  • 25.76×, 25.50×, and 18.05× average speedups over RBR followed addition of angle-constrained active-range computation at 0.1%, 1%, and 10% deletion batches, respectively.The preceding connectivity-loss-driven repair and asynchronous reverse graph raised average speedups to 13.85×, 12.77×, and 11.34×, then 19.46×, 14.95×, and 12.27×.Source: §6.8 · p. 11, Figure 24 · p. 12

6.9 Ablation Study

  • The full three-level CA-PFR achieves the best overall throughput–recall trade-off among tested threshold settings after 90 batches of 1% deletions on OI.Mild-only repair has higher throughput but fails to maintain graph connectivity under sustained deletions; compared with Mild/Severe, CA-PFR has 7.51% higher deletion throughput with a 0.03% recall decrease.Source: Figure 25 · p. 12, §6.9 · p. 12
  • Full ACAR consistently achieves a better accuracy-efficiency trade-off than the variant applying angle constraints uniformly to every layer.The comparison tests whether the first Pareto-frontier layer requires special treatment.Source: Figure 25 · p. 12, §6.9 · p. 12

6.10 Profiling Breakdown of Update Time

  • ACTIVE’s speedup on OI and HM under 1% batch updates primarily comes from reduced distance computation, while reverse-graph maintenance adds little overhead.The remaining update-time cost components are comparable to those of the baselines.Source: Figure 26 · p. 12, §6.10 · p. 12

7 RELATED WORK

Related work spans hybrid retrieval and graph-based index updates. For dual-vector queries, existing unified indices accommodate varying preferences but lack efficient updates.

Hybrid Search

  • Hybrid search includes filtered ANNS with structured constraints and multi-vector ANNS that jointly optimizes similarity across vector spaces.These paradigms incorporate structured or multi-view semantic information into traditional ANNS.Source: §7 · p. 12

Dual-Vector Query

  • Dual-vector query methods use preference-specific multi-index approaches or preference-agnostic unified indices; the former loses accuracy under arbitrary preferences, while the latter lacks efficient updates.The cited unified approach offers a better accuracy–efficiency trade-off.Source: §7 · p. 12

Chamfer-based Multi-Vector Retrieval (CMVR)

  • CMVR uses a set-to-set Chamfer similarity and captures finer-grained within-feature semantics, but its retrieval task and similarity measure differ from DVQ.The passage says CMVR methods such as MUVERA cannot be used directly for DVQ.Source: §7 · p. 12

Graph-based Index Updates

  • Single-vector graph indices commonly use incremental construction for insertions and global reinsertion or local neighbor reconnection for deletions.The passage also notes scalable, deterministic parallel batch insertion in ParlayANN.Source: §7 · p. 12

8 CONCLUSION

ACTIVE combines angle-constrained active-range computation for construction and insertions with connectivity-loss-driven adaptive repair for updates, aiming to preserve retrieval quality under arbitrary query preferences. Experiments report a strong retrieval-quality and update-throughput trade-off across datasets.

8 CONCLUSION

  • ACTIVE combines Pareto-angle constraints to reduce distance computations with connectivity-loss-driven repair strategies selected by affected-node connectivity loss.Experiments report a strong retrieval-quality and update-throughput trade-off across datasets.Source: §8 · p. 12

A APPLICABILITY TO OTHER DUAL ATTRIBUTES

Experiments on geo-tagged text and image datasets extend ACTIVE’s evaluation beyond image–text data. Results report retrieval quality close to DEG, stronger than MR at the same latency, and higher update throughput than the tested baselines.

Datasets with Additional Dual Attributes

Static Search Performance

Update Throughput

Search Accuracy under Updates

B ANALYSIS OF AFFECTED NODES

ACTIVE (In) repairs in-neighbors of deleted nodes, and the analysis relates HM's greater Pareto-angle dispersion and weaker cross-attribute neighborhood consistency to its threshold sensitivity.

B ANALYSIS OF AFFECTED NODES

  • ACTIVE (In) achieves higher update throughput and better search accuracy than repairing out-neighbors or both in- and out-neighbors under 1% batch deletions on OI.The method treats deleted nodes' in-neighbors as affected because deletions mainly cause their connectivity loss.Source: Figure 32 · p. 15, B ANALYSIS OF AFFECTED NODES · p. 15
  • HM's 95%-neighbor interval is 55.5° versus OI's 31.0° and CM's 43.0°; mean neighbor-angle differences are 16.07°, 8.73°, and 10.38°, respectively, and small thresholds may exclude useful comparisons.Figure 33 marks the shortest continuous Pareto-angle interval containing 95% of neighbor pairs.Source: Figure 33 · p. 16, B ANALYSIS OF AFFECTED NODES · p. 16
  • HM's 49.99% mean y-rank percentile is near random, versus 38.98% for OI and 32.90% for CM, indicating weaker cross-attribute neighborhood consistency.The analysis uses 10,000 sampled objects per dataset and ranks each object's 100 nearest neighbors in attribute space x by distance in y; lower percentiles indicate stronger consistency.Source: Table 4 · p. 16, B ANALYSIS OF AFFECTED NODES · p. 16

Related papers

Loading 2610.35751v1…