App2Exa: Accelerating Exact kNN Search via Dynamic Cache-Guided Approximation

1 Introduction

The k-nearest-neighbor (kNN) query is widely employed in similarity-based tasks across various domains, such as image retrieval [Peng et al., 2022], web search [Bae et al., 2009], and recommendation [Halder et al., 2024]. Let V represent a finite set of vectors in a d-dimensional space, and dist(·) denote a distance function between two vectors. Given a query vector vq and a positive integer k, the kNN query identifies k vectors v ∈ V such that dist(v, vq) is smaller than that of all other vectors in V.

The efficiency of kNN search can be greatly enhanced through indexing techniques. For exact kNN search, treebased indexes such as KD-trees [Bentley, 1975] and VPtrees [Yianilos, 1993] are widely used. However, as vector dimensionality increases, the efficiency of exact search declines due to the "curse of dimensionality" [Beyer et al., 1999].

∗Corresponding author.

↑ Dimension

* Ensure exact result

Table 1: Overview of kNN algorithms

In high-dimensional vectors space, graph-based approaches like kGraph [Dong et al., 2011] and HNSW [Malkov and Yashunin, 2020] have emerged as popular alternatives. Table 1 provides a comparison of representative indexing methods alongside the approach proposed in this work. While extensive research has focused on improving the efficiency of kNN search, efforts to support higher dimensionality while ensuring exact results remain limited. Moreover, most existing methods assume static query and data distributions, offering minimal consideration for scenarios involving periodic or dynamic updates. In many real-world applications [Li et al., 2023; Li et al., 2022], query distributions evolve over time (e.g., varying hot queries) while the database of object vectors remains static. Certain object vectors experience periods of high-frequency queries due to evolving user needs or external factors. For instance, medical articles may receive frequent queries during health crises (e.g., the COVID-19 pandemic or flu season), user interests in travel destinations may fluctuate seasonally, and students or educators focus on specific topics during exams or trending research periods. Advancements in embedding techniques now enable such content to be efficiently transformed into feature vectors for similaritybased computations. In these dynamic scenarios, obtaining exact kNN results becomes critical for ensuring accurate and reliable outcomes.

Caching is commonly employed to store the results of frequently occurring queries, which enables "hot" queries to be answered directly, thereby reducing the amount of computation and improving query latency [Zulfa et al., 2020]. Fig. 1 illustrates the speed-up achieved by our cache-guided approach on the SIFT dataset used in our experiments. By leveraging approximate kNN results with a cache update factor ϵ (cf. Alg. 3), our method delivers a substantial performance boost, potentially allowing exact kNN search to handle higher dimensionality more efficiently. While caching is widely used in web search scenarios, there are important differences between general web search and vector kNN search in terms of query matching and cost variation. In web search, results from one query are considered a match to another if they share the same value (e.g., identical text), as exact matching is required. In contrast, for embedding vectors, exact matches are nearly impossible. In kNN queries, results are considered a match if their similarity ratio exceeds a predefined threshold. When a cache miss occurs, additional computation is required to obtain the query result, and some results can be significantly more costly to compute than others. To optimize query performance, it is crucial to develop a cost (or benefit) model that estimates the evaluation cost of a query. However, to the best of our knowledge, no prior work has addressed cost estimation for kNN queries within the context of any index structure.

To address these gaps, we propose a cache-guided approach called App2Exa, which bridges approximate and exact kNN search to improve efficiency (cf. Table 1). Initially, approximate kNN results are retrieved from dynamically maintained cached object vectors, supported by a tailored cache graph index. A benefit model for caching vectors is proposed, along with a benefit-driven cache (BDC) replacement algorithm. These results are then reused to accelerate exact kNN search using a VP-Tree index with a bestfirst strategy. Empirical results on real datasets show that App2Exa consistently outperforms the VP-Tree approach by at least 3x when using the BDC policy. Our method is particularly effective in environments where certain object vectors experience high-frequency retrieval during specific periods, while exact kNN results are still required. The main contributions of this paper can be summarized as follows.

• We introduce a benefit-driven caching mechanism that prioritizes vectors based on query frequency, recency, and computational cost, coupled with an incremental cache graph index to enhance retrieval efficiency.
• We develop a best-first strategy tailored for the VP-Tree, which cooperates with a guided distance to prune unqualified objects at an early stage.
• We propose App2Exa, a novel cache-guided approach that bridges approximate and exact kNN search to enhance efficiency.
• We conduct extensive experiments 1 , demonstrating that our proposal significantly accelerates kNN search, with

1 The implementation is available at https://github.com/ likemelike/App2ExaCache.git.

the benefit-driven cache performing as an optimal caching policy.

2 RelatedWork

2.1 The k Nearest Neighbor Search Problem

The kNN search problem is a fundamental component of similarity-based query tasks and has garnered significant attention from the data science community. Various approaches have been proposed to address this problem, including treebased [Ram and Sinha, 2019], hash-based [Zhao et al., 2023; Zheng et al., 2022], and graph-based methods [Malkov and Yashunin, 2020]. As vector dimensionality increases, exact kNN search becomes increasingly challenging for two main reasons. First, the curse of dimensionality causes data points to become more uniformly distributed, making it harder to distinguish true neighbors, thereby reducing the meaningfulness of similarity search [Beyer et al., 1999; Babenko and Lempitsky, 2016]. Second, traditional indexing methods, such as R-trees [Guttman, 1984] and KD-trees [Bentley, 1975], perform poorly in high dimensions. These methods divide the data space into orthotopes but struggle to effectively separate objects in high-dimensional spaces. Pivot-based indexes, such as the VP-Tree [Yianilos, 1993], are better suited for exact similarity search in metric spaces. The VP-Tree hierarchically partitions data based on a vantage point at each node and leverages the triangle inequality to prune irrelevant regions during search. The MVP-Tree [Bozkaya and ¨Ozsoyoglu, 1999] extends the VP-Tree by generalizing it to an m-ary structure. It organizes objects based on their distance to the vantage point, partitioning them into m groups of equal size. During search, the mean distance of each group is used to efficiently prune unqualified sub-trees, improving search performance in high-dimensional spaces. A recent study [Lampropoulos et al., 2023] considers short-lived object vectors with limited queries before obsolescence. However, no existing research addresses varied query distributions for exact kNN in vector space. In contrast, LSH-based indexes [Liu et al., 2021] are not well-suited for scenarios requiring exact search. More recently, graph-based solutions such as HNSW and MRNG [Fu et al., 2019] have been proposed to ensure connectivity and enable efficient routing in poly-logarithmic time. However, these methods lack error guarantees on search results, making them unsuitable for directly answering exact kNN queries.

2.2 Cache Replacement Policies

Caching is widely used in web search engines to retrieve the top-k relevant documents (e.g., web pages) that match a text query. Maintaining a cache can be costly and may not be worthwhile if queries are evenly distributed. However, it is particularly effective when a small number of queries dominate in frequency and remain popular for a period of time [Frieder et al., 2024]. Existing caching strategies can be classified into dynamic caching [Markatos, 2001; Long and Suel, 2006; Gan and Suel, 2009; Cambazoglu et al., 2010] and static caching [Baeza-Yates et al., 2007]. Dynamic caching stores results of recently accessed queries and adapts quickly to changing query patterns. For example, the LeastRecently-Used (LRU) method [Jelenkovic and Radovanovic, 2004] replaces the least recently used result with the current query result upon a cache miss, while the First-In-FirstOut (FIFO) replacement policy evicts the oldest cached result regardless of access patterns. Techniques like LeastFrequently-Used (LFU) replacement [Lee et al., 2001] analyze past query logs to identify and cache queries that dominate in frequency. Although these approaches adapt well to dynamic query distributions, they may incur frequent update overhead for kNN vector search. Static caching [Ozcan et al., 2012], on the other hand, focuses on storing results for the most popular queries based on historical data, which are updated periodically (e.g., daily).

3 Preliminaries

Let V be a finite vector set in a d-dimensional vector space Rd , and dist be a distance metric. For two vectors v, v′ ∈ V, the distance metric is typically the Euclidean distance, i.e.,

dist(v, v′ ) = √∑di=1 (v[i] - v′ [i])2 . Table 2 summarizes the notations frequently used throughout the paper.

k-nearest-neighbor (kNN) query. Given a query vector vq ∈ V and a positive integer k, a k-nearest-neighbor query problem returns a subset R ⊆ V, such that |R| = k and ∀v ∈ R, ∀v′ ∈ V \ R, dist(v, vq) ≤ dist(v′ , vq).

k-approximate-nearest-neighbor (kANN) query. Given a query vector vq ∈ V and a positive integer k, the kapproximate-nearest-neighbor (kANN) query returns a set R′ that is approximated to R, which contains a proportion of ground-truth answers in R.

In our setting, we assume that the query distribution evolves periodically, with certain object vectors being frequently retrieved as kNN results. The vector cache, as defined below, can be placed either at a proxy or the server. It optimizes the computation of approximate kNN searches and subsequently reduces the response time for exact queries.

Vector cache. Given a cache budget B, a vector cache C is a subset of V such that |C| ≤ B, where |C| denotes the total number of vectors in the cache.

4 App2Exa: ACache-Guided Approach

In this section, we introduce App2Exa, a cache-guided approach designed to accelerate the exact computation of kNN queries in the context of evolving query distributions. Fig. 2 illustrates the overall framework of our proposal, which consists of three main components: cache-guided approximate kNN search, exact kNN search, and a dynamically updated, benefit-driven caching mechanism. Given a query vq and a positive integer k, the high-level process of our approach is as follows. First, we retrieve approximate kNN results for the query vector vq, denoted as R′ , from the dynamically maintained cache of vectors. To ensure efficient search, we develop an incremental cache graph index and apply a benefitdriven caching strategy to optimize the results. The maximum distance between any vector in R′ and vq, denoted as dg, is then determined. Next, we perform the exact kNN search using an improved VP-Tree. The guide value dg is used to effectively prune the VP-Tree search space, and a best-first strategy is employed to further enhance efficiency. Finally, we obtain the exact kNN results, denoted as R. The maximum distance between any vector in R and vq is denoted as dk. Based on the approximate ratio between R and R′ , the cache and the cache graph index is dynamically updated. Specifically, if the approximate ratio meets or exceeds a given threshold ϵ, we update the cache using a benefit-driven replacement policy.

4.1 Cache-Guided Approximate kNN Search Incremental Cache Graph Index

We investigate the cache index structure, focusing on maximizing speed-up and efficiently supporting dynamic updates while ensuring fast result retrieval. To achieve this, we propose an incremental cache graph index, denoted as G(C, lmax,M(l, v),m). Here, C represents the vector cache and lmax denotes the maximum layer. The functionM(l, v) maps each vector v to its connections at a specific layer l, with a maximum of m connections. As illustrated in the bottomleft of Fig. 2, the structure forms a multi-layered graph, where each layer corresponds to a subset of nodes with progressively decreasing density and connectivity as the layers ascend. Our proposal aligns with established practices from prior studies [Malkov and Yashunin, 2020], adopting a multi-layered structure, approximate kNN search, and graph connections.

Algorithm 1 Insert(v)

Input: A vector to be added, v; Output: The updated graph index, G; 1: Let lrandom be the assigned level; 2: R′ ←PriorityQueue(); 3: for l = lrandom; l ≥ 0; l -- do 4: R′ ← find AkNN(v,m, l,R′ ); 5: connect(v,R′ , l); ▷ Record connections of v 6: return G;

Algorithm 2 Delete(v, v′ )

Input: A vector to be removed, v; A vector to repair connections, v′ ; Output: The updated graph index, G;

1: C.remove(v); 2: for l = 0 : lmax -1 do 3: if M(l, v) ̸= ∅ then 4: M(l, ·).remove(v); 5: for vn ∈ v.connections do 6: if M(l, vn) ̸= ∅ then 7: M(l, vn).remove(v); 8: M(l, vn).add(v′ );

9: return G;

Innovatively, we introduce Algorithms 1 and 2 to enable dynamic insertion and deletion of vectors, respectively.

Insert algorithm details. Algorithm 1 demonstrates the insertion process, where a vector v is added by traversing the graph from a random maximum layer (Line 1) downward to identify the closest entry point. At each layer, v is connected to its m-nearest-neighbors, and these connections are recorded (Lines 3-5). The find AkNN(·) and connect(·) functions are consistent with approaches outlined in prior work [Malkov and Yashunin, 2020].

Delete algorithmdetails. Algorithm2 presents the pseudo code for the delete operation. Unlike prior studies, the inputs include both the vector to be removed and a vector used to repair connections. First, the vector v is removed from the cache C (Line 1). Subsequently, all connections involving v are deleted (Lines 4, 7), and these edges are repaired by establishing new connections with v′ (Line 8).

Benefit-Driven Cache Replacement

In web search scenarios, if a new query matches cached historical results, the result is immediately returned to the user. Therefore, the objective of cache designs (e.g., LRU, LFU, FIFO) is to maximize the cache hit ratio. When the cache reaches budget, LRU evicts the least recently used result, LFU removes the least frequently used result, and FIFO evicts the oldest result to make room. However, in the context of kNN search, maximizing the cache hit ratio does not necessarily minimize the overall computation cost, as each cache miss incurs a distinct and often significant computational overhead. Existing cache replacement policies fail to effectively quantify the benefit of a completed kNN query. Furthermore, the importance of a vector may inherently depend on its characteristics and should decay over time.

Motivated by these limitations, we propose a benefit-driven approach to identify which queried vectors should be prioritized for caching.

Benefit model. Abenefit model is proposed to evaluate the caching potential of vectors for future queries, which considers three key factors: (i) query frequency (F), (ii) processing cost (E), which refers to the distance computation count, and (iii) recency of the object vector (R). The normalization factors max(F), max(E), and max(T) are computed for global normalization across the dataset. The benefit value of a vector v is computed using Equation 1, where F ′ (v), R′ (v), and E′ (v) represent the normalized query frequency, recency (i.e., inverted time decay), and computation cost, respectively. Parameters α, β, and γ are adjustable weights that reflect the relative importance of each metric, subject to the constraint α + β + γ = 1. The values of F ′ (v), R′ (v), and E′ (v) are determined using Equation 2, where T(v) denotes the time elapsed since the last access of v.

Compared to the replacement methods discussed earlier, our benefit model offers distinct advantages. While frequency prioritizes frequently accessed queries and recency emphasizes recently accessed ones, computation cost ensures that queries with high computational overhead are prioritized to minimize recomputation. By integrating these factors, the model effectively ranks cached vectors, balancing the tradeoffs between frequency, recency, and computational cost.

Benefit-Driven cache algorithm. Algorithm 3 outlines the pseudo-code for the benefit-driven cache replacement algorithm. A cache update is triggered if the cache size exceeds the budget B and the ratio dg/dk is greater than or equal to the specified update factor ϵ, where dg and dk represent the maximum distances of the approximate results R′ and exact results R to the query, respectively. When the condition dg/dk ≥ ϵ is satisfied, the cache is updated by adding vector v to C and inserting v into the graph G (Line 4). If a cache update occurs, the cached vector v with the minimal benefit is identified (Line 6). This vector is then removed from the cache, and all its connections in G are deleted (Line 7).

4.2 Exact Search with Distance Guidance

For exact search, the distance dg (cf. Section 4.1) is utilized to prune unqualified objects early on. Specifically, we use the VP-Tree as the underlying index structure for exact kNN search due to its superior efficiency and minimal memory requirements compared to ball-trees [Rakotondrasoa et al., 2023; Kumar et al., 2008]. Notably, our approach is compatible with other tree-based solutions as well. As illustrated in Fig. 2, each node in the VP-Tree is represented as N = {pt(left), vp, µ, I, pt(right)}. Here, vp denotes the vantage point, I represents the vector items stored in a leaf node, and pt() serves as a pointer to child nodes. For nonleaf nodes, I remains empty. Starting at the root node Nr,

Algorithm 3 BDC(R, R′ , G, B, ϵ)

Input: The exact / approximate kNN results, R and R′ ; The cache graph index, G; Parameter: The cache budget, B; The cache update factor, ϵ; Output: The updated cache graph index, G; 1: dg =R′ .top(); dk =R.top(); 2: if dg/dk ≥ ϵ then 3: for v′ ∈ R do 4: G.Insert(v′ ); 5: if |C| > B then 6: v ← a cached vector with the minimal benefit; 7: G.Delete(v, v′ ); 8: return G;

which indexes all data, each node N selects a vantage object vp from the data indexed at that node. The data are then split into two partitions: the medium distance µ to vp is calculated for all points under N. Objects with a distance to vp less than µ are assigned to the left subtree, while those with a distance greater than or equal to µ are placed in the right subtree. To evaluate a kNN query, the VP-Tree is traversed recursively following the same partitioning principle.

Algorithm details. Algorithm 4 provides the pseudo code for kNN search using the VP-Tree with a best-first strategy (BF-kNN). The inputs to the algorithm include the starting node of the VP-Tree N, a query vector vq, and a cacheguided distance dg. A priority queue, denoted as R, is used to store the exact kNN results in descending order of their distances. The kNN search follows a recursive traversal process that begins at the root of the tree and progressively updates the result set R. Upon reaching a bucket (i.e., a leaf node), the elements within the bucket are searched sequentially (Lines 3-11). The cache-guided distance dg is utilized to prune unqualified candidates early in the search process (Line 9). In a metric space with the distance dist(v, vq), the triangle inequality is employed to reduce the search space. Specifically, only the left subtree is visited if dist(v, vq) < N.µ -min(dk, dg). Similarly, only the right subtree is explored if dist(v, vq) > N.µ +min(dk, dg). In cases where N.µ - min(dk, dg) ≤ dist(v, vq) ≤ N.µ + min(dk, dg), both subtrees must be visited. The high-level concept of our cache-guided best-first strategy in the VP-Tree is as follows: (i) Cache-guided: Instead of relying solely on the maximum distance among the current kNN results, we incorporate min(dk, dg) to guide the search, enabling early-stage pruning of the search space. (ii) Best-first: If dist(v, vq) < N.µ, the left subtree is prioritized for traversal; otherwise, the right subtree is explored first (Lines 14-23).

4.3 Overall Solution: Cache-Guided Search

The overall cache-guided search algorithm (CGS) is presented in Algorithm 5. Initially, the cache graph index G is empty (Line 1). The algorithm starts with a greedy search from a random entry point in the top layer of the cache graph index, progressively moving closer to the query point through each layer until the bottom layer is reached. At this stage, the

Algorithm 4 BF-kNN(vq , N , R, dg , k)

Input: A query vector, vq; A node of the VP-Tree, N; The exact kNN results, R; A cache-guided distance, dg; Parameter: The query result quantity, k; Output: The exact kNN results, R; 1: if N = null then 2: return; 3: if N.I ̸= ∅ ▷ Leaf Node then 4: for v ∈ N.I do 5: if |R| < k then 6: R.push([v, dist(v, vq)]; 7: else 8: dk ← R.top(); 9: if dist(v, vq) < min(dk, dg) then 10: R.poll(); 11: R.push([v, dist(v, vq)]); 12: v ←N.vp; 13: The same as Lines 5-11; 14: if dist(v, vq) <N.µ ▷ Best-First then 15: if dist(v, vq) - N .µ ≤ min(dk, dg) then 16: BF-kNN(vq , N .lef t, R, dg , k); 17: if N .µ - dist(v, vq) ≤ min(dk, dg) then 18: BF-kNN(vq , N .right, R, dg , k); 19: else 20: if N .µ - dist(v, vq) ≤ min(dk, dg) then 21: BF-kNN(vq , N .right, R, dg , k); 22: if dist(v, vq) - N .µ ≤ min(dk, dg) then 23: BF-kNN(vq , N .lef t, R, dg , k); 24: return R;

top k approximate nearest neighbors R′ and the guiding distance dg are identified (Lines 2-5). In the exact search phase, the guide distance dg is used to effectively prune the VP-Tree search space (Line 6). Based on the ratio between R and R′ , the cache is dynamically updated (Line 7). Finally, the exact kNN results, R, are returned (Line 8).

5 Experiments

5.1 Experimental Setup

Data preparation. We conducted experiments on two real-world datasets to evaluate the performance of our proposal: SIFT 2 and AOL. The SIFT dataset comprises SIFT image descriptors, which are widely used in feature matching applications. The AOL dataset consists of approximately 20 million web queries collected from 650,000 users over three months [Pass et al., 2006]. The data is organized by anonymous user IDs and sequentially arranged. For the AOL dataset, we use the word2vec technique described in [ ˇReh˚uˇrek and Sojka, 2010] to convert each query text into 10-dimensional vectors by default. To simulate evolved query distributions in SIFT, we use KMeans clustering [Kanungo et al., 2002] to reorder the queries. We treat the embedding and clustering process as a black-box mechanism, and optimizing the vector embeddings themselves is beyond the scope of our study. Both the cache graph index and the VP-Tree are kept

2 http://corpus-texmex.irisa.fr

Algorithm 5 CGS(vq , Nr , G, k, B, ϵ)

Input: A query vector, vq;

The root node of the VP-Tree, Nr;

The cache graph index, G;

Parameter: The query result quantity, k;

The cache budget, B;

The cache update factor, ϵ;

Output: The exact kNN results, R;

• 1: Init: G ← ∅;
• 2: R′ ←PriorityQueue(),R←PriorityQueue();
• 3: for l = lmax -1; l ≥ 0; l -- do
• 4: R′ ←G.find AkNN(vq, k, l,R′ );
• 5: dg ←R′ .top();
• 6: R←BF-kNN(vq,Nr,R, dg, k);
• 7: C ←BDC(R,R′ , G,B, ϵ);

• 8: return R;

in memory. By default, we randomly select 30,000 vectors as query vectors Q and 300,000 vectors as object vectors V.

Compared algorithms. We evaluate the performance of the following proposed methods. For approximate kNN search, we employ the cache graph index with four caching strategies: the Least-Recently-Used (LRU) strategy, First-InFirst-Out (FIFO) strategy, the Least-Frequently-Used (LFU) strategy, and the Benefit-Driven Cache (BDC) strategy, denoted as App2Exa-LRU, App2Exa-FIFO, App2Exa-LFU, and App2Exa-BDC, respectively. To validate the best-first strategy on the VP-Tree for exact search, we compare the performance of App2Exa-BDC with and without the best-first strategy. The latter is referred to as App2Exa-BDC#. Efficiency is evaluated by measuring the speed-up, computed as t0 t , where t0 is the query time of the VP-Tree without caching, and t represents the query time when specific caching strategy. For instance, if an App2Exa based solution takes 1 second to process a query while the original VP-Tree without caching takes 10 seconds, the resulting speed-up is 10.

Parameter settings. The evaluation parameter settings are listed in Table 3. For the adjustable parameters α, β and γ in Equation 1, the default values are set to be equal (e.g., 1/3). All the methods are implemented in Java and evaluated on Ubuntu equipped with 2 Intel(R) Xeon(R) Silver 4214R CPU @ 2.40GHz and 128GB memory, utilizing a single thread for execution. Unless otherwise specified, the reported experimental results represent the averages of 20 independent trials.

Note that when we vary one parameter, the others are set to default values.

5.2 Performance Evaluation

Effect of the number of queries. First, we evaluate the speed-up performance of the proposed methods by varying the number of queries from 10,000 to 50,000. Fig. 3 illustrates the speed-up performance across different settings. Using our App2Exa techniques, the exact VP-Tree search achieves a speed-up of at least 2x for SIFT dataset, and 1.5x for AOL dataset. It is observed that App2Exa-BDC consistently achieves the best performance among all methods for all settings, which accelerates the exact search on VP-Tree by at least 3x for SIFT, and 2.5x for AOL. The similar performance of FIFO and LRU stems from the fact that both rely solely on recency for cache replacement, and thus behave similarly in our scenarios. These experimental results demonstrate the superiority of our proposal.

Effect of the database size. Fig. 4 presents the speedup performance of the proposed methods when varying the data cardinality from 100,000 to 500,000. In SIFT dataset, all methods achieve the best performance when the cardinality is 300,000. We can observe that the App2Exa approach with our BDC cache replacement policy, consistently outperforms all other methods, significantly accelerating the exact computation by a factor of 3.2x-4.4x in SIFT dataset, demonstrating the capability of our proposal in handling large data sets.

Effect of the k. We examine the impact of the k - the results are shown in Fig. 5. Intuitively, a larger k results in more nearest neighbors, in which more vectors are required to be computed. Additionally, as k increases, the distance between the query and its k-th nearest neighbor becomes larger.

This, in turn, causes the VP-Tree to have a wider initial search range for exact k-NN search, thereby requiring more computational effort. All methods achieves their best performance at k = 5, with the speed-up stabilizing for k > 20. As k increases, App2Exa-BDC still provides significant speed-up by at least 3.5x for SIFT dataset, and 3x for AOL dataset, demonstrating its scalability across various application scenarios with different k values.

Effect of the cache budget. Fig. 6 shows the speed-up performance as a function of the cache budget B. Specifically, B ranges from 0.5% to 2.5% of the size of object vectors (i.e., database). An increasing trend of the speed-up ratio is observed across all methods as B increases. Notably, due to the effects of data distribution, the speed-up in the AOL dataset increase at a slower rate compared to SIFT. Among the evaluated methods, App2Exa-BDC, which incorporates an effective cache replacement policy in approximate search phase and employs the best-first strategy in the exact search phase using the VP-Tree, consistently outperforms others across all datasets. Specifically, App2Exa-BDC achieves a speed-up exceeding 4x for SIFT and 2.6x for AOL, highlighting the effectiveness of our proposed approach.

Effect of the cache update factor. Fig. 7 shows the speedup performance when varying the cache update factor ϵ (cf. Alg. 3). A larger value of ϵ results in fewer cache replacement. As ϵ increases, the methods with LRU, BDC, and FIFO replacement policies exhibit a declining trend in speedup performance. In contrast, this trend is less pronounced for App2Exa-LFU, due to LFU's tendency to retain frequently accessed vectors without considering time decay. This behavior leads to outdated but previously popular vectors remaining in the cache. Among all methods, our benefit-driven cache

(a) SIFT

(BDC) achieves the highest speed-up performance, which demonstrates the superior effectiveness of our caching replacement policy in adapting to dynamic query distributions.

Evaluation on the best-first strategy. Fig. 8 shows the speed-up performance of best-first strategy that employed in the VP-Tree index. A performance gap is observed between the App2Exa-BDC and App2Exa-BDC# across all datasets. Specifically, the best-first strategy used in the VP-Tree can further shorten the query latency by 8%-12% in SIFT, and 9%-13% in AOL, demonstrating the effectiveness of this strategy in enhancing query efficiency.

6 Conclusion

We proposed App2Exa, a cache-guided approach that bridges approximate and exact kNN searches to enhance efficiency. App2Exa combines an incremental cache graph for fast approximate retrieval with an enhanced VP-Tree for exact search, addressing the challenge of dynamic query distributions in low-to-medium dimensional spaces. Its benefitdriven caching mechanism ensures optimal cache utilization by prioritizing vectors based on query frequency, recency, and computational cost. Experiments on real-world datasets highlight the scalability and robustness of App2Exa, achieving up to a 3x speed-up over traditional exact kNN methods.

Acknowledgments

This paper was supported by the National Key R&D Program of China 2024YFE0111800, NSFC 62032001, and the Science and Technology Development Fund Macau SAR (0003/2023/RIC, 0052/2023/RIA1, 0031/2022/A, 001/2024/SKL for SKL-IOTSC).