---
title: "App2Exa: Accelerating Exact kNN Search via Dynamic Cache-Guided Approximation"
authors:
  - "Ke Li"
  - "Leong Hou U"
  - "Shuo Shang"
doi: "10.24963/ijcai.2025/339"
url: "https://ijcai.org/proceedings/2025/339"
pdf: "https://ijcai.org/proceedings/2025/0339.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3045-3053"
track: "Main Track"
keywords:
  - "Multidisciplinary Topics and Applications: MTA: Databases"
  - "Multidisciplinary Topics and Applications: MTA: Transportation"
  - "Data Mining: DM: Information retrieval"
  - "Data Mining: General"
---

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

Ke Li, Leong Hou U, Shuo Shang

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 3045-3053. DOI: [10.24963/ijcai.2025/339](https://doi.org/10.24963/ijcai.2025/339)

## Abstract

The k-nearest neighbor (kNN) query is a cornerstone of similarity-based applications across various domains. While prior work has enhanced kNN search efficiency, it typically focuses on approximate methods for high-dimensional data or exact methods for low-dimensional data, often assuming static query and data distributions. This creates a significant gap in accelerating exact kNN search for low-to-medium dimensional data with dynamic query distributions. To fill this gap, we propose App2Exa, a cache-guided framework that integrates approximate and exact kNN search. App2Exa utilizes a dynamically maintained cache graph index to retrieve approximate results, which subsequently guide exact search using a VP-Tree with a best-first strategy. A benefit-driven caching mechanism further optimizes performance by prioritizing vectors based on frequency, recency, and computational cost. Experimental results demonstrate that App2Exa significantly boosts efficiency, providing a robust and scalable solution for evolving query patterns and enabling exact kNN search to support higher dimensionality more effectively.