Adaptive Prefiltering for High-Dimensional Similarity Search: A Frequency-Aware Approach

• URL: http://arxiv.org/abs/2602.22214v1
• Date: Wed, 03 Dec 2025 10:11:35 GMT
• Title: Adaptive Prefiltering for High-Dimensional Similarity Search: A Frequency-Aware Approach
• Abstract summary: We present an adaptive prefiltering framework that partitions the query space into frequency tiers following Zipfian distributions.<n>Experiments on ImageNet-1k using CLIP embeddings demonstrate that frequency-aware budget allocation achieves equivalent recall with 20.4% fewer distance computations.<n>The framework introduces minimal overhead through lightweight frequency tracking and provides graceful degradation for unseen queries through coherence-based fallback policies.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: High-dimensional similarity search underpins modern retrieval systems, yet uniform search strategies fail to exploit the heterogeneous nature of real-world query distributions. We present an adaptive prefiltering framework that leverages query frequency patterns and cluster coherence metrics to dynamically allocate computational budgets. Our approach partitions the query space into frequency tiers following Zipfian distributions and assigns differentiated search policies based on historical access patterns and local density characteristics. Experiments on ImageNet-1k using CLIP embeddings demonstrate that frequency-aware budget allocation achieves equivalent recall with 20.4% fewer distance computations compared to static nprobe selection, while maintaining sub-millisecond latency on GPU-accelerated FAISS indices. The framework introduces minimal overhead through lightweight frequency tracking and provides graceful degradation for unseen queries through coherence-based fallback policies.

Related papers

• Pre-retrieval Query Clustering for Adaptive Top-k Document Retrieval in RAG Systems [7.440012812118169]
  RAG systems commonly retrieve a fixed number of documents to ground generation.<n>simple queries suffer over-retrieval (adding noise and cost) while complex queries are under-retrieved.<n>We propose a practical, general framework for query-adaptive retrieval depth.
  arXiv  Detail & Related papers  (2026-09-11T19:57:12Z)
• Evidence-Driven Dynamic Visual Selector for Efficient Long Video Understanding [54.840531495584095]
  We propose a dynamic visual selection framework named EviSelect grounded in the target MLLM's internal attention evidence.<n>Our method efficiently approximates maps of the target MLLM using highly compressed visual inputs and sparse attention.<n>EviSelect achieves superior performance compared to existing methods while reducing selected visual tokens by about 50% and achieving a 3.9x end-to-end speedup.
  arXiv  Detail & Related papers  (2026-08-06T09:15:43Z)
• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDOR is a memory-efficient extension of Greedy Best-First Search (GBFS)<n>GONDOR periodically compresses the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states.<n> Experiments show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS.
  arXiv  Detail & Related papers  (2026-05-27T13:20:58Z)
• FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances [17.58209161125891]
  FAVOR is an efficient filter-agnostic vector ANNS that supports arbitrary filtering conditions while maintaining stable performance across varying selectivity levels.<n>Experiments on real-world datasets demonstrate that FAVOR achieves a 1.3-5$times$ higher QPS at $Recall@10 = 95%$ compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-08T14:11:49Z)
• Channel-wise Retrieval for Multivariate Time Series Forecasting [10.27767121181644]
  CRAFT (Channel-wise retrieval-augmented forecasting) is a novel framework that performs retrieval independently for each channel.<n> Experiments on seven public benchmarks demonstrate that CRAFT outperforms state-of-the-art forecasting baselines.
  arXiv  Detail & Related papers  (2026-04-07T07:40:26Z)
• Rethinking Deep Research from the Perspective of Web Content Distribution Matching [86.90255285277256]
  We propose WeDas, a Web Content Distribution Aware framework that incorporates search-space structural characteristics into the agent's observation space.<n>We introduce a few-shot probing mechanism that iteratively estimates the Query-Result Alignment Score.<n>As a plug-and-play module, WeDas consistently improves sub-goal completion and accuracy across four benchmarks.
  arXiv  Detail & Related papers  (2026-03-07T14:51:17Z)
• Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis [0.5249805590164902]
  Filtered Approximate Nearest Neighbor Search (FANNS) is used to combine semantic retrieval with metadata constraints.<n>In this work, we systematize the taxonomy of filtering strategies and evaluate their integration into vectors.<n>Our experiments reveal that algorithmic adaptations within the engine often override raw index performance.
  arXiv  Detail & Related papers  (2026-02-11T23:40:26Z)
• Learning to Guide Local Search for MPE Inference in Probabilistic Graphical Models [7.287294240824019]
  Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs) is a fundamental yet computationally challenging problem.<n>We propose a neural amortization framework for improving local search in repeated-Query regime.<n>We provide theoretical intuition linking distance-reducing move selection to improved promise during neighbor selection.
  arXiv  Detail & Related papers  (2026-02-01T22:43:28Z)
• Prompt-aware of Frame Sampling for Efficient Text-Video Retrieval [21.65508603851204]
  ProCLIP is a user-centric framework that achieves state-of-the-art accuracy with significantly improved efficiency.<n>We design a prompt-aware frame sampling strategy that dynamically guides lightweight feature extractors using textual prompts to select semantically relevant frames.<n>We adopt a two-stage candidate pruning strategy that combines rapid coarse filtering via a lightweight module with CLIP-powered fine-grained re-ranking, enhancing retrieval efficiency while preserving accuracy.
  arXiv  Detail & Related papers  (2025-07-21T10:46:49Z)
• vCache: Verified Semantic Prompt Caching [95.16654660556975]
  This paper proposes vCache, the first verified semantic cache with user-defined error rate guarantees.<n>It employs an online learning algorithm to estimate an optimal threshold for each cached prompt, enabling reliable cache responses without additional training.<n>Our experiments show that vCache consistently meets the specified error bounds while outperforming state-of-the-art static-threshold and fine-tuned embedding baselines.
  arXiv  Detail & Related papers  (2025-02-06T04:16:20Z)
• Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering [49.1574468325115]
  This paper presents a novel approach for similarity search with complex filtering capabilities on billion-scale datasets, optimized for CPU inference.<n>Our method extends the classical IVF-Flat index structure to integrate multi-dimensional filters.<n>The proposed algorithm combines dense embeddings with discrete filtering attributes, enabling fast retrieval in high-dimensional spaces.
  arXiv  Detail & Related papers  (2025-01-23T07:47:00Z)
• pEBR: A Probabilistic Approach to Embedding Based Retrieval [9.186585413958769]
  Embedding-based retrieval aims to learn a shared semantic representation space for both queries and items.<n>We propose a novel textbfprobabilistic textbfEmbedding-textbfBased textbfRetrieval (textbfpEBR) framework.
  arXiv  Detail & Related papers  (2024-10-25T07:14:12Z)
• Temporal-aware Hierarchical Mask Classification for Video Semantic Segmentation [62.275143240798236]
  Video semantic segmentation dataset has limited categories per video. Less than 10% of queries could be matched to receive meaningful gradient updates during VSS training. Our method achieves state-of-the-art performance on the latest challenging VSS benchmark VSPW without bells and whistles.
  arXiv  Detail & Related papers  (2023-09-14T20:31:06Z)
• Efficient Joint-Dimensional Search with Solution Space Regularization for Real-Time Semantic Segmentation [27.94898516315886]
  We search an optimal network structure that can run in real-time for this problem. A novel Solution Space Regularization (SSR) loss is first proposed to effectively encourage the supernet to converge to its discrete one. A new Hierarchical and Progressive Solution Space Shrinking method is presented to further achieve high efficiency of searching.
  arXiv  Detail & Related papers  (2022-08-10T11:07:33Z)
• Toward A Formalized Approach for Spike Sorting Algorithms and Hardware Evaluation [2.0738462952016232]
  Spike sorting algorithms are used to separate extracellular recordings of neuronal populations into single-unit spike activities. We formalize a set of standardized criteria and a publicly available synthetic dataset entitled Synthetic Simulations Of Extracellular Recordings (SSOER) Our system consumes approximately (per channel) 10.72mW and occupies an area of 0.66mm$2$ in a 22nm FDSOI Complementary Metal-Oxide-Semiconductor (CMOS) process.
  arXiv  Detail & Related papers  (2022-05-13T08:42:18Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  We propose a novel caching paradigm, that we named approximate-key caching. While approximate cache hits alleviate DL inference workload and increase the system throughput, they however introduce an approximation error. We analytically model our caching system performance for classic LRU and ideal caches, we perform a trace-driven evaluation of the expected performance, and we compare the benefits of our proposed approach with the state-of-the-art similarity caching.
  arXiv  Detail & Related papers  (2021-12-13T13:49:11Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  In rank aggregation problems, users exhibit various accuracy levels when comparing pairs of items. We propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons. We prove that our algorithm can return the true ranking of items with high probability.
  arXiv  Detail & Related papers  (2021-10-08T13:51:55Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.