A research team has now introduced MiniRFANN, a disk-resident scheme for range-filtered approximate vector similarity search that is designed specifically for edge devices, where memory is scarce and every trip to disk costs time. The work, published in Data Science and Engineering, describes how a carefully arranged pair of B+tree indexes, product-quantized vector codes and a Z-order disk layout can together deliver high-recall filtered search with substantially lower memory use and latency than existing methods adapted for the same setting.
To understand why this matters, it helps to start with the underlying query. Approximate nearest neighbor search, or ANN, is the task of finding the top-k vectors in a large dataset that lie closest to a query vector, trading a small amount of accuracy for sublinear query time. It underpins recommender systems, multimedia retrieval, question answering and retrieval-augmented generation. In many real applications, however, similarity alone is not enough. Results must also satisfy constraints on auxiliary attributes such as timestamps, locations or prices. This combination gives rise to the range-filtered approximate k-nearest neighbor problem, known as RFANN: retrieving the top-k vectors that are both close to the query in feature space and whose attribute values fall within a specified range. The authors illustrate the idea with queries like finding images visually similar to a given one but taken in the past month, or retrieving sensor readings matching a target pattern from a specific location range.
Existing RFANN approaches follow three broad filtering strategies, and each has a distinct failure mode on constrained hardware. Pre-filtering applies the attribute constraints first and then searches the reduced set; it works well for narrow ranges but, when ranges are wide, it must scan and load many scattered vectors, incurring high random input-output costs on disk. Post-filtering performs the similarity search over the full dataset and discards results that violate the attribute bounds afterward, which wastes effort when ranges are narrow. In-filtering integrates range checks directly into index traversal for early pruning and is highly efficient on in-memory indexes, but it requires the entire index to reside in memory. On servers with abundant RAM these designs perform impressively, often by combining powerful graph or tree index structures with compression techniques such as product quantization.
Edge devices change the calculus entirely. The researchers note that a growing number of applications must run such searches on hardware with tight resource budgets, often sub-gigabyte memory. On a typical smartphone with 2 to 8 gigabytes of RAM, the datasets involved can reach multi-gigabyte sizes, far exceeding what the application memory can hold, so the entire dataset lives primarily on device storage with only a small fraction cached in RAM. Under those conditions, in-filtering exhausts memory, while pre- and post-filtering suffer severe input-output amplification, and both problems significantly degrade query latency. According to the authors, no prior work has systematically addressed RFANN on edge devices, and MiniRFANN is their attempt to fill that gap.
The system’s design rests on three insights. First, range filtering and similarity pruning can be jointly modeled as hard and soft selectivity: attribute constraints deterministically eliminate objects, while distance-based pruning probabilistically narrows candidates. Second, the relative pruning power of these two filters varies from query to query and can be estimated at runtime. Third, disk input-output costs can be greatly reduced by co-designing the index structure with the on-disk data layout. The offline indexing phase begins with hierarchical clustering, built through recursive K-means, which partitions the vectors into semantically meaningful clusters and assigns each vector a cluster ID that reflects its similarity locality. Because high-dimensional vectors have no natural total ordering, this clustering approximates an ordering that attributes already possess.
On top of that preprocessing, MiniRFANN compresses every vector with product quantization, a technique that splits each vector into disjoint subvectors, trains a codebook of centroids per subspace, and encodes each subvector by the index of its nearest centroid. Approximate Euclidean distances can then be computed efficiently from precomputed lookup tables of centroid distances, offering a practical trade-off between memory efficiency and retrieval accuracy. Over these compressed codes the team builds two B+tree indexes: one keyed by attribute values, to support efficient range filtering, and one keyed by cluster IDs, to enable distance-based pruning through cluster locality. B+ trees are chosen over graph-based indexes such as HNSW because they are inherently range-aware, disk-friendly and memory-efficient, allowing range-restricted scans that graph indexes, which assume memory residency, do not naturally provide.
At query time, MiniRFANN’s most distinctive mechanism comes into play: adaptive index selection. The attribute selectivity, the fraction of the dataset satisfying the query’s range, can be computed directly because the range is specified. The distance selectivity, the fraction accessed via cluster-based filtering, is estimated from a minimum candidate count needed to meet the user’s recall threshold, assuming a uniform distribution. The system then compares the two selectivities and picks the index with greater pruning power: if the attribute selectivity is lower, it uses the attribute-based tree; otherwise, the cluster-based tree. The search proceeds as a range query on the chosen tree, jointly applying attribute constraints and quantization-based distance pruning, and only the top-ranked candidates are loaded from disk for exact distance computation and final re-ranking. The authors also store raw vectors on disk following a Z-order curve over the attribute and cluster ID spaces, so that vectors close in that two-dimensional space tend to sit contiguously on disk, letting a single sequential read fetch multiple useful candidates and reducing random seeks during re-ranking.
The experimental evaluation compares MiniRFANN against state-of-the-art RFANN baselines, including pre-filtering, DiskIVF-PostFiltering and SPANN-PostFiltering, on three standard benchmarks. SIFT contains one million 128-dimensional image patch descriptors with 10,000 query vectors; GIST holds one million 960-dimensional global image descriptors with 1,000 queries; and Paper consists of 2,029,997 200-dimensional dense embeddings with 10,000 queries. Since these datasets carry no numerical attributes, the team assigned each vector a random value within specified ranges. All methods were implemented in C++ and run single-threaded on an Ubuntu virtual machine with 4 gigabytes of RAM, 40 gigabytes of disk and two virtual CPUs, with each experiment repeated three times. Latency, recall rate, memory overhead and construction time were measured across four attribute range ratios simulating intervals from narrow to broad.
The reported results are concrete. Across all query workloads, MiniRFANN consistently reduced query latency by 10.02 percent to 87.13 percent while maintaining the same recall levels, with the advantage most pronounced for narrow ranges; on the Paper dataset at a 2^-6 range ratio it achieved a latency of 39.88 milliseconds, a 51.38 percent reduction from the best baseline at 82.02 milliseconds. Memory overhead was lowest in every tested scenario, cut by 5.88 percent to 66.67 percent relative to the best baselines; at the same Paper dataset workload MiniRFANN consumed 25 megabytes against 57 for the most efficient baseline. Memory footprints stayed below 50 megabytes on SIFT and Paper and under 80 megabytes on GIST. Index construction time remained comparable to post-filtering methods, adding only 7.4, 2.1 and 9.1 percent overhead over SPANN-PostFiltering on the three datasets. Latency and recall rose together for all methods, as expected when higher accuracy is pursued.
The authors frame MiniRFANN as a disk-friendly framework that jointly addresses the memory and input-output bottlenecks of existing RFANN methods by combining dual B+tree indexing, selectivity-driven adaptive index selection and a Z-order data layout. They also outline its current boundaries: updates are handled through an in-memory buffer with batch synchronization into Z-order partitions, suited to append-dominant or moderately dynamic workloads, while concurrent update handling and incremental re-clustering remain future work, as do richer filter types and multi-attribute constraints combining time, location and other contextual filters. For a field racing to bring semantic retrieval onto the devices people actually carry, the paper offers a measured but notable data point: filtered vector search, long a server-side luxury, can be made to run within the tight budgets of the edge.
Subject of Research: Range-filtered approximate vector similarity search on resource-constrained edge devices
Article Title: MiniRFANN: Range-Filtered Approximate Vector Similarity Search on Edge Devices
Article References: Li, S., Liu, Y., Wang, Y., Zhou, Z., Zhang, K., & Tong, Y. (2026). MiniRFANN: Range-Filtered Approximate Vector Similarity Search on Edge Devices. Data Science and Engineering. https://doi.org/10.1007/s41019-025-00343-5
Image Credits: AI Generated
DOI: 10.1007/s41019-025-00343-5
Keywords: approximate nearest neighbor search, edge computing, vector similarity search, B+tree indexing, product quantization, range filtering, disk-resident indexes, Z-order layout, retrieval-augmented generation, memory-constrained devices, recall and latency trade-off, hierarchical clustering
News Source: Denise Maddox. (October 30, 2026). New Indexing Scheme Brings Filtered Vector Search to Edge Devices. Scienmag.
