Source-linked AI summary
Fast Approximate Line Nearest Neighbor Search
Jiadong Xie, Jeffrey Xu Yu, Yingfan Liu
TL;DR
Line nearest neighbor search addresses queries that should match content while allowing a specified aspect, such as illumination, to vary. LinePG adds scored pair edges to an existing proximity graph to connect separated near-line regions. It outperforms the compared methods on the reported search-performance and index-cost measures.
Problem
Ordinary point queries do not explicitly express retrieval that preserves content while allowing a specified aspect variation, and existing LANN approaches focus on top-1 search.
Source: §1 · p. 1Method
LinePG augments an existing point-search proximity graph with selected pair edges that connect separated near-line regions and support graph navigation.
Source: §1 · p. 2Results
At Recall@10 of 0.99, LinePG delivers up to 4.23x QPS of DirectSearch and, on full datasets on average, uses 1.86% of Lift’s index space and 2.15% of its construction time.
Source: §9 · p. 13Takeaways & Limitations
LinePG’s selected pair edges provide additional entrances into promising near-line regions while retaining the original vector dimension and total degree limit.
Source: §1 · p. 2, §9 · p. 12Beam search on a conventional proximity graph may stop after finding enough candidates in one region, leaving better points in another undiscovered.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Approximate nearest neighbor (ANN) search, which retrieves vectors close to a given query vector, is a fundamental operation in vector databases. However, emerging applications, such as selecting source images for photo-based animation and video synthesis, may require matching content while allowing a query-specified aspect contrast, such as an illumination change, to vary; a single query point does not directly express this requirement. In this paper, we study approximate line nearest neighbor (LANN) search, where an infinite query line removes the distance contribution along a specified direction while database records remain points. Prior approaches focus on top-$1$ search only for LANN and can incur high construction costs. Converting LANN into ordinary point ANN search through dimension lifting substantially increases index construction and query costs, while direct search on a proximity graph built for ordinary point ANN search can miss distinct regions close to a line. To address these issues, we propose LinePG, which enhances an existing proximity graph with pair edges to facilitate navigation between separated near-line regions. To find these pair edges efficiently, we first generate region pairs with spatial or graph separation, and near a line. We then score edges between the selected region pairs to guide the point endpoint selections. We conduct extensive performance studies and confirm the accuracy and efficiency of LinePG in comparison with the baseline approaches.
1 Introduction
The introduction motivates line nearest neighbor search for queries that should preserve content while allowing a specified aspect to vary. It proposes LinePG, which augments a point-search proximity graph with pair edges to navigate between separated near-line regions.
1 Introduction
- Visual workflows motivate queries that preserve subject and pose while allowing illumination to vary, a requirement ordinary point queries do not explicitly express.The introduction cites photo animation and video creation workflows as examples.Source: §1 · p. 1
- LANN ranks database points by minimum distance to an infinite query line, which removes the distance contribution along the specified direction.A single fixed projection suffices only when all queries share one direction; the paper considers varying directions and offsets.Source: §1 · p. 2
- Prior LANN methods focus on top-1 search and can require construction costs higher than quadratic, while dimension lifting requires Θ(d^2) dimensions.The paper states that the lifted dimension substantially increases index construction and search costs.Source: §1 · p. 2
- LinePG adds pair edges between separated near-line regions, selecting region pairs and scoring endpoints to support navigation without exceeding the graph’s total degree limit.Its search uses selected pair edges as additional entrances while avoiding redundant entrances into regions already being explored.Source: §1 · p. 2
- At 99% recall, LinePG achieves 1.44–4.23x QPS of direct search on the original proximity graph across six real-world datasets.On N=512 subsets at 100% recall, its QPS speedups reach 976.17x over dimension lifting and 1,665.63x over theoretical methods.Source: §1 · p. 2
2 Preliminaries and Problem Statement
The section defines line queries and their distance-based ranking, then places approximate line search alongside conventional point search on proximity graphs. It also describes the graph beam-search procedure used for point ANN.
2 Preliminaries and Problem Statement
- A line query is represented by a unit direction u and a closest-to-origin point a orthogonal to u; its distance to point p is ||H_u(p−a)||.H_u is the orthogonal projector onto the complement of u, and squared line distance is used for ranking.Source: §2 · p. 2
- LANN returns an approximate set of k points closest to the query line, with retrieval quality measured by Recall@k against the exact line neighbors.The exact search is described as expensive.Source: §2 · p. 2
- A proximity graph represents each database point as a node and connects selected nearby points; its degree parameter M controls each node’s out-neighbor list size.Pruning and additional navigation edges can affect the topology, so edges need not be exactly the M nearest neighbors.Source: §2 · p. 2
- Point ANN beam search expands the closest unexpanded candidate, evaluates unseen out-neighbors, retains at most w candidates, and returns the k closest retained points when expansion ends.The search begins from one or more entry nodes, with w ≥ k.Source: §2 · p. 3
3 Limitations of Existing Approaches
The existing LANN approaches described here are limited by top-1 scope and costly construction, by the dimensionality of exact lifting, or by graph navigation that can miss separate near-line regions.
Provable Line ANN Search
- TheoryLP selects dense near-line groups iteratively and uses Projection-DS for residual points, but its cylinder selection examines axes through pairs of active points.The selection work is O(d Σᵢ nᵢ³) as stated in the supplied passage.Source: §3 · p. 3
- TheoryLP targets k=1; its literal cylinder selection has high construction overhead, and its search efficiency remains substantially worse than other approaches despite a k-neighbor extension.It builds dense near-line groups and a sparse residual set, using Cylinder-DS and Projection-DS structures.Source: §3 · p. 3
Direct Search on a Proximity Graph
- Direct search can miss better near-line points when beam search stays in one region and terminates before crossing to another.In the example, all paths between two near-line regions leave the set, and beam search returns three points that are not the line’s 3-NN.Source: §3 · p. 3
Reduction via Quadratic Lifting
- Exact quadratic lifting preserves nearest-neighbor rankings, but requires at least D★ = d(d + 1)/2 + d dimensions in the stated reduction model, increasing storage and search costs.The construction attains this dimension bound on the unit ball; the resulting lifted vectors require Θ(Nd²) storage.Source: §3 · pp. 3–4
4 Line-Enhanced Proximity Graph
LinePG augments a point-ANN proximity graph with pair edges so search can reach separated regions near the same query line. It selects candidate region pairs and endpoints using spatial and graph structure, line proximity, and direction diversity while respecting a degree limit.
4 Line-Enhanced Proximity Graph
- Pair edges address the risk that beam search explores one near-line region and stops before reaching another because the connecting route passes through points farther from the line.Local exploration continues on original graph edges after a pair edge reaches the target region.Source: §4 · p. 4
- Because there are Θ(N^2) potential point pairs, LinePG first groups points into regions and proposes candidate pairs through a spatial hierarchy and quotient-graph topology.The hierarchy proposes spatial alternatives at multiple scales; the quotient graph records how the original graph connects leaves.Source: §4 · pp. 4–5
- A short directed route in the quotient graph can reveal a detour worth shortening, but region pairs still need geometric scoring for separation and proximity to a common line.The hierarchy and quotient graph generate alternatives; the score checks whether they are geometrically suitable.Source: §4 · p. 5
- For each candidate target region, LinePG chooses among representative endpoints using J(p,y;B), which rewards a candidate direction supported by other points in that region.A representative bank combines points nearest the region centroid with a bounded number of farthest distinct points.Source: §4 · p. 5
- Endpoint selection favors directions that add diversity relative to already selected pair edges and original neighbors, then prunes edges as needed to stay within the degree limit.When the pair-edge limit is exceeded, direction-diversity scores guide pair-edge removal; otherwise, the longest original edge may be pruned.Source: §4 · p. 5
5 Hierarchy and Quotient Graph Constructions
The hierarchy recursively partitions points using a split signal smoothed over the original proximity graph, and the quotient graph records connections between the resulting leaves. The section establishes smoothing properties and notes that too many rounds can erase geometric separation.
5 Hierarchy and Quotient Graph Constructions
- Graph smoothing adjusts a vector-derived split signal before balanced recursive partitioning, so the hierarchy reflects point locations and local graph connections.Splitting continues until each leaf contains at most b points; the default is b = 32.Source: §5 · pp. 5–6
- The smoothing update decreases weighted split-signal variation and keeps every new value within the preceding round’s range.The result follows from the update and its convex-combination form.Source: §5 · p. 6
- Smoothing to convergence can erase the initial geometric separation when the induced graph is strongly connected, so the method uses a small number of rounds.The default is t_s = 4.Source: §5 · p. 6
- In the illustrated split, smoothing exchanges the assignments of p11 and p12 and reduces the directed edges crossing the split from nine to four.The example compares a raw median split with the smoothed partition.Source: §5 · p. 6
- The quotient graph is built by scanning original edges and adding one arc for each distinct inter-leaf connection, without rebuilding proximity graphs for individual leaves.Duplicate arcs are removed, and averaging weights are not used as quotient-arc weights.Source: §5 · p. 6
6 Candidate Region Pair Selection
LinePG selects candidate region pairs from spatial alternatives in a hierarchy and destinations lacking short quotient-graph paths, then scores them for separation and support from points near their representative secant.
6 Candidate Region Pair Selection
- For each source, hierarchy and quotient candidates are merged before scoring, and the highest-scoring pairs are converted into point-level edges.The hierarchy supplies spatial alternatives at multiple scales, while quotient sampling targets leaves without short directed routes.Source: §6 · p. 6, §6.1 · p. 7
6.1 Candidate Region Pairs
- Sampling a shared uniform pool before checking κ-hop reachability gives each eligible leaf conditional inclusion probability s/|Fκ(A)| for returned size s.The uniformity averages over both random stages; it does not hold after fixing the pool or after score-based top-r selection.Source: §6.1 · p. 7
- Hierarchy sibling-subtree sampling and quotient-graph sampling generate complementary candidate regions, which are deduplicated and ranked to retain at most r pairs per source.Hierarchy samples leaves along sibling subtrees; quotient candidates exclude destinations reachable within κ hops.Source: §6.1 · pp. 6–7
6.2 Scoring Candidate Regions
- The representative secant is the infinite line through two region centroids, and candidate edges should span beyond local region extent while following a direction supported by their points.The score combines a separation factor relative to local spread with a secant-support factor based on perpendicular deviations.Source: §6.2 · p. 8
- The combined score S(A, B) = g(A, B)h(A, B) favors pairs with both appreciable separation and secant support; neither factor can compensate without limit for the other.Both factors lie in [0, 1], and the product cannot exceed either factor.Source: §6.2 · p. 8
7 Search on the Line-Enhanced Graph
Search on the enhanced graph combines local exploration with conditional probes through pair edges, while suppressing repeated entrances into leaves already being explored.
7 Search on the Line-Enhanced Graph
- Beam search explores original neighbors first and considers pair edges only when the retained frontier offers no closer unexpanded continuation.The candidate pool is ordered by point-to-line distance and capped at beam width w.Source: §7 · p. 8
- Pair-edge endpoints are considered in stored order, while endpoints in already explored leaves are skipped to avoid redundant regional entrances.The algorithm retains at most w candidates and returns the k closest points to the line.Source: §7 · pp. 8–9
8 Experiments
Experiments compare LinePG with graph-search, lifting, theoretical, and brute-force baselines across six real-world datasets. They report faster high-recall search, manageable index overhead, benefits from pair-edge design choices, and throughput at 100M points.
Exp. 1: Search Performance Comparison
- At recall ≥0.99 on full data, LinePG reaches 4.23x DirectSearch QPS on YaleB (k=10); on N=512 subsets it reaches recall 1.0 on all six datasets.The full-data comparison covers Figures 10 and 11; subset QPS also exceeds DirectSearch, Lift, and TheoryLP at the same reported recall.Source: Figure 10 · p. 10, Figure 11 · p. 10, §8 · p. 10
Exp. 2: Index Size and Construction Time
- On full datasets, LinePG uses 1.000–1.046 times DirectSearch storage; its additional GIST construction stages take 255.680 s beyond a 2,271.748 s HNSW build.Pair-edge selection accounts for 73.9–94.5% of the three additional stages, while total construction time is reported as smaller than Lift and TheoryLP.Source: Table 2 · p. 11, §8 · p. 11
Exp. 3: Ablation Studies
- On SIFT, adding pair edges raises maximum recorded recall from 0.9893 for DirectSearch to 0.9993 for LinePG, while pruning versus retaining original edges has no uniformly faster strategy.The ablation also reports that pruning maintains the degree bound without preventing high-recall retrieval.Source: Figure 12 · p. 11, §8 · p. 11
- On SIFT, LinePG is 2.23x faster than normal pair-edge exploration at recall 0.995, but normal exploration is 2.09x faster at its reported 0.999 operating point.LinePG outperforms pair-edge-first and pair-edge-last scheduling; the no-leaf-gate comparison also finds higher QPS at similar recall.Source: Figure 13 · p. 11, §8 · pp. 11–12
- At recall 0.99, LinePG achieves 1.09–2.43x the QPS of pair-selection variants, supporting the combination of hierarchy candidates, quotient candidates, and graph smoothing.The compared variants remove hierarchy-derived pairs, quotient-derived pairs, or smoothing, respectively.Source: Figure 14 · p. 12, §8 · p. 12
Exp. 4: Parameter Sensitivity
- On YaleB at recall 0.99, pair-edge budget M_pair=4 yields 4.23x, 1.98x, and 1.10x the QPS of budgets 1, 2, and 8, respectively.Sensitivity tests also show parameter-dependent query/build tradeoffs for leaf capacity, smoothing, sampling budget, quotient-hop radius, and retained region partners.Source: Figure 15 · p. 12, §8 · p. 12
Exp. 5: Scalability
- On SIFT100M at 100M points, LinePG delivers 394.3 QPS at Recall@10 = 0.95 and 140.8 QPS at Recall@100 = 0.95, with total build time 144.90k s.Index-size curves for HNSW and the enhancements grow nearly linearly with data scale.Source: Figure 16 · p. 12, §8 · p. 12
9 Conclusion
LinePG enhances a proximity graph with selected pair edges while retaining the original vector dimension and total degree limit. It outperforms the compared LANN methods in search performance, index space, and construction time.
9 Conclusion
- LinePG enhances a proximity graph with selected pair edges while retaining the original vector dimension and total degree limit.Source: §9 · p. 12
- At Recall@10 of 0.99, LinePG delivers up to 4.23x QPS of DirectSearch and can reach higher recall that DirectSearch cannot.Source: §9 · p. 13
- Compared with Lift, LinePG uses 1.86% of the index space and 2.15% of the construction time on full datasets on average.Source: §9 · p. 13
- Compared with TheoryLP, LinePG achieves more than 3 orders of magnitude faster index construction, a smaller index, and higher search performance.Source: §9 · p. 13