Space efficiency in Synopsis construction algorithms

Summary: Introduces a general technique to reduce the working space of optimal and approximate histogram/wavelet synopsis construction algorithms, showing that explicit “working space” is redundant. The method retrofits existing dynamic programs and delivers practical gains on real and synthetic data. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9513
Venue: VLDB
Year: 2005
Pagerank: 6.4940349e-05
Overall Rank: 4,819 | 66.94%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sudipto Guha (University of Pennsylvania)

BibTeX Citation

@article{guha_vldb05,
        title = {{Space efficiency in Synopsis construction algorithms}},
        author = {Guha, Sudipto},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {409},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,375	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.6299286e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
11,563	SIEVE: A Space-Efficient Algorithm for Viterbi Decoding	2022	SIGMOD	5.093636e-05
11,957	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
9	Online Aggregation	1997	SIGMOD	0.00077458002
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00026105472
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.8448865e-05
4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.7605683e-05
5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD	6.1337629e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
2	136	Join Synopses for Approximate Query Answering	1999	SIGMOD
3	723	Dynamic Multidimensional Histograms	2002	SIGMOD
4	5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB
5	307	Approximate Query Processing Using Wavelets	2000	VLDB
6	7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS
7	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
8	7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB
9	10,182	The Space-Time Complexity of Sum-Product Queries	2026	PODS
10	13,868	Offline and Data Stream algorithms for efficient computation of synopsis structures	2005	VLDB