PaperlayerView exact revision on arXiv

Source-linked AI summary

Geo-Filtered Approximate Nearest-Neighbor Search on a Single Proximity Graph

Zhiqiu Zou, Rong-Hua Li, Qiangqiang Dai, Guoren Wang

arXiv:2610.34109v1cs.DB

TL;DR

Geo-filtered ANN must find vector-nearest objects inside geographic disks, where filtering can disrupt graph routes and existing approaches trade latency against index overhead. REACH uses one graph with vector-sorted rows and coordinate-aware connectivity; across four datasets it raises selective-query throughput over the best per-setting baseline. Its connectivity guarantees are proved under a spatial marked-site model.

  • Problem

    Disk filtering removes routing vertices from standard proximity graphs, while existing scan, over-fetch, and partitioned-index approaches trade latency against index overhead.

    Source: §1 · p. 1

  • Method

    REACH uses vector-sorted fixed-width rows whose active entries retain vector order, combines global vector candidates with a fiber-aware geographic stream, and searches the resulting single graph.

    Source: §1 · pp. 1–2

  • Results

    2.49× higher geometric-mean QPS than the best per-setting baseline at 0.95 Recall@10 on selective queries across four datasets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper concludes that active-edge recovery and coordinate-fiber connectivity let one REACH index per dataset support geo-filtered search with higher selective-query throughput.

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

    The connectivity guarantee is established under a regular marked-site model with sites on a compact connected region and bounded site density.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

Geo-filtered approximate nearest-neighbor (GFANN) search retrieves the objects inside a query-specified geographic disk whose feature vectors are closest to a query vector, a core operation in location-aware Web search. A disk filter on a standard proximity graph invalidates out-of-disk routing vertices; on selective disks, these removals break greedy paths and recall drops sharply. Existing methods scan all in-disk objects, over-fetch unfiltered candidates, or maintain separate sub-indexes across spatial partitions, trading latency for index overhead. We propose REACH, a single-graph index based on row-local active-order invariance: if every vertex stores its outgoing neighbors in a fixed-width row sorted by vector distance, any disk filter masks out-of-disk entries while surviving in-disk (active) neighbors remain vector-sorted. Offline, each vertex merges globally closest vector candidates with a nearest-first geographic stream into one row; online, beam search evaluates vector distances only for the first l active entries of each visited row. Because co-located objects share the same distance to every query center, every disk admits a coordinate group in full or not at all, decomposing active connectivity into intra-group and inter-coordinate conditions. Under a spatial marked-site model with repeated coordinates, we prove that polylogarithmic out-degree guarantees strong connectivity across all disks and constant-factor distance reduction per hop on compact disks, while a cut-rank threshold characterizes the minimum scan budget l. Across four datasets up to 10^7 objects, one REACH index per dataset outperforms SOTA methods, achieving 2.49x higher geometric-mean QPS than the strongest baseline at 0.95 Recall@10 on selective queries, while building 3.8x-11.9x faster and using 37%-45% less space than a SOTA spatial-graph index.

1 Introduction

REACH addresses the path erosion and index trade-offs of geo-filtered ANN with one fixed-width graph, combining vector-ranked rows with coordinate-aware connectivity. Across four datasets, it improves selective-query throughput while reducing build time and space relative to reported baselines.

1 Introduction

  • A disk filter can sever paths in a standard proximity graph because out-of-disk vertices that route between in-disk objects become unavailable.Existing approaches scan all in-disk objects, over-fetch global vector candidates, explore two-hop neighborhoods, or use partitioned indexes with latency or index-overhead trade-offs.Source: §1 · p. 1
  • REACH stores each vertex’s neighbors in a vector-sorted row so filtering preserves the vector-distance order of surviving in-disk entries.Scanning to the first ℓ active neighbors recovers Hℓ(c), with per-step vector evaluations capped at ℓ and minimum connectivity governed by cut rank.Source: §1 · pp. 1–2
  • Coordinate fibers pass or fail a disk filter as a unit, separating active connectivity into intra-fiber and inter-coordinate conditions.REACH assembles each row from global vector candidates and a fiber-aware geographic stream; co-located objects otherwise could consume the neighbor budget.Source: §1 · p. 2
  • The paper proves polylogarithmic-degree guarantees for strong connectivity and compact-disk shortcut routing under its marked-site model.Its contributions also include a cut-rank threshold and dual-source row assembly with a two-phase first-ℓ-active query algorithm and an O(n) seed grid.Source: §1 · p. 2

Comprehensive Evaluation

  • 2.49× higher geometric-mean QPS than the best per-setting baseline at 0.95 Recall@10 on selective queries; REACH was fastest in 14/16 selective cells.It also built 3.8×–11.9× faster than CubeGraph and used 37%–45% less space on three of four datasets.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the objects, geographic disks, and vector-nearest answers in GFANN, then explain how filtering affects proximity-graph search. They also establish why a single global ordering cannot represent every disk filter.

Data Model and GFANN Queries

  • A GFANN query asks for the k in-disk objects nearest to its query vector, with the requested count capped by the active-set size.Objects carry feature vectors and geographic coordinates; a closed disk defines the active set and its selectivity.Source: §2 · p. 2

Proximity Graphs, Beam Search, and Path Erosion

  • Proximity-graph ANN search uses vector-proximate neighbors and best-first beam search, but disk filtering can disconnect the induced active graph.With independent vectors and locations, only Bσ active edges per vertex remain in expectation; at σ=10−3 and B=32, the example expectation is 0.032.Source: §2 · pp. 2–3

Why 1D Range and Per-Condition Indexes Fail

  • The cited 1D range-filtered graph approach relies on one global order that makes every query interval contiguous, a property disks lack [12] [23] [43] [47].The three-object construction demonstrates the failure even for a small set of locations.Source: §2 · p. 3
  • 2D disks can induce Ω(n²) distinct active sets, and three objects suffice to show that no linear order makes every disk’s active set contiguous.The stated upper bound on the number of distinct disk active sets is O(n⁴).Source: §2 · p. 3

3 Ranked Active-Graph Recovery Theory

Ranked Active-Graph Recovery preserves vector-distance order after disk filtering, then uses coordinate fibers to reason about connectivity at two scales. Under a regular marked-site model, polylogarithmic degree suffices for strong connectivity, while a cut-rank threshold specifies the scan budget needed for a particular disk.

3.1 Active-Order Invariance and Recovery Graph

  • Filtering vector-sorted rows preserves the order of active neighbors; Hℓ(c) keeps the first ℓ, and it is strongly connected exactly when ℓ reaches the disk’s cut-rank threshold.The threshold is the worst cut’s earliest active rank for an outgoing edge.Source: §3.1 · p. 3

3.2 Coordinate Fibers and Route Decomposition

  • A disk admits each coordinate fiber wholly or not at all, and active-graph connectivity follows when both every active fiber and the quotient graph of active sites are strongly connected.The quotient route lifts to an object route by alternating inter-coordinate bridges with intra-fiber paths.Source: Figure 2 · p. 3, §3.2 · p. 4

3.3 Polylogarithmic Guarantees

  • Under the regular marked-site model, polylogarithmic geographic and fiber quotas make every active fiber and coordinate quotient strongly connected with probability at least 1−δ, yielding a strongly connected active graph.The stated bounds are B_g = Θ(log²(nM/δ)) and K_f ≥ C_f log(3nM/δ); the result also extends across Q disks by replacing δ with δ/Q.Source: §3.3 · pp. 4–5
  • On compact disks, the theorem gives α-factor distance reduction per greedy hop and at most ⌈log_α(D_x/ε_α)⌉ hops to reach the target under its fiber-size condition.A single width B = 384 suffices across the described coordinate-multiplicity scales.Source: §3.3 · p. 5

4 The Proposed REACH Index

REACH stores each vertex’s neighbors in one fixed-width, vector-distance-sorted row assembled from global vector candidates and a fiber-aware geographic stream. At query time, beam search filters each row and scores only its first ℓ active entries, with spatial seeding and practical budget choices supporting search.

4 The Proposed REACH Index

  • Each REACH row combines global-vector shortcuts with fiber-aware geographic edges, then sorts all retained neighbors by vector distance in a single fixed-width graph.The vector quota supports broad disks, while the geographic quota supplies local connectivity on selective disks.Source: §4 · p. 5

4.1 Dual-Source Row Construction

  • Algorithm 1 fills rows from a vector-neighbor pool and a nearest-first fiber stream, reuses vector survivors as zero-cost witnesses, and sorts the retained neighbors by distance.Its contract bounds rows by B valid IDs and preserves geographic representatives within radius ρ when the cumulative quota charge fits B_g.Source: §4.1 · p. 5

4.2 Online Query Processing and Spatial Entry

  • Algorithm 2 scans each visited row until ℓ active entries are found, then computes vector distances only for unvisited buffered neighbors, traversing Hℓ(cq).A fixed ℓ of 64, or 32 for selectivity at most 10^-3, stays within 0.0032 of the full-row recall ceiling across the 20 filtered benchmark cells; a grid directory supplies 16 active seeds.Source: §4.2 · pp. 5–6

5 Experiments

Across four datasets, experiments evaluate one fixed REACH index across geographic selectivities, measuring query performance, construction, storage, connectivity, and design choices. REACH leads most selective-query comparisons, while results also expose differences between clustered and uniform locations.

5.1 Experimental Setup

  • The evaluation uses four datasets, six selectivities, 1,000 queries per cell, and five baselines; REACH uses one fixed profile across datasets.The selectivities range from 10^-5 to 1, spanning street- or walking-scale, city- or metropolitan-scale, and unfiltered search.Source: §5.1 · p. 6

5.2 Experimental Results

  • 2.49× higher geometric-mean QPS than the best per-cell baseline at 0.95 Recall@10, with REACH fastest in 14 of 16 selective cells.The comparison uses one REACH index per dataset across selective queries.Source: §5.2 · p. 6, Figure 5 · p. 7
  • On SpaceV-Geo-10M, REACH leads at selectivities 10^-5 and 10^-4 but trails at 10^-2 and 10^-1, unlike its results on clustered datasets.At 10^-3 it beats CubeGraph (381 vs. 351 QPS) but trails Geo-Partition (586 QPS); the text attributes the later pattern to the uniform-site setting.Source: §5.2 · p. 7
  • REACH builds 3.8×–11.9× faster than CubeGraph and uses 37%–45% less space on three datasets.Construction times range from 117 s to 2,007 s; Figure 6 shows construction time and persistent index size.Source: §5.2 · pp. 7–8, Figure 6 · p. 7
  • For Yfcc-Clip at selectivity 10^-3, the full active projection has LSCC=100% on 98.4% of queries, while the cut-rank median is 48.With ℓ=64, the maximum-recall gap from ℓ=∞ is at most 0.0032 across filtered cells.Source: §5.2 · p. 8
  • Removing geographic or vector edges lowers Yfcc-Clip recall to 0.8811 or 0.9285, compared with 0.9981 using both sources.Grid seeding matches graph descent while reducing seed time 18×; Figure 7 covers connectivity and source/seeding ablations.Source: §5.2 · p. 8, Figure 7 · p. 8
  • At row width 384, the tested quota split 128/256 balances scan cost and recall; fiber α-pruning beats ID truncation on Yfcc-Clip.At L=256, recall is 0.9928 with fiber α-pruning versus 0.9860 with ID truncation; Figure 8 covers sensitivity and robustness.Source: §5.2 · p. 8, Figure 8 · p. 8

6 Related Work

Related work addresses filtered ANN through attribute-aware graphs, sub-indexes, composite metrics, or spatial partitioning. REACH instead uses coordinate fibers and a flat grid only for entry seeds.

6 Related Work

  • Filtered-ANN methods include label-embedded edges, inverted files, workload-tuned sub-indexes, relaxed monotonicity, composite metrics, and two-hop filtering.The section names Filtered-DiskANN, UNG, JAG [42], CGIF, SIEVE [21], VBASE, NHQ, DEG [45], and ACORN.Source: §6 · p. 8
  • Range-graph methods rely on a one-dimensional attribute order, which the paper says is absent for two-dimensional disks.The cited examples include SeRF, uRNG [23], RNSG [47], WinFilter [12], iRangeGraph [43], UNIFY [22], DSG, and DIGRA.Source: §6 · p. 8
  • Spatial and geo-textual indexes prune space before secondary filtering; REACH uses a flat grid only for entry seeds, unlike Mesh and CubeGraph [44].Mesh tunes cell graphs for a known workload, while CubeGraph [44] builds graphs across tree levels.Source: §6 · p. 8
  • REACH defines coordinate fibers as co-located objects admitted together by any disk, distinguishing them from FNS’s predicate-induced use of “fiber” [10].The section connects coordinate fibers to RGG theory [32].Source: §6 · p. 8

7 Conclusion

The conclusion frames REACH around row-local recovery and coordinate fibers, reporting polylogarithmic-degree connectivity and higher selective-query throughput. The appendix supplies complete formal proofs for the paper’s stated theoretical results.

7 Conclusion

  • REACH filters vector-sorted rows to recover Hℓ(c), with its scan budget governed by cut rank ℓSC(c).The conclusion describes this as Ranked Active-Graph Recovery.Source: §7 · p. 8
  • Coordinate fibers pass or fail a disk filter as a unit, supporting polylogarithmic-degree connectivity and 2.49× higher selective QPS.The conclusion presents these as the consequences of the fiber-based design.Source: §7 · p. 8

A Complete Proofs of Theoretical Results

A.1 Online Realization Invariance and Omitted Main-Text Proofs

The appendix formalizes how scan budgets, fiber structure, and spatial conditions yield active-graph connectivity and routing guarantees. It also states when recovery reproduces exact active nearest neighbors.

A.1 Online Realization Invariance and Omitted Main-Text Proofs

  • Hℓ(c) is strongly connected exactly when ℓ meets the maximum, over cuts, of the lowest-ranked active edge crossing each cut.The cut-rank threshold ℓSC(c) characterizes the minimum scan budget for strong connectivity.Source: §A.1 · p. 11
  • Fiber closure and route decomposition combine intra-fiber paths with a path through the quotient of active coordinates.The proof uses fiber closure to ensure a disk contains each coordinate fiber in full or not at all.Source: §A.1 · p. 11
  • Algorithm 2’s inspected active neighbors depend on the row, disk, and ℓ, not the runtime visited set.The appendix also states that recovery returns the exact active j-neighbor prefix when those neighbors are present in the row.Source: §A.1 · p. 11, §A.2 · p. 11
  • Under Theorem 3.7’s two conditions, the proof obtains strong connectivity with probability at least 1−δ, including under permitted location–vector dependence.The two conditions establish intra-fiber connectivity and quotient connectivity, respectively.Source: §A.1 · p. 11
  • For compact disks, the proof derives a witness at least an α-factor closer to a target, then bounds greedy hops by ⌈log_α(Dx/εα)⌉.It also bounds a greedy-search local minimum’s query distance by the optimum distance times (α+1)/(α−1).Source: §A.1 · p. 11
  • A single graph satisfies the connectivity theorem simultaneously for Q workload disks with probability at least 1−δ when quotas grow additively by O(log Q).The proof applies a union bound, with the required quotas affected by log Q inside the degree bounds.Source: §A.1 · p. 11

A.3 Proof of Disk Range Complexity

The proof bounds the number of distinct active sets induced by geographic disks between Ω(n^2) and O(n^4). The lower bound follows from disks realizing distinct contiguous intervals along a short geodesic arc.

A.3 Proof of Disk Range Complexity

  • O(n^4) is an upper bound on the number of disk-induced subsets, from the VC-dimension-four affine-halfspace class restricted to the sphere.The Sauer–Shelah lemma supplies the corresponding growth-function bound.Source: §A.3 · pp. 11–12
  • Ω(n^2) distinct active sets are realized by placing points along a short geodesic arc and choosing disks for every contiguous interval.The construction yields n(n + 1)/2 + 1 distinct sets, including the empty set.Source: §A.3 · p. 12

A.4 Proof of Intra-Fiber Connectivity (Theorem 3.7)

The intra-fiber proof uses regularity of vector supports and bounded candidate counts to lift short-range pairs into contracting directed paths. This supports strong connectivity within coordinate fibers under the stated model.

A.4 Proof of Intra-Fiber Connectivity (Theorem 3.7)

  • Under the marked-site model, vector supports are compact, connected geodesic spaces with bounded diameter and doubling constant, and satisfy local mass and covering bounds.The assumptions also require atomless distances and specify a minimum separation scale.Source: §A.4 · p. 12
  • If each vertex has at most K_f other fiber members within radius r, every r-radius pair has a directed path contracting vector distance by at least α per hop.The path length is at most ⌈log_α(d(x_u,x_v)/ε_z)⌉ hops.Source: §A.4 · p. 12
  • A rejected candidate is covered by an earlier retained witness within 1/α of the owner-to-candidate distance, yielding a sequence of progressively closer hops.The minimum pairwise separation ε_z terminates this sequence and bounds its length.Source: §A.4 · p. 12
  • When the symmetric r-radius graph on a fiber is connected, lifting both orientations of its edges through these paths makes the directed fiber graph strongly connected.The proof of Theorem 3.7 bounds the probability of violating the required fiber conditions using a covering net and a bound on nearby fiber marks.Source: §A.4 · p. 12
  • The survivor count from one coordinate is bounded by a_α when the minimum separation condition holds, with a union bound used to establish that condition globally.The argument counts separated survivors across dyadic annuli and bounds the chance of a pair falling below ε_α.Source: §A.4 · pp. 12–13

A.5 Proof of Coordinate-Quotient Connectivity (Theorem 3.7)

The appendix proves connectivity of the coordinate quotient under the spatial model, gives a finite-sample failure bound, and bounds route length on broader disks. It also describes REACH’s stored structures and grid-based entry seeding.

A.5 Proof of Coordinate-Quotient Connectivity (Theorem 3.7)

  • With probability at least 1 − 2δ/3, active coordinates form a strongly connected quotient when the geographic radius graph is connected and the per-vertex edge quota covers nearby coordinates.The proof combines fiber-charge, cell-occupancy, and site-crowding events.Source: §A.5 · p. 13

A.6 Explicit Finite-Sample Connectivity Bound

  • The finite-sample theorem bounds failure by Π(c), the sum of four event probabilities for charge, empty cells, site crowding, and disconnected fibers.Under the stated quota condition, the complete active projection is strongly connected with probability at least 1 − Π(c).Source: §A.6 · p. 13

A.7 Route Diameter on Broader Disks

  • For disks broader than ρ_c, route length is O(Δ(s_u,s_v)/ρ_c) geographic hops plus at most 1 + ⌈log_α(D_x/ε_α)⌉ hops within the target fiber.The route first follows the geographic site backbone, then contracts vector distance inside the target fiber.Source: §A.7 · pp. 13–14

B.1 Summary of Notation and System Overview

  • Offline REACH stores vector-sorted rows in a 4nB-byte table and an O(n) spatial grid seed directory; online queries scan active row entries and obtain initial seeds from the directory.The directory supplies τ active seeds inside the query disk.Source: §B.1 · p. 14

B.2 Grid Directory and Entry Seeding

  • The grid directory uses 0.5° latitude–longitude cells, and query-time ring expansion stops after τ = 16 active seeds are found or no remaining cell can intersect the disk.Construction takes two linear counting passes and under 0.6 seconds at n = 10^7.Source: §B.2 · p. 14

B.3 Spherical Numerics, Hyperparameters, and Work Scaling

The evaluation examines spherical disk checks, fixed construction settings, and query work across datasets and selectivities. Recovery-budget results show diminishing recall gains at high scan budgets, while required work varies with query selectivity.

B.3 Spherical Numerics, Hyperparameters, and Work Scaling

  • The overview figure depicts offline dual-source row assembly and online first-ℓ-active scanning, with the spatial directory supplying beam-search seeds.In its ℓ = 3 example, only the first two active entries are sent for vector scoring.Source: Figure 9 · p. 15
  • On SpaceV-Geo-10M at σ̄ = 10^-1, ℓ = 64 and L = 2048 reaches 0.9804 Recall@10 with 99,366 vector evaluations, while ℓ = ∞ reaches 0.9823.At the same selectivity, 23,766 evaluations yield 0.9561 recall; the table summarizes minimum mean calculations for Recall@10 ≥ 0.99.Source: Table 5 · p. 15, §B.3 · p. 15
  • Across three 10^6 datasets, the evaluated fraction of the active set falls from approximately 1.0 to 0.004–0.02 as σ̄ grows from 10^-5 to 1.Yfcc-Clip’s ratio of 1.76 at 10^-5 is attributed to boundary coordinate ties making m_q exceed m_tar.Source: Table 5 · p. 15, §B.3 · p. 15
  • The disk predicate uses a latitude–longitude bounding box followed by a 3D dot-product test on precomputed unit vectors; dataset preparation and baseline settings vary by dataset.The evaluation sweeps recovery budgets and beam sizes for REACH and search-effort settings for the compared methods.Source: §B.3 · pp. 14–15
  • On Overture-1M at σ̄ = 10^-1 and L = 16, increasing ℓ from 96 to ∞ changes Recall@10 by 0.0047, triples vector-distance evaluations, and reduces QPS by 2.8×.Across the 24 workload cells, only two unfiltered cells have a maximum-recall gap above 0.0032 between ℓ = 64 and ℓ = ∞.Source: §B.3 · p. 15

Related papers

Loading 2610.34109v1…