Offline and Data Stream algorithms for efficient computation of synopsis structures

Summary: Tutorial surveying near-optimal offline and streaming algorithms for wavelet and histogram synopsis construction. Unifies recurring algorithmic techniques, mathematical intuition, and database applications across compact representations and data streams. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9483
Venue: VLDB
Year: 2005
Pagerank: -
Overall Rank: 13,868 | 4.86%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Sudipto Guha (University of Pennsylvania)
2. Kyuseok Shim (Seoul National University)

BibTeX Citation

@article{guha_vldb05,
        title = {{Offline and Data Stream algorithms for efficient computation of synopsis structures}},
        author = {Guha, Sudipto and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {1364},
        year = {2005}
}

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
1	4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB
2	168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
3	363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB
4	4,695	Graph Synopses, Sketches, and Streams: A Survey	2012	VLDB
5	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
6	307	Approximate Query Processing Using Wavelets	2000	VLDB
7	213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
8	311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB
9	1,274	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD
10	4,819	Space efficiency in Synopsis construction algorithms	2005	VLDB