Fast Manhattan sketches in data streams

No abstract is available for this paper.

• Publication year

  2010

• Venue

  ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

• Publication date

  2010-06-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1807085.1807101
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the exact space complexity of sketching and streaming small norms

  2010cited by this paper
• Coresets and sketches for high dimensional subspace approximation problems

  2010cited by this paper
• 1-pass relative-error Lp-sampling with applications

  2010cited by this paper
• Space-optimal heavy hitters with strong error bounds

  2010cited by this paper
• Functionally Private Approximations of Negligibly-Biased Estimators

  2009cited by this paper
• A Near-Optimal Algorithm for L1-Difference

  2009cited by this paper
• The Data Stream Space Complexity of Cascaded Norms

  2009cited by this paper
• Declaring independence via the sketching of sketches

  2008cited by this paper
• Time-decaying aggregates in out-of-order streams

  2008cited by this paper
• Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections

  2008influential reference
• Finding Frequent Items over General Update Streams

  2008cited by this paper
• Uniform Hashing in Constant Time and Optimal Space

  2008cited by this paper
• Reversible Sketches: Enabling Monitoring and Analysis Over High-Speed Data Streams

  2007cited by this paper
• OPEN PROBLEMS IN DATA STREAMS AND RELATED TOPICS IITK WORKSHOP ON ALGORITHMS FOR DATA STREAMS ’06

  2007cited by this paper
• DATALITE: a distributed architecture for traffic analysis via light-weight traffic digest

  2007cited by this paper
• One sketch for all: fast algorithms for compressed sensing

  2007cited by this paper
• Algorithms and estimators for accurate summarization of internet traffic

  2007cited by this paper
• On Estimating Frequency Moments of Data Streams

  2007influential reference
• Semidefinite Representation of the k-Ellipse

  2007cited by this paper
• Very sparse random projections

  2006influential reference
• Polylogarithmic Private Approximations and Efficient Matching

  2006cited by this paper
• Space- and time-efficient deterministic algorithms for biased quantiles over data streams

  2006cited by this paper
• Sketching Streams Through the Net: Distributed Approximate Query Tracking

  2005cited by this paper
• A Hardware-Based Clustering Approach for Anomaly Detection

  2005cited by this paper
• Space efficient mining of multigraph streams

  2005cited by this paper
• Subgradient and sampling algorithms for l1 regression

  2005cited by this paper
• Space complexity of hierarchical heavy hitters in multi-dimensional data streams

  2005cited by this paper
• Robust Regression and Outlier Detection

  2005cited by this paper
• Stable signal recovery from incomplete and inaccurate measurements

  2005cited by this paper
• Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling

  2005cited by this paper
• Tabulation based 4-universal hashing with applications to second moment estimation

  2004influential reference
• An improved data stream summary: the count-min sketch and its applications

  2004cited by this paper
• Optimal space lower bounds for all frequency moments

  2004cited by this paper
• What's hot and what's not: tracking most frequent items dynamically

  2003cited by this paper
• Uniform hashing in constant time and linear space

  2003influential reference
• Abstract The

  2002influential reference
• Finding frequent items in data streams

  2002influential reference
• Comparing Data Streams Using Hamming Norms (How to Zero In)

  2002cited by this paper
• Fast mining of massive tabular data via approximate distance computations

  2002cited by this paper
• On the Surprising Behavior of Distance Metrics in High Dimensional Spaces

  2001cited by this paper
• Efficient computation of Iceberg cubes with complex measures

  2001cited by this paper
• Stable distributions, pseudorandom generators, embeddings and data stream computation

  2000influential reference
• Fast Time Sequence Indexing for Arbitrary Lp Norms

  2000cited by this paper
• An Approximate Lp Difference Algorithm for Massive Data Streams

  1999cited by this paper
• Bottom-up computation of sparse and Iceberg CUBE

  1999cited by this paper
• On random sampling over joins

  1999cited by this paper
• Mathematical programming algorithms for regression-based nonlinear filtering in RN

  1999cited by this paper
• Computing Iceberg Queries Efficiently

  1998cited by this paper
• L[1]-statistical procedures and related topics

  1997cited by this paper
• Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases

  1995influential reference
• Pseudorandom generators for space-bounded computation

  1992influential reference
• Another proof of the defect relation for moving targets

  1991cited by this paper
• Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices

  1991cited by this paper
• Pseudorandom generators for space-bounded computations

  1990cited by this paper

• Enabling General and Efficient Window Mechanism for In-Network Telemetry

  2026cites this paper
• Federated Data Shift Distance Estimation

  2025cites this paper
• OmniWindow: A General and Efficient Window Mechanism Framework for Network Telemetry

  2023cites this paper
• Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

  2023influential citation
• Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

  2022cites this paper
• Differentially Private Frequency Moments Estimation with Polylogarithmic Space

  2021cites this paper
• Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

  2021cites this paper
• A Fast and Compact Invertible Sketch for Network-Wide Heavy Flow Detection

  2019cites this paper
• MV-Sketch: A Fast and Compact Invertible Sketch for Heavy Flow Detection in Network Data Streams

  2019cites this paper
• Streaming Algorithms for High Throughput Massive Datasets

  2017cites this paper
• Continuous monitoring of $\ell_p$ norms in data streams

  2017cites this paper
• Continuous monitoring of 𝓁p norms in data streams

  2017cites this paper
• Heavy Hitters via Cluster-Preserving Clustering

  2016cites this paper
• On approximating functions of the singular values in a stream

  2016cites this paper
• Interacting with Large Distributed Datasets Using Sketch

  2016cites this paper
• Efficient Genome-Wide, Privacy-Preserving Similar Patient Query based on Private Edit Distance

  2015cites this paper
• A Unified Framework for Linear Dimensionality Reduction in L1

  2014cites this paper
• An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits

  2014cites this paper
• Approximating Large Frequency Moments with O(n1-2/k) Bits

  2014cites this paper
• Data Streaming Algorithms for Rapid Cyber Attack Detection

  2013cites this paper
• Tight Lower Bound for Linear Sketches of Moments

  2013cites this paper
• Fast, Scalable Algorithms for Reinforcement Learning in High Dimensional Domains

  2013cites this paper
• Mergeable summaries

  2013cites this paper
• Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams

  2013cites this paper
• A fast sketch for aggregate queries over high-speed network traffic

  2012cites this paper
• Mergeable summaries

  2012cites this paper
• Low rank approximation and regression in input sparsity time

  2012cites this paper
• Low-Rank Approximation and Regression in Input Sparsity Time

  2012cites this paper
• Approximating Large Frequency Moments with Pick-and-Drop Sampling

  2012cites this paper
• Sketching and streaming high-dimensional vectors

  2011influential citation
• Mergeable Coresets

  2011cites this paper
• Near-optimal private approximation protocols via a black box transformation

  2011cites this paper
• Fast moment estimation in data streams in optimal space

  2010influential citation
• Streaming Algorithms from Precision Sampling

  2010cites this paper
• Recursive Sketching For Frequency Moments

  2010cites this paper
• Streaming Algorithms via Precision Sampling

  2010cites this paper