Streaming Algorithms and Metric Fitting

The field of streaming algorithms and metric fitting is rapidly advancing, with a focus on developing efficient and space-optimal methods for clustering, subspace embeddings, and ultrametric fitting. Recent developments have shown that streaming algorithms can match offline algorithms in both space and time complexity, enabling the processing of large datasets in real-time. Notably, innovative approaches have been proposed for clustering and subspace embeddings in the streaming model, achieving optimal bounds and exponential improvements over previous methods. The study of metric fitting problems in the semi-streaming model has also led to the development of single-pass polynomial-time algorithms for ultrametrics and tree metrics. Noteworthy papers include: Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings, which achieves optimal bounds for clustering and subspace embeddings in the streaming model. Fitting Tree Metrics and Ultrametrics in Data Streams, which provides a single-pass polynomial-time algorithm for ultrametrics and a complete characterization of the ultrametric fitting problem.

Sources

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings

Hardness of Median and Center in the Ulam Metric

Streaming algorithms for products of probabilities

Fitting Tree Metrics and Ultrametrics in Data Streams

Built with on top of