CS Paper Radar

When Imputation Changes the Nearest Neighbor: Exact Certification of Similarity Retrieval for Incomplete Sensor Time Series

Jianru Shen

cs.DB cs.DS ·submitted 2026-10-29 17:45 UTC · v1
publishedtheory

Abstract

Sensor time series routinely reach similarity search with missing values, and the retrieved neighbours then depend on how the gaps were filled. We ask which retrieval conclusions hold for every admissible completion of an incomplete query. For a family of window-minimum distances that contains the $L_1$ distance as its separable end we give a pairwise certificate that one candidate is strictly closer than another, a guaranteed candidate set that contains every possible nearest neighbour, and a certificate that a nearest-neighbour label cannot change. The guarantees hold uniformly over the specified box and apply to the true query whenever it lies inside. At the separable end a closed form is known, but beyond it the worst-case gap need not be attained at a corner of the box. We prove a finite reduction to critical values, give an exact interval dynamic programme for the worst-case ranking gap, and a quadratic-time fast layer of valid bounds and feasible witnesses, supported by an exact criterion for when the feature-box relaxation is tight. On three traffic-sensor collections with real gap patterns, linear interpolation changes the nearest neighbour in 15 to 33 percent of the queries. At the full band the feature-box relaxation misses up to 14 percent of the exactly stable boundary pairs, whereas fixed-completion and Monte Carlo checks issue false certificates. The fast layer resolves about 90 percent of all tested boundary pairs without dynamic programming, and on paired network-scale queries the exact method is 82 to 110 times faster than the programme alone. Label certificates transfer to three public benchmarks, and the band width trades forecasting accuracy and certification coverage for lower imputation sensitivity, with dataset-dependent crossovers.

Comment
Accepted at IEEE BigData

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.55
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

Grant: A Framework for Approximate Nearest Neighbor Search with Multi-Attribute Range Filters

cs.DB ·2026-10-08 ·Daichi Amagata
similarity 0.54
Abstract

Recently, academia and industry have considered the problem of approximate nearest neighbor search (ANNS) with filters. In this setting, each object consists of a high-dimensional vector and attribute values. Given a query vector, filters for attribute values, and $k$, this problem retrieves $k$ vectors approximately nearest to the query vector among a set of objects passing the filters. This paper considers range filters, i.e., users can specify a range constraint for each attribute. Most existing works do not consider this setting, and they assume (i) only a single attribute or (ii) matching filters that require the same attribute values or categories. Existing techniques for these assumptions are not available for our setting or are trivially not efficient. Although standard solutions, such as pre-filter and post-filter, can handle our problem, they are also inefficient. Some works tackle the same problem as ours, but their techniques necessitate historical query workloads, which significantly limit practical use cases. To remove these limitations, this work proposes Grant, a novel framework that solves this problem efficiently while accepting arbitrary range filters and ANNS data structures. Grant can guarantee a search time sub-linear to the number of objects, which is not held by existing techniques. We conduct extensive experiments, and their results demonstrate that Grant outperforms existing techniques.

0.19

TSGuard: A Real-Time Framework for Detecting and Imputing Missing Data in Streaming Time Series

cs.DB cs.HCcs.IRcs.LG ·2026-10-02 ·Imane Hocine, Asma Abboura, Soror Sahri, Abhijith Senthilkumar, Yacine Hakimi +1 more
top venue similarity 0.54
Abstract · The 35th ACM International Conference on Information and Knowledge Management (CIKM '26), November 07--11, 2026, Rome, Italy

Streaming sensor applications routinely suffer from delayed or missing observations caused by faults, communication losses, or environmental interference. Although recent imputation methods exploit temporal and spatial dependencies effectively, most either assume offline access to future observations or prioritize throughput without enforcing domain plausibility. We present TSGuard, a real-time demonstration system for monitoring, validating, and imputing missing values in streaming time series. TSGuard combines a lightweight graph-aware temporal imputation model with constraint-aware validation, fallback estimation, and operator-facing explanations. Rather than treating imputation as an isolated prediction task, TSGuard integrates it into a broader data-quality loop: detect problematic observations, impute missing values, validate estimated against physical and spatial constraints, and either retain the original value as a plausible anomaly or replace it when it violates domain constraints. Using environmental sensing as a motivating setting, the demo enables users to inspect delayed sensors, compare imputers, define constraints, and validate flagged values in real time. The combination of lightweight online spatiotemporal imputation, domain-aware validation, and explicit retain-or-replace decisions is our central contribution, while interactive explanations make these decisions inspectable and actionable. for operators.

0.37

The Price of Almost Navigability

cs.DS ·2026-09-02 ·Tomer Waizer, Yoav Danieli
theory similarity 0.53
Abstract

Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $Ω(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-ε)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $ε$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/ε)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $ε$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $ε$, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $Ω(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.

0.09

misi: a Metric Inverted Sample Index

cs.IR ·2026-08-27 ·Edgar Chavez
similarity 0.53
Abstract · 14 pages. Links to code

We present misi, an inverted index for approximate nearest-neighbor search over general metric spaces whose vocabulary is a random sample of the database, of size proportional to $n$. Each object is represented by its $k_b$ nearest sample points, found by a pluggable inner index over the sample; queries are answered by an idf-weighted shared-neighbor vote followed by exact verification of $C$ candidates. The construction generalizes the NAPP index from a constant number of pivots to a linear-size vocabulary, which keeps posting lists at constant expected length $ρ= k_b/α$ as $n$ grows and turns the index into a combinator: any high-recall index on $αn$ points yields an index on $n$ points, for any metric. A probabilistic model gives a recall guarantee -- $k_b$ logarithmic in $n$ over the overlap gap suffices, with a verification budget the index itself estimates -- and a matching limit: the vote cannot resolve overlap differences below order $1/\sqrt{k_b}$. The design's strengths are structural: construction is $n$ independent searches -- embarrassingly parallel, deterministic, $5{,}250$ s for $10^8$ vectors on 64 cores, $3.7\times$ faster than a matched-recall graph build -- it streams under an enforced 3 GiB cap, and the portable artifact serves $10^8$ vectors from NVMe within an enforced 8 GB budget, below the working floor of the SSD-graph baseline. Its cost is query-time work: saturated graph baselines answer $6$-$16\times$ faster in RAM, and the verification budget for 0.99 recall grows as $n^{0.30}$. All results carry seeds, saturation sweeps and full configurations, are generated from run manifests, and include measured negative results. The intended applications weight construction cost, determinism, memory footprint, or black-box metrics over peak throughput: frequently rebuilt corpora, batch similarity workloads, constrained-memory serving.

0.48

Adaptive search with path-constrained mobile sensors using multi-arm bandits

cs.RO cs.LGmath.OC ·2026-10-29 ·Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy, Stefano Di Cairano
similarity 0.52
Abstract · 24 pages, 5 figures

We study a constrained sequential decision problem for detecting regions of interest from noisy online measurements collected by a team of energy-constrained mobile sensors. The sensor motion is restricted to a precomputed set of feasible paths that satisfy mobility constraints, limited available energy by requiring return to charging stations, and avoidance of known obstacles. We cast the resulting active path selection as a multi-armed bandit problem and propose an iterative search algorithm that adaptively assigns paths using confidence bounds computed from the collected data. We also propose a graph-based method to construct low-cardinality path covers under the team's constraints. We establish finite-time and anytime probabilistic correctness guarantees for the proposed algorithm, derive non-asymptotic upper bounds on the times required to detect all regions of interest and to label all nodes, and show that these bounds match algorithm-independent lower bounds up to constant factors for a broad class of problem instances. Using numerical simulations, we illustrate the behavior of the proposed approach and the effect of path redundancy and team size on search performance.

0.15

Constant Approximation of Fréchet Distance in Near-Linear Time

cs.CG ·2026-10-30 ·Haoqiang Huang, Zihe Wang, Shuo Zhang
similarity 0.52
Abstract

We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.

0.15

A Versioned Unified Graph Index for Dynamic Timestamp-Aware Nearest Neighbor Search

cs.IR ·2026-08-27 ·Jun Woo Chung, Weijie Zhao
similarity 0.52
Abstract · 15 pages, 8 figures, 3 algorithms

We present TiGER (Time-Integrated Graph for Efficient Retrieval), a novel approach for performing fast time-aware approximate nearest neighbor searches on dynamic vector datasets with flexibility over any possible time range. Our proposed algorithm builds and maintains a unified graph for all vectors by leveraging an index structure based on integrated versioned connectivity, allowing arbitrary time intervals to be queried directly on the unified graph without having to traverse invalid vectors. This forgoes the need for post-search filtering or merging, or separate graphs for each possible composite range. Empirical evaluations show that our method attains up to a 5x improvement in queries per second (QPS) without compromising accuracy over baselines based on filtering or per-time-segment sub-graphs. We believe that this method will enable efficient temporal analysis across evolving datasets in real-time recommendation systems, log analysis, and any scenario requiring fast similarity search over dynamic, time-segmented data.

0.32