Experiments show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.
Abstract
Coreset selection reduces the cost of model training by replacing a large training set with a small representative subset. Existing gradient-approximation coreset methods such as CRAIG and cluster-based variants can preserve model accuracy. Still, their selection stages often rely on dense pairwise distances or large item-cluster bound matrices, leading to high time and memory costs on large datasets. This paper proposes KNNG-CS, a lightweight coreset selection method based on a $K$-nearest neighbor graph. KNNG-CS exploits local neighborhood structures to estimate the importance of each data item and greedily selects representative nodes without maintaining a quadratic distance matrix. The method requires only linear storage in the number of edges. Experiments on four real-world datasets show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
The annual SISAP Indexing Challenge benchmarks Approximate Nearest Neighbor Search (ANNS) algorithms under rigorous constraints. This paper presents our submissions for the 2026 edition, addressing both $k$-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings (Task 1) and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features (Task 2). To optimize construction speed, we utilize Equi-Voronoi Polytopes (EVP) for efficient quantization, supplemented by targeted reranking strategies to maintain high recall. For MIPS, we transform the asymmetric inner product problem into a Euclidean search space via dimensionality augmentation. To reduce query latency and optimize memory access, we introduce a 1D presorting mechanism via Fast Linear Assignment Sorting (FLAS) prior to graph construction. This significantly improves spatial locality and cache hit rates during subsequent graph traversal. Source Code: https://github.com/Visual-Computing/sisap26-deglib
Nico Hezel, Kai Barthel, Bruno Schilling et al.· 0 citations
This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.
Approximate Nearest Neighbor (ANN) search at scale exposes a structural trade-off between routing accuracy, memory footprint, and query latency. Graph-based indices such as HNSW provide high recall but incur significant memory overhead due to full-dataset connectivity, while centroid-based IVF variants remain memory-efficient yet degrade under highdimensional, non-convex cluster manifolds. This trade-off forces system designers to choose between recall and storage cost, and no existing single-index design resolves both simultaneously at scale. The need for an index that delivers graph-level recall at IVF-level memory cost therefore motivates this work. We present a density-aware hybrid indexing architecture that explicitly decouples routing from storage. The system extracts manifold representatives via a robust Lloyd refinement and constructs a lightweight HNSW graph over this reduced set, preserving topological routing precision while avoiding fullgraph memory costs. Candidate selection is performed through a dual-path routing mechanism combining geometric centroids and density-aware graph traversal. The search pipeline then diverges into two execution regimes: (1) an uncompressed, SIMD-optimized L2 path achieving hardware-bound latency, and (2) a compressed OPQ-based residual reconstruction path for memory-constrained deployment. On SIFT1M, the uncompressed configuration achieves 0.09 ms/query with 0.974 Recall@10, while the 32-byte/vector OPQ configuration attains 0.341 ms/query with 0.997 Recall@10. Integrated into a gRPC scatter-gather framework, the distributed system sustains 0.9975 Recall@10 across sharded partitions. These results demonstrate that density-aware routing enables graph-level recall with IVF-level storage cost, providing a scalable foundation for high-dimensional vector retrieval.
Aditya Parthiban, Arindam Kalita, Rishab K Das et al.· 2026 International Conferenc...· 0 citations
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.
R. Ganian, M. Vasilakis, Simon Wietheger· 0 citations