Efficient sketches for the set query problem
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
Abstract: We develop an algorithm for estimating the values of a vector x in R^n over a support S of size k from a randomized sparse binary linear sketch Ax of size O(k). Given Ax and S, we can recover x' with ||x' - x_S||_2 <= eps ||x - x_S||_2 with probability at least 1 - k^{-Omega(1)}. The recovery takes O(k) time. While interesting in its own right, this primitive also has a number of applications. For example, we can: 1. Improve the linear k-sparse recovery of heavy hitters in Zipfian distributions with O(k log n) space from a (1+eps) approximation to a (1 + o(1)) approximation, giving the first such approximation in O(k log n) space when k <= O(n^{1-eps}). 2. Recover block-sparse vectors with O(k) space and a (1+eps) approximation. Previous algorithms required either omega(k) space or omega(1) approximation.
Recommendations
- Deterministic heavy hitters with sublinear query time
- On deterministic sketching and streaming for sparse recovery and norm estimation
- Improved concentration bounds for count-sketch
- On deterministic sketching and streaming for sparse recovery and norm estimation
- An improved data stream summary: the count-min sketch and its applications
Cited in
(4)
This page was built for publication: Efficient sketches for the set query problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365020)
