Fast Manhattan Sketches in Data Streams

Summary: First 1-pass turnstile streaming algorithm for approximating l1 (Manhattan) distance with O*(ε^{-2}) space and O*(1) update time. Improves prior trade-offs (previously Ω(ε^{-3}) space or Ω(ε^{-2}) update) and is optimal up to polylog factors. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1510
Venue: PODS
Year: 2010
Pagerank: 6.7387541e-05
Overall Rank: 4,370 | 70.02%
DOI: 10.1145/1807085.1807101

Incoming Non-self Citations Over Time

Authors

1. Jelani Nelson (Massachusetts Institute of Technology)
2. David P. Woodruff (IBM)

BibTeX Citation

@inproceedings{nelson_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Fast Manhattan Sketches in Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807101},
        doi = {10.1145/1807085.1807101},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nelson, Jelani and Woodruff, David P.},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
451	Mergeable Summaries	2012	PODS	0.00018151445
10,869	Federated Data Distribution Shift Estimation	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019869565
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
1,825	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.6726613e-05
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05
3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.2428869e-05
5,802	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	6.0843083e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB
2	7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
3	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
4	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
5	4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
6	12,034	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
7	11,559	Approximate Range Thresholding	2022	SIGMOD
8	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
9	12,056	Range Thresholding on Streams	2016	SIGMOD
10	5,669	Data Streams with Bounded Deletions	2018	PODS