Offline and Data Stream algorithms for efficient computation of synopsis structures

Summary: Survey of offline and streaming algorithms for synopsis structures (wavelet, histogram) in OLAP, AQP and mining; near-optimal guarantees. Unifies core techniques and a self-contained roadmap to extend these methods to new data-management problems in VLDB-scale systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9292
Venue: VLDB
Year: 2005
Pagerank: -
Overall Rank: 13,667 | 4.93%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Sudipto Guha
2. Kyuseok Shim

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
4,659	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.0160083e-05
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
4,900	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB	5.8423536e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026702512
1,222	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00013213129
3,719	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8204683e-05