Back to papers
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
- 1511
- Venue
- PODS
- Year
- 2010
- Pagerank
- 6.9711051e-05
- Overall Rank
- 3,557 | 75.28%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
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 |
| 18 |
On Random Sampling over Joins |
1999 |
SIGMOD |
0.00092569117 |
| 362 |
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases |
1995 |
VLDB |
0.00025758421 |
| 475 |
Bottom-Up Computation of Sparse and Iceberg CUBEs |
1999 |
SIGMOD |
0.00022238407 |
| 537 |
Fast Time Sequence Indexing for Arbitrary L_p Norms |
2000 |
VLDB |
0.00020650291 |
| 598 |
Computing Iceberg Queries Efficiently |
1998 |
VLDB |
0.00019431661 |
| 874 |
What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically |
2003 |
PODS |
0.0001568356 |
| 1,394 |
Sketching Streams Through the Net: Distributed Approximate Query Tracking |
2005 |
VLDB |
0.00012218557 |
| 1,466 |
Space Efficient Mining of Multigraph Streams |
2005 |
PODS |
0.00011838607 |
| 1,744 |
Space-optimal Heavy Hitters with Strong Error Bounds |
2009 |
PODS |
0.00010694459 |
| 1,967 |
Efficient Computation of Iceberg Cubes with Complex Measures |
2001 |
SIGMOD |
9.9108189e-05 |
| 2,269 |
Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling |
2005 |
VLDB |
9.1507118e-05 |
| 2,952 |
Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams |
2006 |
PODS |
7.8230109e-05 |
| 3,123 |
Comparing Data Streams Using Hamming Norms (How to Zero In) |
2002 |
VLDB |
7.5270618e-05 |
| 3,701 |
Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams |
2005 |
PODS |
6.825442e-05 |
| 5,602 |
Time-Decaying Aggregates in Out-of-order Streams |
2008 |
PODS |
5.4153555e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 7,479 |
Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms |
2024 |
SIGMOD |
4.7135369e-05 |
| 344 |
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
2001 |
VLDB |
0.00026698826 |
| 7,146 |
Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model |
2019 |
PODS |
4.8133378e-05 |
| 6,415 |
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems |
2016 |
PODS |
5.064828e-05 |
| 10,986 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1905499e-05 |
| 4,379 |
Rectangle-Efficient Aggregation in Spatial Data Streams |
2012 |
PODS |
6.2326895e-05 |
| 11,841 |
Streaming Algorithms for Robust Distinct Elements |
2016 |
SIGMOD |
4.1905499e-05 |
| 11,363 |
Approximate Range Thresholding |
2022 |
SIGMOD |
4.1905499e-05 |
| 2,952 |
Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams |
2006 |
PODS |
7.8230109e-05 |
| 11,863 |
Range Thresholding on Streams |
2016 |
SIGMOD |
4.1905499e-05 |