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.9629443e-05
- Overall Rank
- 3,566 | 75.20%
- 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.00092385438 |
| 362 |
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases |
1995 |
VLDB |
0.00025770385 |
| 472 |
Bottom-Up Computation of Sparse and Iceberg CUBEs |
1999 |
SIGMOD |
0.00022346384 |
| 539 |
Fast Time Sequence Indexing for Arbitrary L_p Norms |
2000 |
VLDB |
0.00020666392 |
| 597 |
Computing Iceberg Queries Efficiently |
1998 |
VLDB |
0.00019475592 |
| 865 |
What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically |
2003 |
PODS |
0.00015808172 |
| 1,392 |
Sketching Streams Through the Net: Distributed Approximate Query Tracking |
2005 |
VLDB |
0.00012229045 |
| 1,472 |
Space Efficient Mining of Multigraph Streams |
2005 |
PODS |
0.00011828662 |
| 1,629 |
Space-optimal Heavy Hitters with Strong Error Bounds |
2009 |
PODS |
0.00011085267 |
| 1,955 |
Efficient Computation of Iceberg Cubes with Complex Measures |
2001 |
SIGMOD |
9.9629452e-05 |
| 2,282 |
Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling |
2005 |
VLDB |
9.1073603e-05 |
| 2,955 |
Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams |
2006 |
PODS |
7.8239173e-05 |
| 3,050 |
Comparing Data Streams Using Hamming Norms (How to Zero In) |
2002 |
VLDB |
7.6512619e-05 |
| 3,660 |
Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams |
2005 |
PODS |
6.8691367e-05 |
| 5,594 |
Time-Decaying Aggregates in Out-of-order Streams |
2008 |
PODS |
5.4192122e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 344 |
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries |
2001 |
VLDB |
0.00026702512 |
| 7,480 |
Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms |
2024 |
SIGMOD |
4.7180617e-05 |
| 7,145 |
Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model |
2019 |
PODS |
4.8179617e-05 |
| 6,418 |
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems |
2016 |
PODS |
5.0696932e-05 |
| 10,983 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1945683e-05 |
| 4,382 |
Rectangle-Efficient Aggregation in Spatial Data Streams |
2012 |
PODS |
6.2386853e-05 |
| 11,833 |
Streaming Algorithms for Robust Distinct Elements |
2016 |
SIGMOD |
4.1945683e-05 |
| 11,361 |
Approximate Range Thresholding |
2022 |
SIGMOD |
4.1945683e-05 |
| 2,955 |
Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams |
2006 |
PODS |
7.8239173e-05 |
| 11,855 |
Range Thresholding on Streams |
2016 |
SIGMOD |
4.1945683e-05 |