An Approximate L1 -Difference Algorithm for Massive Data Streams

DOI10.1137/S0097539799361701zbMath1029.68157MaRDI QIDQ4785634

Sampath Kannan, Mahesh Viswanathan, Joan Feigenbaum, Martin J. Strauss

Publication date: 5 January 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

streaming algorithmsdistance approximation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (13)

Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ On-board vehicle data stream monitoring using mine-fleet and fast resource constrained monitoring of correlation matrices ⋮ An information statistics approach to data stream and communication complexity ⋮ Adapting parallel algorithms to the W-stream model, with applications to graph problems ⋮ Symmetric norm estimation and regression on sliding windows ⋮ Unnamed Item ⋮ Adaptive sampling for geometric problems over data streams ⋮ Statistical estimation with bounded memory ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Sketching information divergences ⋮ Depth First Search in the Semi-streaming Model ⋮ Communication Complexity of Statistical Distance ⋮ On graph problems in a semi-streaming model

This page was built for publication: An Approximate L¹ -Difference Algorithm for Massive Data Streams