2025/10/06 by Sanjeev Khanna, Khanna, Sanjeev, Ashwin Padaki +5 · 1 citation
Computer Science · Engineering · #Neural Networks and Applications #Target Tracking and Data Fusion in Sensor Networks #Fault Detection and Control Systems
paper · pdf · doi:10.48550/arxiv.2510.04918
We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stream of updates to a frequency vector x ∈ ℤ≥ 0n, where the support of x defines a multiset of points in a fixed metric space M = ([n], d). The goal is to estimate the diameter of this multiset, defined as max\d(i,j) : xi, xj > 0\, to a specified approximation factor while using as little space as possible. In insertion-only streams, a simple O(log n)-space algorithm achieves a 2-approximation. In sharp contrast to this, we show that in the dynamic streaming model, any algorithm achieving a constant-factor approximation to diameter requires polynomial space. Specifically, we prove that a c-approximation to the diameter requires nΩ(1/c) space. Our lower bound relies on two conceptual contributions: (1) a new connection between dynamic streaming algorithms and linear sketches for \em scale-invariant functions, a class that includes diameter estimation, and (2) a connection between linear sketches for diameter and the \em minrank of graphs, a notion previously studied in index coding. We complement our lower bound with a nearly matching upper bound, which gives a c-approximation to the diameter in general metrics using nO(1/c) space.