Unverified

Fast L_1 Difference

Let $x$ and $y$ be the two vectors specified by data streams, and let $D_1(x,y)$ denote their $L_1$ difference. Determine the time complexity of computing or approximating $D_1(x,y)$ , with particular attention to the time required to process each stream update. The source does not specify the stream model or a formal approximation guarantee beyond the notation $(\epsilon,\delta)$ .

Problem 1.

Can the large-frequency estimation-and-removal approach used for higher-order frequency computations be adapted to computing $L_1$ difference?

Problem 2.

What update-time bounds follow from sparse projections based on stable distributions for $(\epsilon,\delta)$ -approximation of $L_1$ distance, where $\epsilon$ and $\delta$ are the two approximation parameters used by the source?

Problem 3.

Can one prove a nontrivial lower bound on stream-update time, either in the worst case or amortized over the stream?

Download

Abstract

The problem concerns the update-time complexity of computing the $L_1$ difference between two vectors specified by data streams. The standard approach described by the source uses projections onto pseudorandom vectors whose entries are drawn from the Cauchy distribution, but sufficient accuracy requires many independent inner products and can make each update costly. The open directions are to obtain faster $L_1$ -difference algorithms through large-frequency or sparse-projection techniques and to prove nontrivial worst-case or amortized lower bounds for stream-update time.

Background and progress

The problem was suggested by Graham Cormode and lists Kanpur 2006 as its source [sublinear2006fastl1, 2006]. Data-streaming research often emphasizes space complexity, while the source observes that many aggregates also admit very time-efficient update procedures. It identifies $L_1$ difference as a notable exception and describes the well-known method based on $1$ -stable Cauchy distributions: each vector is projected onto pseudorandom Cauchy vectors, but achieving sufficient accuracy requires maintaining many independent inner products and therefore makes updates costly.

The source proposes two algorithmic directions. The first asks whether methods for higher-order frequency computations that estimate large frequencies individually and use a removal step can be adapted to $L_1$ . The second asks what update-time bounds follow from sparse random projections, including sparse projections based on stable distributions, for $(\epsilon,\delta)$ -approximation of $L_1$ distance.

The source also asks for nontrivial worst-case or amortized lower bounds on stream-update time, noting that communication-complexity and cell-probe tools have successfully yielded space lower bounds. For a stream of $n$ updates, it contrasts $O(1)$ update time with $O(\epsilon^{-2}\log^3 n)$ update time, which give total times $O(n)$ and $O(n\epsilon^{-2}\log^3 n)$ , respectively. The original problem page is https://sublinear.info/index.php?title=Open_Problems:1.

Reference papers

Problem 1: Fast L_1 Difference2006 ↗

Fast L_1 Difference

Problem 1.

Problem 2.

Problem 3.

Coming soon

Organizer