arXiv CS open access

RECAST: A Region-Scoped Adaptive Index for Exact Similarity Search

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

RECAST: A Region-Scoped Adaptive Index for Exact Similarity Search Yining Liu∗ , Rui Mao† ⊠

arXiv:2608.06962v1 [cs.DB] 7 Aug 2026

∗

Beijing Institute of Technology, Zhuhai, China † Shenzhen University, Shenzhen, China Email: lynnn@bit.edu.cn, mao@szu.edu.cn ⊠ Corresponding author

Abstract—Similarity search in metric spaces is routinely used in applications including bioinformatics, data mining, and recommender systems. Exact similarity search is dominated by distance computations, while real query streams often concentrate in specific regions rather than spreading uniformly across the space. Pre-built indexes are constructed before the query stream; if queries concentrate in regions poorly served by the fixed index structure, pruning remains weak and cannot improve online. Adaptive indexes such as AV-tree build the index from distances computed while answering queries, but discard most of the distances each query computes and do not effectively organize the retained distances for reuse, so valuable computation is not fully exploited to serve future queries in the same region. These limitations raise three challenges: the query-concentrated region is not known in advance and may change over time; distances already computed while answering earlier queries must be accumulated and reused only where they remain effective; and outdated distances from one region should not add overhead to queries in another. We propose RECAST, a region-scoped adaptive index for exact similarity search. RECAST maintains query regions, accumulates distances already computed while answering earlier queries (paid distances) within each region for exact pruning, and uses changes in their pruning effect to infer whether incoming queries are still concentrated in the current region. When queries shift, RECAST recursively dispatches query work to child regions, so paid distances are accumulated and reused only where they remain effective. On five real-world datasets under four workload patterns, RECAST achieves consistently lower cumulative cost than the adaptive baseline and most prebuilt baselines, reducing per-query distance computations by up to 64% and query time by up to 46% compared with the stateof-the-art adaptive baseline AV-tree. Index Terms—similarity search, metric space, adaptive indexing

I. I NTRODUCTION Similarity search in metric spaces is a fundamental operation in bioinformatics, multimedia retrieval, recommendation, and vector databases. Given a query object and a radius, an exact range query returns all database objects within that distance. Since objects in a metric space may lack coordinates and distance functions can be expensive, exact search is dominated by distance computations. In real workloads, queries often concentrate in specific regions rather than spreading uniformly across the space. For example, a researcher exploring a molecular database may first search intensively around one compound family and then shift to another. In each concentrated phase, nearby queries repeatedly encounter

false positive: far case

false positive: near case 𝒅 𝒑, 𝒒𝒏𝒆𝒂𝒓 +𝒓

𝒑 = 𝒒𝒕

𝒅 𝒑, 𝒒𝒏𝒆𝒂𝒓 −𝒓

𝒅 𝒑, 𝒒𝒇𝒂𝒓 −𝒓

𝒒𝒇𝒂𝒓

𝒒𝒏𝒆𝒂𝒓

𝒅 𝒑, 𝒒𝒇𝒂𝒓 +𝒓

Fig. 1. Pivot pruning on uniformly distributed data.

similar hard-to-prune candidates. This creates an opportunity to accelerate future queries by reusing what previous queries have already computed. Limitations of existing approaches. Existing indexes for exact similarity search fall into two groups: those that build a fixed structure before the query stream, and those that adapt query by query. Pre-built indexes such as LAESA [7], GNAT [8], SAT [9], and the learned index LIMS [13] optimize global separability without future query information. When queries concentrate in regions poorly served by the fixed structure, these methods cannot adapt online and pruning stays weak. AV-tree [1] is the closest adaptive baseline for exact similarity search in general metric spaces. It builds the index incrementally during queries [4], but each query contributes only a narrow refinement of the tree: it compresses all cracking distances into a single global tree and keeps at most one cached distance per object, so leaf-level pruning is bounded by a single pivot. Many distances paid while answering a costly query are not turned into a richer local pruning state, and later nearby queries may still revisit similar hard candidates. AVtree also cannot distinguish whether a costly query produces reusable distances, indicates a saturated region, or signals a new task. Figure 1 illustrates this effect on uniformly distributed data. Given a pivot p (a historical query) and a search radius r, the objects that cannot be pruned by the triangle inequality lie in

Challenges. When queries concentrate in specific regions, the distances that a query is forced to compute expose which objects are hard to prune, and this difficulty often recurs in nearby future queries. Exploiting this regularity while answering queries, without seeing the future, raises three difficulties. Challenge 1: The query-concentrated region is not known in advance and may change. The benefit of adaptive indexing comes from query concentration, but the index cannot observe where queries concentrate. It sees only the distances each query computes: how many objects were checked, how many were false positives, how many were pruned by the existing structure, and how these counts change over time. The same high cost can arise from different causes. The index may not yet have enough pruning power in this region, so continued learning would help. The available pruning mechanisms may already be near their limit in this region, so further effort yields little gain. The query may have moved to a new region where previously accumulated information does not apply. Or the query parameters may have changed. The challenge is to infer from these observable costs whether historical information is still relevant to the current query region. Challenge 2: An online index must decide when to exploit accumulated information and when to adapt to a new region. An online adaptive index must decide how each new query should change the structure. If the index changes the structure on every query, for example by unconditionally cracking large leaves as AV-tree does, repeated reorganization disrupts the structure learned under a stable workload, and the small modification from a single query may not accumulate into a strong local pruning state. If the index is too conservative and keeps the old structure, the structure fails on new queries when the workload drifts or shifts to a new region. The challenge is to keep learning when queries remain concentrated, to stop expanding when a region is saturated, and to switch to a new scope when the query focus shifts. Distinguishing these regimes requires reading the cost signals that each query exposes. Challenge 3: Historical information has scope and can pollute new queries. The distances paid by a past query are most effective for future queries in the same region. For queries in a different region, their pruning power is often weak and may vanish entirely: the stored distances fail to prune the new candidates, but the index still pays the cost of checking

LAESA

AV-tree

RECAST

(a) Fixed workload

105

(b) Jump workload shift A B

#distance computations

an annulus centered at p with inner radius max(0, d(q, p)−r) and outer radius d(q, p)+r. In the figure, gray dashed circles are pruned objects and orange dots are unprunable false positives that must be verified by exact distance computation. For a nearby query qnear , the annulus is narrow and contains few objects (strong pruning). For a distant query qfar , the annulus shifts outward and, in typical data distributions, covers more objects (weak pruning). This asymmetry is the source of adaptive benefit: an index that accumulates paid distances in a region where queries concentrate is often more effective than a pre-built global structure, because each stored distance is closely aligned with the query neighborhood it serves.

104 200

400 600 Query Sequence

800

1000

200

400 600 Query Sequence

800

1000

Fig. 2. Per-query distance computations on uniform20d under fixed and jump workloads.

them. If a partition splits a region but leaves objects whose distance to the split center was not computed in the parent, different query tasks accumulate in the same scope and the observable cost signals become ambiguous. The challenge is to maintain the correct scope for historical information so that it stays where it is useful and the rest forms a new scope that can learn on its own. Figure 2 confirms this on uniform data. Under a fixed workload (Figure 2(a)), both adaptive methods reduce perquery cost over time as accumulated distances provide pruning for subsequent queries in the same region; LAESA’s cost stays flat because its global pivots do not learn from the query stream. Under a jump workload (Figure 2(b)), the cost of both adaptive methods spikes when the query focus shifts at query 500, because the distances accumulated in region A are far from region B and its pruning power degrades as the annulus analysis predicts. AV-tree’s spike reaches 2.88× its pre-shift cost and recovers slowly (0.929×), because the tree structure shaped by queries in region A provides little pruning for queries in region B, and each leaf retains at most one cached distance, limiting the multi-pivot pruning that could accelerate re-learning. RECAST’s spike is smaller (1.75×) and recovery is faster (0.742×), because its region-scoped design allows region B to accumulate its own pivot distances independently of region A. Our approach. We observe that the distances a query is forced to compute serve a dual role. They are paid distances that can prune future candidates through the triangle inequality, and they are a signal of whether the current structure fits the current query region. RECAST builds on this observation. RECAST is an adaptive index for exact similarity search that treats each query region as an independent recursive online task. Each region maintains its own paid pivot table for objectlevel pruning. The same distance-computation statistics serve as runtime signals of regional task difficulty: the index reads whether the count of checked objects is falling, flat, or rising to assess whether its historical information remains relevant (addressing Challenge 1). When these signals indicate that the current structure no longer fits, RECAST does not reorganize at once but runs a shadow test over subsequent queries. The test checks whether a candidate partition would reduce later distance computations relative to the current pruning path, and

the partition is committed only if the test confirms a net saving, so regions that are saturated or still learning are naturally excluded from reorganization. The same cost signal also drives pivot retention within a region: when the cost is falling, the region conservatively keeps its accumulated distances; when the cost spikes, the region prefers evicting older pivots to make room for new distances. These two adaptive decisions share the same query-cost observations rather than relying on independent heuristics (addressing Challenge 2). After a partition, objects whose distance to the split center was not computed are collected into a residual child region with its own table. This prevents outdated distances from adding overhead to new queries and keeps these objects in a scope that can continue to learn and to partition (addressing Challenge 3). Experimental evidence. On five real-world datasets under four workload patterns, RECAST achieves consistently lower cumulative cost than the adaptive baseline and most pre-built baselines, reducing per-query distance computations by up to 64% and query time by up to 46% compared with the stateof-the-art adaptive baseline AV-tree (Section IV). Contributions. Our contributions can be summarized as follows. Recursive region-adaptive indexing framework. We propose RECAST, a region-scoped adaptive index for exact similarity search in metric spaces. RECAST models each query region as an independent recursive online task. Each region maintains its own paid pivot table for object-level pruning and reuses query-paid distances as signals of regional task difficulty. Objects not covered by a partition form independent child regions that continue to learn, so the entire dataset remains continuously adaptive (Section III-A). • Signal-driven adaptive pivot management (addresses Challenge 2). We design a per-region paid pivot table whose retention and eviction are driven by the region’s cost signal rather than by a fixed lifecycle rule. The same signal that distinguishes “still learning”, “saturated”, and “shifted” regimes governs both pivot retention and partition timing, so pivot management and partition decisions share a unified adaptive framework (Section III-B). • Cost-signal-driven partition algorithm with shadow validation. We introduce a partition decision algorithm that reads the trend of distance computations in a region, including the checked count, the false-positive ratio, the pruning rate, and their evolution, to determine when the current structure no longer fits the query workload. A candidate partition is committed only after a shadow test over subsequent queries confirms that it reduces distance computations beyond the current pruning path (Section III-C). • Extensive experiments. On five datasets under four workload patterns (20 combinations), RECAST reduces per-query distance computations by up to 64% and query time by up to 46% compared with AV-tree, winning all 20 combinations in distance computations. Four ablation

•

TABLE I F REQUENTLY USED NOTATION

Symbol

Meaning

(M, d) O, n o, x q, r R PR p s θ

metric space and distance function dataset and its cardinality |O| a data object in O a query object and its search radius a region, a subset of O with its own table the paid pivot table of region R a pivot (a past query center or split center) a split center of a region the leaf-size threshold

studies confirm the individual contributions of each component (Section IV). II. P ROBLEM S TATEMENT We define the metric space, the similarity query, and the adaptive setting we study. Table I lists the frequently used notation. Metric space. A metric space is a pair (M, d), where M is a domain of objects and d : M × M → R≥0 is a distance function. For all x, y, z ∈ M , d satisfies identity (d(x, x) = 0), positivity (x ̸= y ⇒ d(x, y) > 0), symmetry (d(x, y) = d(y, x)), and the triangle inequality (d(x, z) ≤ d(x, y) + d(y, z)). Distance functions used in practice include Manhattan and Euclidean distance on numerical features, edit distance on strings, and quadratic-form distance on color histograms. Evaluating d can take milliseconds, so the number of distance computations is the dominant cost of a query. We index a dataset O ⊂ M with |O| = n objects. Range query. Given a query object q ∈ M and a search radius r ≥ 0, a range query seeks all objects in O within distance r from q [1], [5]. Definition 1 (Range Query): Given a dataset O, a query object q ∈ M , and a radius r ≥ 0, a range query returns RQ(q, r) = { o ∈ O | d(q, o) ≤ r }. Given a positive integer k, a k-nearest-neighbor (kNN) query seeks the k objects in O with the smallest distance to q. A kNN query can be reduced to a sequence of range queries with a shrinking radius. Our implementation includes a basic kNN variant; adapting the cost signal to the dynamic radius for stronger performance is left for future work. This paper focuses on range queries. Adaptive setting. We study similarity search in an adaptive setting. The dataset O is given, but no index over O is built in advance. Queries q1 , q2 , . . . arrive in sequence, and the index must answer each qi before qi+1 arrives. Distances computed while answering a query may be kept and reused for later queries, but the index never runs a separate construction phase that computes distances unrelated to a pending query. We measure the cost of a query by the number of distance computations it performs, and report query time as a secondary measure.

III. T HE RECAST I NDEX We derive the design of RECAST from three observations about the nature of distance computations in adaptive indexing for exact similarity search. These observations are properties of the problem setting, not of any particular index. Observation 1: Every distance computation has dual value. When an adaptive index computes d(x, p) to answer a query, this distance serves two purposes. It determines whether x belongs to the result, and it becomes a reusable fact: for any future query (q, r), the triangle inequality gives d(q, x) ≥ |d(x, p) − d(q, p)|, so x can be pruned without computing d(q, x) if this lower bound exceeds r. The distance is both the cost of the current query and a reusable paid distance for future queries. This dual value exists as soon as the distance is computed. Observation 2: The reuse value of a distance is local, not global. The pruning power of a stored distance d(x, p) for a future query (q, r) depends on d(q, p). When q is close to p, the objects that p cannot prune form a narrow band, and most others are pruned. When q is far from p, the band widens and the stored distance loses its pruning power. In highdimensional spaces where distances concentrate, the band may cover most objects even for nearby queries, limiting all pivotbased pruning. Nevertheless, the dependence on d(q, p) holds in all settings: distances paid by queries in one region are most useful for future queries in the same region. A single global table that mixes distances from different regions dilutes the locally useful pruning power. More precisely, given pivot p and query (q, r), the objects that cannot be pruned by p are those with d(x, p) ∈ [max(0, d(q, p)−r), d(q, p)+r]. As d(q, p) grows, this interval shifts outward and typically contains more objects, so the fraction of candidates that survive the pivot increases (Figure 1). This is why distances computed by nearby queries provide strong pruning while distances from distant queries contribute little. Observation 3: The number of distances a query still computes directly measures structure fitness. After an adaptive index has accumulated some structure, each new query computes fewer distances than a linear scan. The count of distances still computed, relative to the region size and its recent trend, measures how well the current structure serves the current workload. A falling count means the structure is learning. A flat or rising count means the structure may have reached its limit or the workload may have shifted. We call this count the cost signal; it is a free byproduct of query execution. Design implications. These observations lead to three design choices. From Observation 1, distances computed during a query that meet the admission threshold are retained as a trial pivot column in the region where the query was processed (Section III-B). From Observation 2, we scope each pivot table to its own region, and when a region no longer fits the workload, we create new regions with their own tables (Section III-A). Observation 3 is used at two levels: the same cost signal drives both pivot retention in Section III-B and

partition timing in Section III-C, so the two adaptive decisions share a single mechanism rather than independent heuristics. A. Index Structure and Query Flow This subsection describes how RECAST organizes the dataset and processes queries. Figure 3 illustrates the query flow on a small example. Region. RECAST organizes the dataset as a tree of regions. A region R holds four components: an object scope OR ⊆ O, a paid pivot table PR (so called because every distance in PR was computed as part of answering a past query, not in a separate construction phase), query statistics HR that track recent distance-computation counts, and, if R has been partitioned, three children (left, right, and residual). Every region runs the same logic. The root region covers the whole dataset. A leaf region covers a small subset. There is no separate global structure. Running example. Figure 3 shows the state of RECAST after processing several queries that triggered two partitions. Initially, all objects reside in a single root region with an empty pivot table. As queries arrive, the root accumulates pivot columns and its cost signal stabilizes. When query q 5 arrives, the candidate selection conditions (Section III-C) are met and a shadow test confirms that splitting around q 5 would reduce future distance computations. The root is partitioned: objects whose distance to q 5 falls below the median go to R1 , those above go to the right child, and objects whose distance was (root) not computed go to the residual child Rres . The split center q 5 is installed as the first pivot in both R1 and the right child at no extra cost. The right child then accumulates its own pivots from subsequent queries. When query q 12 triggers a second partition of the right child, the same process produces (node) R2 , R3 , and Rres ; existing pivots in the right child, such as those from q 8 , are inherited by the new children. When the current query q arrives (left side of Figure 3), RECAST routes it through the tree. At the root, d(q, q 5 ) is computed and checked against each child’s distance interval: R1 is skipped (no intersection), the internal node is visited (root) (intersection), and Rres is visited unconditionally. At the internal node, both R2 and R3 are visited. The right side of the figure expands R3 ’s pivot table PR3 , which holds distances from three historical queries (p1 =q 8 , p2 =q 21 , p3 =q 35 ). For each active pivot p, RECAST computes d(q, p) once and prunes every object x satisfying |d(x, p)−d(q, p)| > r. A dash in the table indicates a missing distance; such objects pass the pivot unchecked and require exact distance verification. Query flow. A query (q, r) enters at the root region. If the region has been partitioned with split center s and child distance intervals Ileft and Iright , RECAST computes d(q, s) and skips a child whose interval does not intersect [d(q, s)−r, d(q, s)+r]. The residual child has no interval, so it is always visited. If the region has not been partitioned, RECAST processes it as a leaf (Algorithm 2). The query may then trigger a partition of the region (Section III-C). Algorithm 1 summarizes the routing.

root node current query q

split center = historical query 𝑞" children: L: [...]

R: [...]

residual

always visited

Leaf region R3: local pivot table PR3

𝑅$%& (,--.)

visit

residual region

internal node

object

p1 = q8 historical query pivot

p2 = q21 historical query pivot

p3 = q35 historical query pivot

2.1

—

7.8

1.9

4.8

6.6

x12

3.2

6.1

—

x18

2.7

—

split center = historical query q12 children: L: [...] skip

𝑅! leaf region

local pivot table 𝑃!

always visited

𝑅$%& (()*%)

residual region

local pivot table 𝑃!

R: [...]

residual

visit

local pivot table 𝑃! visit

𝑅#

𝑅"

leaf region

local pivot table 𝑃!

Fig. 3. RECAST query processing. Each leaf region maintains its own pivot table PR . All split centers and pivot centers are historical queries.

Algorithm 1 Query routing 1: procedure Q UERY (R, q, r, result) 2: if R is partitioned with split center s then 3: compute d(q, s) 4: for all child C ∈ {Rleft , Rright } do 5: if IC ∩ [d(q, s) − r, d(q, s) + r] ̸= ∅ then 6: Q UERY(C, q, r, result) 7: end if 8: end for 9: Q UERY(Rresidual , q, r, result) 10: else 11: P ROCESS L EAF(R, q, r, result) 12: end if 13: end procedure

Recursive decomposition. A partition produces three children: left and right hold objects with known distances to the split center; the residual child holds objects whose distance to the split center was not computed. The residual child is a full region with its own table and can be further partitioned. Section III-C describes the partition mechanism. B. Signal-Driven Paid Pivot Management Observation 1 tells us that distances computed during a query can serve as reusable paid distances. The question is how to manage these distances within a region. Keeping all distances forever fills the table with old or low-value pivots, while a fixed eviction policy such as FIFO or LRU cannot fit both stable workloads, where good pivots should be preserved, and shifting workloads, where stale pivots should be replaced quickly. We use the same region cost signal to govern pivot admission, retention, and eviction, so that pivot management and the partition decision in Section III-C share a single signaldriven framework.

Object-level pruning. When a region R is processed as a leaf, RECAST prunes candidates using PR . Each pivot p ∈ PR is a past query center or a split center. The table stores d(x, p) for each object x whose distance to p was computed by an earlier query. For a new query (q, r), RECAST computes d(q, p) once and prunes every object x for which |d(x, p) − d(q, p)| > r. An object survives only if it passes every active pivot. Because PR is scoped to R, the pivots come from queries that visited R, not from queries elsewhere. Admission and confirmation. Each region R maintains a paid pivot table with a total budget of K pivots. A new distance column enters the table only when the current query checked at least cmin objects and produced at least fmin false positives in R. The column starts in a trial state. Each subsequent query that visits R activates the column and records its pruning gain. Let gp denote the cumulative number of objects pruned by pivot p minus the cumulative number of pivot-query distances d(q, p) it consumed. When gp exceeds a confirmation threshold τ , the pivot transitions to a confirmed state. Signal-driven eviction. When the table budget K is exceeded or the number of trial pivots exceeds the trial cap Kn , the eviction policy is selected by the current cost signal in R: When cR (q) < c̄R (the cost is falling and R is still learning), or when R is visited for the first time and no prior cost history exists, only trial pivots with gp ≤ 0 are evicted; confirmed pivots are kept. • When cR (q) > κ · c̄R (κ=4, i.e., a fourfold cost spike), pivots are evicted in order of oldest birth query, and confirmed pivots may also be evicted to make room for new distances. • Otherwise, the pivot with the lowest eviction score ep = gp /|Vp | is removed, where |Vp | is the number of objects with a stored distance to p; trial pivots receive an additional penalty so that unproven columns are removed

•

Algorithm 2 Leaf processing 1: procedure P ROCESS L EAF(R, q, r, result) 2: active ← select up to K pivots from PR by gain gp 3: for all p ∈ active do compute d(q, p) 4: end for ▷ K pivot-query distances 5: for all x ∈ OR do 6: pruned ← false 7: for all p ∈ active with d(x, p) stored do 8: if |d(x, p) − d(q, p)| > r then 9: pruned ← true; break 10: end if 11: end for 12: if not pruned then 13: compute d(q, x) 14: if d(q, x) ≤ r then add x to result 15: end if 16: end if 17: end for 18: if checked count ≥ cmin and false positives ≥ fmin then 19: record {d(q, x)} as a new trial column in PR 20: end if 21: select eviction mode by cR (q) vs c̄R ; confirm and evict accordingly 22: update HR : checked count, false positives, pivot pruned 23: evaluate partition candidate (Section III-C) 24: end procedure

before confirmed ones. The conditions that select the eviction behavior are the same cost observations used by the partition trigger in Section III-C: stable workloads keep good pivots and avoid partition, shifting workloads replace stale pivots and trigger partition candidates, and intermediate states fall back to gain-ordered decisions in both subsystems. We use K=32 pivots per region with a trial cap of Kn =8; Section IV-A lists the full parameter setting. Algorithm 2 details the leaf processing. It selects up to K active pivots by gain (line 1), computes d(q, p) for each (line 2), and prunes objects whose stored distance violates the triangle bound (lines 5–8). Survivors are verified by exact distance (lines 10–12). If the checked count and false-positive count exceed their thresholds, the distances from this query are recorded as a new trial column (lines 14–15). Finally, the cost signal selects the eviction behavior and the region statistics are updated (lines 17–19). C. Cost-Signal-Driven Partition Observations 1 and 3 together tell us that the distances computed during a query both produce reusable paid distances and measure structure fitness. Section III-B described how the same signal drives pivot retention. This subsection describes how the same signal drives the partition timing. Partitioning a region introduces a routing distance on every future query and changes the structure that later queries depend on. A premature

partition disrupts learning. A delayed partition keeps paying for a poor structure. Split mechanism. A partition uses the triggering query q as the split center s. Let Cq ⊆ OR be the objects whose distance to s was computed during this query. RECAST computes the median µ of {d(x, s) : x ∈ Cq } and assigns objects with d(x, s) ≤ µ to the left child and objects with d(x, s) > µ to the right child. Let L = {x ∈ Cq : d(x, s) ≤ µ} and R′ = {x ∈ Cq : d(x, s) > µ}. The distance intervals are Ileft = [minx∈L d(x, s), µ] and Iright = (µ, maxx∈R′ d(x, s)]. These intervals are fixed at split time and not updated afterward. Objects in OR \Cq , whose distance to s was not computed, are collected into the residual child. The split center s is installed as a pivot in the left and right children, providing them with an initial pruning column at no extra cost. Query statistics. Each region R maintains statistics HR that track the recent behavior of queries in R. These include the number of visits, the exponential moving average of the checked-object count c̄R , the total false positives, and the total objects pruned by the pivot table. The EMA is updated after each visit as c̄R ← λ·cR (q)+(1−λ)·c̄R , where λ controls how fast the average responds to new queries. These statistics are updated at the end of each leaf processing step (Algorithm 2, line 19). Candidate selection. A region R becomes a partition candidate for the current query (q, r) when the following conditions are all met: 1) |OR | ≥ σ (σ=512); 2) R has been visited at least twice; 3) the checked-object count cR (q) satisfies cR (q)/|OR | ≥ α; 4) the false-positive ratio fR (q)/cR (q) ≥ β; 5) at least one of the following holds: (5a) the pivot prune rate pruned R (q)/(cR (q) + pruned R (q)) < ρ (the existing pivots are not pruning well, suggesting the structure is saturated for this region); (5b) the checked count exceeds κ · c̄R (κ=4; a fourfold cost spike suggests the workload has shifted to a new region); (5c) the pivot table is full (the region has no room for new distances, so further learning within the current scope is limited). A region whose cost is falling (cR (q) < c̄R ) is not a candidate, because the pivot table is still learning. The three trigger conditions (5a saturation, 5b spike, 5c table full) correspond directly to the three eviction modes in Section III-B: 5a triggers when gain-based eviction in R no longer recovers pruning power, 5b coincides with aggressive-mode eviction when the workload shifts, and 5c arises when conservativemode eviction cannot free space, so all adaptive decisions in RECAST derive from the same cost observation. Shadow validation. A candidate partition is not committed at once. RECAST creates a shadow split with center s and median µ, and tests it against subsequent queries without

changing the actual structure. For each subsequent query (q ′ , r′ ) that visits R, the shadow computes d(q ′ , s) and determines which child would have been skipped. It records the counterfactual saved checks: the number of objects in the skippable child that were not already pruned by the existing pivot table. The net score is X X net = saved i − routing i , i

where saved i is the counterfactual saved checks of the i-th subsequent query and routing i = 1 is the routing distance it would have added. The partition is committed when the shadow has been tested for at least v queries and net ≥ η. If net < η after v queries, the shadow is discarded. This two-stage process follows from Observation 3. Candidate selection reads the cost signal to detect that a region may need reorganization. Shadow validation verifies that the specific partition would reduce distance computations. Together they avoid both premature and delayed partition. The shadow test also mitigates the risk of a poor split center: if the triggering query happens to be an outlier, the shadow will not accumulate enough saved checks to pass the commit threshold. In Figure 3, the partition at the internal node (split center q 12 ) was committed only after the shadow test confirmed that routing through q 12 would save enough distance computations in subsequent queries to offset the added routing cost. Algorithm 3 summarizes the partition decision. It is invoked at the end of each leaf processing step (Algorithm 2, line 20). When the candidate conditions are met, a shadow is created; when a shadow passes validation, the region is committed into three children. Cost and correctness. Each stored distance d(x, p) is recorded once. With a budget of K pivots per region, the worst-case storage is O(n · K) distance pairs; in practice, only objects that have been checked by at least one query have stored distances. Each query pays one routing distance per visited internal region, up to K pivot-query distances per visited leaf, and exact distances for survivors. Regions smaller than σ are not further partitioned, which limits the tree depth in practice. RECAST prunes an object only when a stored distance and the triangle inequality prove it cannot be in the result. Objects whose distance to a pivot is missing pass the pivot unchecked. The residual child is always visited because it has no distance interval. Therefore, every query returns the exact answer. IV. E XPERIMENTS We evaluate RECAST against adaptive and pre-built baselines. We first compare RECAST with AV-tree across multiple workload patterns (Section IV-B), then include pre-built indexes in a cumulative-cost analysis that accounts for their upfront build cost (Section IV-C). Section IV-D studies the contribution of each component. A. Experimental Settings Datasets. Table II summarizes the five datasets.

Algorithm 3 Partition decision 1: procedure E VALUATE PARTITION(R, q, r, Cq ) 2: if R has an active shadow S then 3: compute d(q, S.center ) 4: saved ← objects in skippable child not already pruned 5: S.net ← S.net + saved − 1 6: S.visits ← S.visits + 1 7: if S.visits ≥ v and S.net ≥ η then 8: C OMMIT PARTITION(R, S) ▷ create 3 children 9: else if S.visits ≥ v and S.net < η then 10: discard S 11: end if 12: else if candidate conditions (1)–(5) are met then 13: µ ← median{d(x, q) : x ∈ Cq } 14: create shadow S with S.center ← q, S.µ ← µ, S.C ← Cq , S.D ← {d(x, q) : x ∈ Cq } 15: end if 16: end procedure 17: procedure C OMMIT PARTITION(R, S) 18: L ← {x ∈ S.C : S.D[x] ≤ S.µ} 19: R′ ← {x ∈ S.C : S.D[x] > S.µ} 20: U ← OR \ S.C ▷ residual: distances unknown

create Rleft with objects L, install S.center as pivot create Rright with objects R′ , install S.center as pivot create Rresidual with objects U set Ileft ← [minx∈L S.D[x], S.µ], Iright ← (S.µ, maxx∈R′ S.D[x]] 25: mark R as partitioned 26: end procedure 21: 22: 23: 24:

TABLE II DATASETS USED IN THE EXPERIMENTS .

Dataset glove100 sift1m sift10m colors112d nasa20d

Size

Dim

Distance

Note

1.18M 1.0M 10.0M 0.11M 0.4M

100 128 128 112 20

L2 L2 L2 QFD L2

word embeddings SIFT descriptors scalability non-L2 metric low-dim boundary

Workloads. We use four workload patterns, each consisting of 1 000 queries at 1% selectivity: a fixed pattern where all queries target the same region, a jump where the focus shifts from region A to region B at query 500, a drift that gradually moves from A to B over the full trace, and a three-jump that cycles A→B→C. Baselines. Adaptive: AV-tree [1] (cracking threshold θ=128, distance caching enabled). Pre-built: LAESA (32 pivots) [7] and GNAT [8]. Reference: Linear scan. We fix K=32 for RECAST throughout (both pivot budget and active budget). Metrics. The number of distance computations per query is the primary measure; query time is the secondary measure. Each experiment runs three seeds; we report the mean.

Hardware and implementation. All methods are implemented in C++ and compiled with g++ 11.4.0 using -O3 -mavx -march=native. Experiments run on a 754 GiB Ubuntu 22.04.5 LTS machine with two Intel Xeon Platinum 8276L CPUs at 2.20 GHz. B. Main Comparison This experiment tests whether RECAST reduces per-query distance computations consistently across datasets and workload patterns. We compare RECAST with AV-tree across all five datasets and four workloads (20 combinations). Both are adaptive indexes that build from queries, so per-query distance computations (DC) and query time are directly comparable without a build-cost offset. Linear scan is included as a sanity reference. Overall, RECAST reduces per-query distance computations to 0.615× that of AV-tree (geometric mean across all 20 combinations) and query time to 0.863×, winning all 20 combinations in distance computations. RECAST also reduces query time on 16 of 20 combinations; on nasa20d (1.7– 2.3× slower), the per-pivot management overhead exceeds the distance-computation savings because individual distance evaluations in 20 dimensions cost only ∼0.5 µs. Figure 4 plots the per-query distance computations across all 20 combinations. Cross-dataset comparison. The DC advantage varies across datasets in a pattern that reflects dimensionality, dataset size, and the cost of the distance function. On nasa20d (20 dimensions), RECAST achieves the largest DC reduction (geometric mean 0.435× across four workloads) (Figure 4, panels e, j, o, t), because the low intrinsic dimensionality makes each stored pivot distance a strong discriminator: the triangle-inequality lower bound is tight relative to the search radius, so a small number of region-local pivots already prunes most candidates. On sift10m (n=10M, 128 dimensions), the per-dataset geometric mean is 0.569×, and on colors112d (112 dimensions, quadratic-form distance) it is 0.558×. The sift10m result confirms that the DC advantage scales with dataset size: at 10× the objects of sift1m, the per-query saving from accumulated pivot distances grows because more candidates fall within each region and each pivot column amortizes over a larger object set. The colors112d result confirms that the region-scoped design is metric-agnostic; the quadratic-form distance is not L2 , yet the same pivot-reuse mechanism reduces DC by a comparable factor. On glove100 (100-dimensional word embeddings), the DC ratio is 0.926×, the smallest improvement among all datasets (panels a, f, k, p). We attribute this to the distance concentration in the embedding space: the pairwise distance distribution of glove100 is narrower than those of sift1m and colors112d, which makes the triangle-inequality lower bound loose for most object-pivot pairs regardless of the pivot’s position. RECAST still reduces DC on glove100 because region-scoping restricts each pivot table to a local neighborhood where the effective distance spread is wider than the global distribution, but the absolute gain is smaller. On sift1m (128 dimensions, n=1M), the geometric mean is

0.685×, intermediate between the low-dimensional and the highly concentrated cases. Workload comparison. Under the fixed workload, both adaptive methods converge because neither faces a shift. The gap widens under jump and drift workloads: after the query focus moves to a new region, AV-tree’s existing tree structure provides little pruning in the new region, whereas RECAST’s region-local tables in the new target may already hold partial distances from earlier visits. Quantitatively, the per-workload DC geometric means (across five datasets) are: fixed 0.707×, drift 0.639×, jump 0.572×, and three-jump 0.552×. The three-jump workload produces the largest advantage (panels p–t) because each shift exposes AV-tree to a region where its existing tree structure provides little pruning, and the single cached distance per object limits how quickly it can re-learn. RECAST’s region-local tables, by contrast, retain distances accumulated during phase A that partially transfers when the workload returns to a nearby region or when the residual child from an earlier split already covers objects in the new target. Under fixed, both methods converge to a stable structure and the gap is smallest; the remaining 0.707× reduction comes from RECAST’s multi-pivot pruning within each region, which AV-tree cannot match with its single cached distance per object. Figure 4 visualizes the per-query behavior across all 20 combinations. Under jump and three-jump workloads, AVtree’s per-query distance computations spike at the shift point and recover slowly; RECAST’s spike is shallower and recovery is faster, because region-local pivot tables retain distances from earlier visits. Under drift, the transition is gradual and RECAST maintains a consistently lower envelope. On nasa20d, the distance-computation gap is large (DC ratio 0.435×), yet RECAST’s query time exceeds AV-tree’s by 1.7– 2.3× because each distance evaluation in 20 dimensions costs only ∼0.5 µs, and the per-pivot overhead outweighs the saved computations. This boundary case confirms that RECAST targets settings where distance computations are expensive relative to the bookkeeping cost. C. Cumulative Cost versus Pre-Built Indexes This experiment tests whether RECAST’s cumulative cost remains competitive with pre-built indexes that pay their build cost upfront. Pre-built indexes pay a one-time build cost and then answer every query at a fixed per-query rate. We include this build cost in the cumulative DC curve so that the trade-off between upfront investment and adaptive learning is visible. We add the construction cost of each pre-built index to its cumulative curve before the first query. Figure 5 plots the cumulative cost normalized to linear scan. Break-even analysis. Pre-built indexes pay their full construction cost before answering any query, so their cumulative curves start above zero. Adaptive indexes start from zero but pay a higher per-query cost during early learning. The breakeven point is the query index at which the adaptive curve crosses below the pre-built curve. On sift10m (Figure 5(c)), LAESA’s build cost is 320 × 106 DC (32 × n). RECAST’s

RECAST

Linear

GloVe-100

SIFT-1M

SIFT-10M

Colors-112

NASA-20

(a) GloVe-100 / fixed

(b) SIFT-1M / fixed

(d) Colors-112 / fixed

(e) NASA-20 / fixed

107

106

fixed

AV-tree

105

104

106

105

(f) GloVe-100 / jump

(g) SIFT-1M / jump

(h) SIFT-10M / jump 10

(i) Colors-112 / jump 10

jump

104

104 10

106

(l) SIFT-1M / drift

(m) SIFT-10M / drift 10

(n) Colors-112 / drift 10

drift

(k) GloVe-100 / drift

(q) SIFT-1M / 3-jump

(r) SIFT-10M / 3-jump 10

104

(s) Colors-112 / 3-jump 10

3-jump

106 500

Query Sequence

1000

500

Query Sequence

1000

500

Query Sequence

1000

(o) NASA-20 / drift

104

(p) GloVe-100 / 3-jump

(j) NASA-20 / jump

(t) NASA-20 / 3-jump

104 500

Query Sequence

1000

500

Query Sequence

1000

Fig. 4. Per-query distance computations on five datasets under four workloads.

cumulative DC curve starts from zero and remains below LAESA’s curve for the entire 1 000-query trace, because the build cost alone exceeds the total distance computations RECAST pays over 1 000 queries. On sift1m (build cost 32 × 106 DC), RECAST’s cumulative curve crosses below LAESA within the first 150 queries; once region-local pivots accumulate, the per-query DC drops and the gap widens steadily. On glove100 (build cost 38.4 × 106 DC), the crossover also occurs early because RECAST’s per-query DC (∼1.09 × 106 ) is only marginally below LAESA’s (∼1.17 × 106 ), but the build cost deficit that LAESA carries is never recovered within 1 000 queries. On nasa20d (Figure 5(e), build cost 1.28 × 107 DC), LAESA’s 32 global pivots already prune well in 20 dimensions (per-query DC ∼4.6 × 103 ), lower than both AVtree (19.9 × 103 ) and RECAST (8.5 × 103 ). LAESA’s cumulative curve crosses below RECAST’s after approximately 200 queries and remains lower for the rest of the trace. This is

the one dataset where a pre-built index outperforms RECAST in cumulative DC, because the low dimensionality makes a small set of global pivots sufficient and the build cost is modest relative to n. On colors112d (build cost 3.6×106 DC), RECAST crosses below LAESA at approximately query 200. Across all datasets, AV-tree’s cumulative curve lies between RECAST and LAESA, confirming that region-scoped distance reuse, not merely adaptive construction, drives the cumulative improvement over both pre-built and adaptive baselines. We show the jump workload because it is the standard single-shift pattern; trends under fixed, drift, and three-jump are consistent. D. Component Ablation This experiment isolates the contribution of each RECAST component by replacing it with a simpler alternative while keeping the rest intact. Figure 6 plots the cumulative distancecomputation ratio (variant / RECAST-full) over the query

Cumulative DC / Linear

RECAST

LAESA

GNAT

Linear

GloVe-100

SIFT-1M

SIFT-10M

Colors-112

NASA-20

(a) GloVe-100

(b) SIFT-1M

(d) Colors-112

(e) NASA-20

102

101

100

101 100

100

(f) GloVe-100

Cumulative time / Linear

AV-tree

(g) SIFT-1M 102

10 0

500

1000

Query Sequence

(i) Colors-112

(j) NASA-20

102

101

101 100

(h) SIFT-10M

101

101 100

100

100 0

500

1000

Query Sequence

500

1000

Query Sequence

500

1000

Query Sequence

500

1000

Query Sequence

Fig. 5. Cumulative cost normalized to linear scan (jump workload). Top: distance computations. Bottom: query time. Pre-built methods include build cost.

trace: a line above 1.0 means removing the component increases cost. Pivot management. We replace the signal-driven adaptive eviction policy (Section III-B) with two fixed alternatives: FIFO (evict the oldest pivot) and LRU (evict the least recently used pivot), keeping the same pivot budget K=32. On colors112d (Figure 6(a)), FIFO and LRU increase cumulative distance computations by 20–30%. The QFD distance function concentrates pruning power in a few pivots whose triangleinequality bounds align well with the query distribution; the adaptive policy detects these pivots through their high cumulative gain gp and retains them, while FIFO evicts them once they become the oldest entry regardless of pruning value. On glove100 (Figure 6(b)), the gap is small (<5%) because distance concentration limits all pivots to similar marginal pruning power. Signal and shadow validation. We replace the cost-signaldriven partition trigger with shadow validation (Section III-C) by an unconditional split: every qualifying query triggers an immediate split without cost-signal gating or shadow testing. On colors112d (Figure 6(c)), unconditional splitting increases cumulative distance computations by 10–15%, because it fractures regions whose pivot tables are still learning, destroying accumulated distances before it reaches full pruning effectiveness. On glove100 (Figure 6(d)), the distance-computation increase is smaller (5–10%), but query time roughly doubles because each unnecessary split adds one routing distance computation d(q, s) on every subsequent query that traverses the over-fragmented tree.

Residual child. We remove the residual child by assigning all unclassified objects to the parent bucket instead of creating an independent child region. This produces the largest ablation effect. On nasa20d under three-jump (Figure 6(f)), the cumulative ratio reaches 1.5× by query 1 000. Each of the three workload shifts routes queries into a region where unclassified objects from an earlier split reside. With the residual child, these objects form an independent region and begin accumulating pivots from the new query stream. Without it, they remain in the parent bucket, which mixes objects from all prior splits; every visit scans them linearly because the parent’s pivot table was built for the old workload and provides little pruning for the new one. Region scoping. We compare RECAST with GlobalPT-all, a single unbounded global pivot table that retains every query column with no region scoping and no budget limit. Figure 7 overlays cumulative distance computations (solid lines) and cumulative query time (dashed lines) for both methods. On glove100 and sift1m, GlobalPT-all’s solid line (distance computations) is slightly below RECAST’s, but its dashed line (query time) is far above. RECAST accepts a bounded increase in distance computations (geometric mean 1.29×) in exchange for substantially lower query time (geometric mean 0.39×) because scanning a per-region table of K=32 columns is far cheaper than scanning a global table that grows to 1 000 columns. On colors112d (n=112K), the dataset is small enough that GlobalPT-all’s table scan does not dominate, and query times are comparable.

FIFO

LRU

1.5

1.4

1.3

1.26×

1.2

1.1

1.5

1.4

1.3

1.3 1.12×

1.2

1.1

1.0

(e) Residual: Colors/jump 1.5

1.4

1.3

1.06×

1.23×

1.2

1.1

1.0

1.0 200

400

600

800

1000

GlobalPT-all advantage

GlobalPT: 6% fewer DC

GlobalPT: 16% fewer DC

12.5 GlobalPT: 24% fewer DC

2.0

10.0

0.95

1.5

7.5

0.90

1.0

5.0 2.5

0.5

0.0

(d) GloVe-100

(e) SIFT-1M

(f) Colors-112

6 RECAST: 3.2x faster

8 RECAST: 3.1x faster

GlobalPT: 1.2x faster

4 4

3 2

0 500

1000

Query Sequence

500

1000

Query Sequence

500

1000

Query Sequence

1.49×

1.3

1.2

RECAST advantage

(b) SIFT-1M

Fig. 7. Region scoping vs. unbounded global table (jump workload). Top: cumulative distance computations. Bottom: cumulative query time.

(f) Residual: NASA/3-jump

1.5

1.00

GlobalPT-all / RECAST

(a) GloVe-100

0.85

(d) Signal: GloVe/jump

1.5

1.2

Ratio = 1 (same)

0.99×

1.0

Cumulative DC Ratio

No-residual

1.3

1.2

1.0

Cumulative DC Ratio

Unconditional

(b) Pivot: GloVe/jump

DC ratio (GlobalPT / RECAST)

Cumulative DC Ratio

(a) Pivot: Colors/jump

Time ratio (GlobalPT / RECAST)

1.0 = RECAST-full

200

Query Sequence

400

600

800

1000

Query Sequence

Fig. 6. Component ablation. Each panel compares RECAST-full (red) with an ablated variant on cumulative distance computations.

V. R ELATED W ORK We organize related work by whether the index uses query information during construction: methods that build entirely from the data (Section V-A), and methods that build as a side effect of answering queries (Section V-B). A. Data-Driven Indexes for Exact Similarity Search Classical multidimensional indexes such as the KD-tree [17] and the R-tree [18] partition a coordinate space with axisaligned or rectangular regions, and iDistance [19] maps points to a one-dimensional B+ -tree key for nearest-neighbor search. These methods assume that objects carry coordinates. In a general metric space, objects may have no coordinates and an index can prune only through the triangle inequality, using precomputed distances to a set of reference objects [5], [15]. Pivot- and partition-based metric space indexes follow this principle. AESA [6] stores all pairwise distances and achieves near-constant query cost on small datasets; LAESA [7] reduces the storage to a fixed set of pivots, and later work studies how to select pivots that maximize pruning power [22], often

through facility-location heuristics akin to the k-center problem [56]. Tree-structured indexes partition the space around reference objects: VP-tree [10] and MVP-tree [11] split by vantage points, GNAT [8] uses multiple split points per node, SAT [9] navigates by spatial approximation, the M-tree [3] and PM-tree [20] support balanced disk-based access, and cover trees [21] and rank cover trees [45] give worst-case guarantees under bounded intrinsic dimension. Clusteringbased decompositions such as the list of clusters [43] and the scalable M-index [44] group nearby objects to bound the search to a few clusters. Learned indexes such as LIMS [13] use data clustering and pivot-based feature transformations to reduce the candidate set for exact search. Specialized indexes target exact similarity search over data series: SAX-based summaries [64] and variable-length indexes [65] yield tight lower bounds for pruning, recent systems push exact search to scale [29], and progressive variants return refining answers with quality guarantees [30]. In all of these, the partition is fixed at build time from the data distribution; a region that is queried heavily and a region that is never touched receive the same indexing effort, and the structure cannot redirect that effort toward the part of the space the workload actually visits. Some metric space indexes support data updates. EGNAT [23], dynamic spatial approximation trees [24], and the dynamic VP-tree [25] allow incremental insertions and deletions, and D-Cache [26] reuses previously computed distances across queries for pruning. These mechanisms accommodate changes in the data, but the partition structure still reflects the data distribution rather than the query distribution, and is not reorganized when queries concentrate in a particular region. A separate line of work trades exactness for speed: when distances concentrate in high dimensions and exact pruning weakens [16], approximate nearest-neighbor methods such

as locality-sensitive hashing [27] and proximity graphs [28] accept a small recall loss for sublinear query time. RECAST targets exact range search, where every object within the query radius must be returned, so these approximate methods are complementary rather than competing. All of these methods build a fixed structure before any query arrives. In our setting, the index starts empty and must learn its structure from the queries themselves; the query distribution may also shift during execution, which a fixed structure cannot track. B. Adaptive Indexing A second line of work builds the index incrementally as queries arrive, with no separate construction phase. The idea of building structure lazily in response to queries dates back to deferred data structuring [46]. Database cracking [4] brought it to relational columns: each query partitions an unsorted array into progressively finer sorted segments, in effect an incremental quicksort [55] driven by the query predicates, and self-organizing reconstruction extends it to full tuples [39]. A large body of work refined the relational case, adding support for updates [31], convergence through merging [32], [50], robustness to adversarial query orders [14], efficient scan-based reorganization [47], holistic integration with the query optimizer [48], self-tuning index selection [33], variants over encrypted data [49], and systematic analyses of the overhead each query pays [34], [40]. A complementary line bounds the convergence of cracking theoretically [42] and smooths its early-query cost through progressive indexing that spreads the sorting effort across a controlled number of queries [41], [51]. These refinements all target the relational, coordinate-ordered setting, where a total order over key values makes the partition boundaries explicit. Later work extended adaptive indexing to multidimensional coordinate data: cracking KD-trees [35], the query-aware spatial index QUASII [36], multidimensional adaptive and progressive indexes [37], adaptive indexes over objects with spatial extent [38], and recent work on updating such indexes [12]. These methods rely on hyperplane- or coordinatebased partitioning that does not generalize to arbitrary metric spaces, where objects carry no coordinates and only distances are available. The same query-driven philosophy has reached similarity search in other domains: the adaptive data series index builds and refines its structure in response to incoming queries rather than in a separate construction phase [66]. A parallel line of learned indexes replaces index nodes with models that predict key positions [52], [57], [58], [63], with later work supporting updates [53], multi-dimensional [54] and workload-skewed data [59], [60], as part of a broader vision of self-driving database systems [61], [62]. Like cracking, these methods assume a total order or coordinate representation and do not address the metric-space setting. AV-tree [1] advances adaptive indexing from coordinate spaces to generic high-dimensional metric spaces, supporting both exact range and k-NN queries. It uses each query center as a vantage point, cracks the data array around the query

ball, and caches each object’s distance to its parent split pivot for triangle-inequality pruning in later queries. AV-tree demonstrates that the cracking principle can work in metric spaces and achieves per-query cost that converges toward that of pre-built indexes such as MVP-tree after enough queries. AV-tree’s design keeps at most one cached distance per object per leaf, so leaf-level pruning is bounded by a single pivot. Distances computed by earlier queries on ancestor pivots are not carried forward when a leaf is reorganized. This means that a costly query in a region produces distances that are used once for cracking but not accumulated as multi-pivot pruning distances for later queries in the same region. The index also treats every query uniformly: a query that produces reusable distances, a query that indicates the region is already well served, and a query that signals a workload shift all trigger the same cracking operation. CrackIVF [2] applies cracking to approximate nearestneighbor search over IVF indexes, demonstrating that adaptive construction scales to large vector datasets. CrackIVF focuses on the approximate search setting and explicitly scopes out query distribution shifts. RECAST belongs to the adaptive group and differs from prior work in three ways: it partitions only when a region’s cost signal and a shadow test agree the change pays off (Section III-C), rather than before any query [22] or on every qualifying query [1]; it accumulates a region-scoped multi-pivot table from already-paid distances without requiring coordinates (Section III-B); and its residual child keeps every object in a learnable region (Section III-A). VI. C ONCLUSION We have presented RECAST, a region-scoped adaptive index for exact similarity search that treats each query region as a recursive online task. By organizing the distances that queries are forced to compute into region-scoped pruning structures and reading their cost trends as adaptive signals, RECAST adapts its structure to the query stream without a separate construction phase. Experiments on five datasets under four workload patterns showed that RECAST reduced per-query distance computations on all 20 dataset-workload combinations and query time on 16 of 20 compared with AV-tree, with the largest gains under multi-shift workloads and diminishing returns when distance concentration limits pivot-based pruning or when individual distance evaluations are cheap. Ablation studies confirmed that each component contributes to the overall improvement. Extending the costsignal framework to kNN queries, where the effective search radius shrinks dynamically, is a natural next step. ACKNOWLEDGMENTS This work is partially supported by the NSFC project 62532007.

R EFERENCES [1] K. Lampropoulos, F. Zardbani, N. Mamoulis, and P. Karras, “Adaptive indexing in high-dimensional metric spaces,” Proc. VLDB Endow., vol. 16, no. 10, pp. 2525–2537, 2023. [2] V. Mageirakos, B. Wu, and G. Alonso, “Cracking vector search indexes,” Proc. VLDB Endow., vol. 18, no. 11, pp. 3951–3964, 2025. [3] P. Ciaccia, M. Patella, and P. Zezula, “M-tree: An efficient access method for similarity search in metric spaces,” in Proc. VLDB, 1997, pp. 426– 435. [4] S. Idreos, M. L. Kersten, and S. Manegold, “Database cracking,” in Proc. CIDR, 2007, pp. 68–78. [5] L. Chen, Y. Gao, X. Song, Z. Li, Y. Zhu, X. Miao, and C. S. Jensen, “Indexing metric spaces for exact similarity search,” ACM Comput. Surv., vol. 55, no. 6, pp. 128:1–128:39, 2023. [6] E. Vidal, “An algorithm for finding nearest neighbours in (approximately) constant average time,” Pattern Recognit. Lett., vol. 4, no. 3, pp. 145–157, 1986. [7] M. L. Micó, J. Oncina, and E. Vidal, “A new version of the nearestneighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements,” Pattern Recognit. Lett., vol. 15, no. 1, pp. 9–17, 1994. [8] S. Brin, “Near neighbor search in large metric spaces,” in Proc. VLDB, 1995, pp. 574–584. [9] G. Navarro, “Searching in metric spaces by spatial approximation,” VLDB J., vol. 11, no. 1, pp. 28–46, 2002. [10] P. N. Yianilos, “Data structures and algorithms for nearest neighbor search in general metric spaces,” in Proc. SODA, 1993, pp. 311–321. [11] T. Bozkaya and M. Ozsoyoglu, “Indexing large metric spaces for similarity search queries,” ACM Trans. Database Syst., vol. 24, no. 3, pp. 361–404, 1999. [12] F. Zardbani, K. Lampropoulos, N. Mamoulis, and P. Karras, “Updating an adaptive spatial index,” in Proc. ICDE, 2025, pp. 1194–1206. [13] Y. Tian, T. Yan, X. Zhao, K. Huang, and X. Zhou, “A learned index for exact similarity search in metric spaces,” IEEE Trans. Knowl. Data Eng., vol. 35, no. 8, pp. 7624–7638, 2023. [14] F. Halim, S. Idreos, P. Karras, and R. H. C. Yap, “Stochastic database cracking: towards robust adaptive indexing in main-memory columnstores,” Proc. VLDB Endow., vol. 5, no. 6, pp. 502–513, 2012. [15] E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquı́n, “Searching in metric spaces,” ACM Comput. Surv., vol. 33, no. 3, pp. 273–321, 2001. [16] K. S. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft, “When is ‘nearest neighbor’ meaningful?” in Proc. ICDT, 1999, pp. 217–235. [17] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. ACM, vol. 18, no. 9, pp. 509–517, 1975. [18] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proc. ACM SIGMOD, 1984, pp. 47–57. [19] H. V. Jagadish, B. C. Ooi, K.-L. Tan, C. Yu, and R. Zhang, “iDistance: An adaptive B+ -tree based indexing method for nearest neighbor search,” ACM Trans. Database Syst., vol. 30, no. 2, pp. 364–397, 2005. [20] T. Skopal, J. Pokorný, and V. Snášel, “PM-tree: Pivoting metric tree for similarity search in multimedia databases,” in Proc. ADBIS, 2004, pp. 803–815. [21] A. Beygelzimer, S. Kakade, and J. Langford, “Cover trees for nearest neighbor,” in Proc. ICML, 2006, pp. 97–104. [22] L. Chen, Y. Gao, B. Zheng, C. S. Jensen, H. Yang, and K. Yang, “Pivotbased metric indexing,” Proc. VLDB Endow., vol. 10, no. 10, pp. 1058– 1069, 2017. [23] R. Uribe, G. Navarro, R. J. Barrientos, and M. Marı́n, “An index data structure for searching in metric space databases,” in Proc. ICCS, 2006, pp. 611–617. [24] G. Navarro and N. Reyes, “Dynamic spatial approximation trees,” ACM J. Exp. Algorithmics, vol. 12, pp. 1.5:1–1.5:68, 2008. [25] A. W.-C. Fu, P. M.-S. Chan, Y.-L. Cheung, and Y. S. Moon, “Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances,” VLDB J., vol. 9, no. 2, pp. 154–173, 2000. [26] T. Skopal, J. Lokoč, and B. Bustos, “D-Cache: Universal distance cache for metric access methods,” IEEE Trans. Knowl. Data Eng., vol. 24, no. 5, pp. 868–881, 2012. [27] A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high dimensions via hashing,” in Proc. VLDB, 1999, pp. 518–529. [28] Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world

graphs,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 42, no. 4, pp. 824– 836, 2020. [29] K. Echihabi, P. Fatourou, K. Zoumpatianos, T. Palpanas, and H. Benbrahim, “Hercules against data series similarity search,” Proc. VLDB Endow., vol. 15, no. 10, pp. 2005–2018, 2022. [30] K. Echihabi, T. Tsandilas, A. Gogolou, A. Bezerianos, and T. Palpanas, “ProS: Data series progressive k-NN similarity search and classification with probabilistic quality guarantees,” VLDB J., vol. 32, no. 4, pp. 763– 789, 2023. [31] S. Idreos, M. L. Kersten, and S. Manegold, “Updating a cracked database,” in Proc. ACM SIGMOD, 2007, pp. 413–424. [32] S. Idreos, S. Manegold, H. Kuno, and G. Graefe, “Merging what’s cracked, cracking what’s merged: Adaptive indexing in main-memory column-stores,” Proc. VLDB Endow., vol. 4, no. 9, pp. 585–597, 2011. [33] G. Graefe and H. Kuno, “Self-selecting, self-tuning, incrementally optimized indexes,” in Proc. EDBT, 2010, pp. 371–381. [34] F. M. Schuhknecht, A. Jindal, and J. Dittrich, “The uncracked pieces in database cracking,” Proc. VLDB Endow., vol. 7, no. 2, pp. 97–108, 2013. [35] P. Holanda, M. Nerone, E. C. de Almeida, and S. Manegold, “Cracking KD-tree: The first multidimensional adaptive indexing,” in Proc. DATA, 2018, pp. 393–399. [36] M. Pavlovic, D. Sidlauskas, T. Heinis, and A. Ailamaki, “QUASII: Query-aware spatial incremental index,” in Proc. EDBT, 2018, pp. 325– 336. [37] M. A. Nerone, P. Holanda, E. C. de Almeida, and S. Manegold, “Multidimensional adaptive & progressive indexes,” in Proc. ICDE, 2021, pp. 624–635. [38] F. Zardbani, N. Mamoulis, S. Idreos, and P. Karras, “Adaptive indexing of objects with spatial extent,” Proc. VLDB Endow., vol. 16, no. 9, pp. 2248–2260, 2023. [39] S. Idreos, M. L. Kersten, and S. Manegold, “Self-organizing tuple reconstruction in column-stores,” in Proc. ACM SIGMOD, 2009, pp. 297–308. [40] F. M. Schuhknecht, A. Jindal, and J. Dittrich, “An experimental evaluation and analysis of database cracking,” VLDB J., vol. 25, no. 1, pp. 27– 52, 2016. [41] P. Holanda, S. Manegold, H. Mühleisen, and M. Raasveldt, “Progressive indexes: Indexing for interactive data analysis,” Proc. VLDB Endow., vol. 12, no. 13, pp. 2366–2378, 2019. [42] F. Zardbani, P. Afshani, and P. Karras, “Revisiting the theory and practice of database cracking,” in Proc. EDBT, 2020, pp. 415–418. [43] E. Chávez and G. Navarro, “A compact space decomposition for effective metric indexing,” Pattern Recognit. Lett., vol. 26, no. 9, pp. 1363– 1376, 2005. [44] D. Novak, M. Batko, and P. Zezula, “Metric index: An efficient and scalable solution for precise and approximate similarity search,” Inf. Syst., vol. 36, no. 4, pp. 721–733, 2011. [45] M. E. Houle and M. Nett, “Rank cover trees for nearest neighbor search,” in Proc. SISAP, 2013, pp. 16–29. [46] R. M. Karp, R. Motwani, and P. Raghavan, “Deferred data structuring,” SIAM J. Comput., vol. 17, no. 5, pp. 883–902, 1988. [47] H. Pirk, E. Petraki, S. Idreos, S. Manegold, and M. L. Kersten, “Database cracking: Fancy scan, not poor man’s sort!” in Proc. DaMoN, 2014, pp. 4:1–4:8. [48] E. Petraki, S. Idreos, and S. Manegold, “Holistic indexing in mainmemory column-stores,” in Proc. ACM SIGMOD, 2015, pp. 1153–1166. [49] P. Karras, A. Nikitin, M. Saad, R. Bhatt, D. Antyukhov, and S. Idreos, “Adaptive indexing over encrypted numeric data,” in Proc. ACM SIGMOD, 2016, pp. 171–183. [50] P. Holanda and S. Manegold, “Progressive mergesort: Merging batches of appends into progressive indexes,” in Proc. EDBT, 2021, pp. 481–486. [51] A. H. Jensen, F. Lauridsen, F. Zardbani, S. Idreos, and P. Karras, “Revisiting multidimensional adaptive indexing,” in Proc. EDBT, 2021, pp. 469–474. [52] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” in Proc. ACM SIGMOD, 2018, pp. 489–504. [53] J. Ding, U. F. Minhas, J. Yu, C. Wang, J. Do, Y. Li, H. Zhang, B. Chandramouli, J. Gehrke, D. Kossmann, D. Lomet, and T. Kraska, “ALEX: An updatable adaptive learned index,” in Proc. ACM SIGMOD, 2020, pp. 969–984. [54] V. Nathan, J. Ding, M. Alizadeh, and T. Kraska, “Learning multidimensional indexes,” in Proc. ACM SIGMOD, 2020, pp. 985–1000. [55] C. A. R. Hoare, “Algorithm 64: Quicksort,” Commun. ACM, vol. 4, no. 7, p. 321, 1961.

[56] D. S. Hochbaum and D. B. Shmoys, “A best possible heuristic for the k-center problem,” Math. Oper. Res., vol. 10, no. 2, pp. 180–184, 1985. [57] A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska, “FITing-Tree: A data-aware index structure,” in Proc. ACM SIGMOD, 2019, pp. 1189–1206. [58] P. Ferragina and G. Vinciguerra, “The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds,” Proc. VLDB Endow., vol. 13, no. 8, pp. 1162–1175, 2020. [59] J. Ding, V. Nathan, M. Alizadeh, and T. Kraska, “Tsunami: A learned multi-dimensional index for correlated data and skewed workloads,” Proc. VLDB Endow., vol. 14, no. 2, pp. 74–86, 2020. [60] R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska, “Benchmarking learned indexes,” Proc. VLDB Endow., vol. 14, no. 1, pp. 1–13, 2020. [61] A. Pavlo, G. Angulo, J. Arulraj, H. Lin, J. Lin, L. Ma, P. Menon, T. C. Mowry, M. Perron, I. Quah, S. Santurkar, A. Tomasic, S. Toor, D. V. Aken, Z. Wang, Y. Wu, R. Xian, and T. Zhang, “Self-driving database management systems,” in Proc. CIDR, 2017. [62] T. Kraska, M. Alizadeh, A. Beutel, E. H. Chi, A. Kristo, G. Leclerc, S. Madden, H. Mao, and V. Nathan, “SageDB: A learned database system,” in Proc. CIDR, 2019. [63] A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann, “RadixSpline: A single-pass learned index,” in Proc. aiDM@SIGMOD, 2020, pp. 5:1–5:5. [64] A. Camerra, T. Palpanas, J. Shieh, and E. J. Keogh, “iSAX 2.0: Indexing and mining one billion time series,” in Proc. IEEE ICDM, 2010, pp. 58– 67. [65] M. Linardi and T. Palpanas, “Scalable, variable-length similarity search in data series: The ULISSE approach,” Proc. VLDB Endow., vol. 11, no. 13, pp. 2236–2248, 2018. [66] K. Zoumpatianos, S. Idreos, and T. Palpanas, “ADS: The adaptive data series index,” VLDB J., vol. 25, no. 6, pp. 843–866, 2016.

RECAST: A Region-Scoped Adaptive Index for Exact Similarity Search

Analyze & explore related research in Conceptio

Related documents