Space needed to estimate distance grows fast with accuracy needs
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams
Data Structures and AlgorithmsComputational Geometry
Summary
This paper looks at how much memory is required to estimate the largest distance between points in a changing collection of data points, using a method that updates as points are added or removed. Previous work showed ways to estimate this distance approximately using a certain amount of memory. The authors prove that this amount of memory is nearly the smallest possible for any method that tries to keep this approximation quality. In other words, they establish a strong limit on how efficient such methods can be in terms of memory use.
What this means in practice
- •For data engineers: Understand minimum memory needed to track approximate largest distances in dynamic data streams.
- •For streaming algorithm designers: Guide design choices by ruling out highly memory-efficient algorithms beyond certain approximation limits for diameter estimation.
A theory result. No direct application yet.
Authors
Ashwin Padaki, Krish Singal, Erik Waingarten
Abstract
We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matching lower bound. Any dynamic streaming algorithm which can $c$-approximate the diameter of $n$ Euclidean vectors must use $n^{\tildeΩ(1/c^2)}$ space.