Article

Space efficiency in synopsis construction algorithms

Author:

Sudipto GuhaAuthors Info & Claims

VLDB '05: Proceedings of the 31st international conference on Very large data bases

Pages 409 - 420

Published: 30 August 2005 Publication History

Abstract

Histograms and Wavelet synopses have been found to be useful in query optimization, approximate query answering and mining. Over the last few years several good synopsis algorithms have been proposed. These have mostly focused on the running time of the synopsis constructions, optimum or approximate, vis-a-vis their quality. However the space complexity of synopsis construction algorithms has not been investigated as thoroughly. Many of the optimum synopsis construction algorithms (as well as few of the approximate ones) are expensive in space. In this paper, we propose a general technique that reduces space complexity. We show that the notion of "working space" proposed in these contexts is redundant. We believe that our algorithm also generalizes to a broader range of dynamic programs beyond synopsis construction. Our modifications can be easily adapted to existing algorithms. We demonstrate the performance benefits through experiments on real-life and synthetic data.

References

[1]

S. Acharya, P. Gibbons, V. Poosala, and S. Ramaswamy. The Aqua Approximate Query Answering System. SIGMOD Conference, 1999.]]

Digital Library

[2]

L. Amsaleg, P. Bonnet, M. J. Franklin, A. Tomasic, and T. Urhan. Improving responsiveness for wide-area data access. IEEE Data Eng., 20(3):3--11, 1997.]]

[3]

L. Arge. External memory data structures. Proc. of ESA, pages 1--29, 2001.]]

Digital Library

[4]

K. Chakrabarti, M. N. Garofalakis, R. Rastogi, and K. Shim. Approximate query processing using wavelets. VLDB Conference, 2000.]]

Digital Library

[5]

K. Chakrabarti, E. J. Keogh, S. Mehrotra, and M. J. Pazzani. Locally adaptive dimensionality reduction for indexing large time series databases. ACM TODS, 27(2):188--228, 2002.]]

Digital Library

[6]

I. Daubechies. Ten Lectures on Wavelets. SIAM, 1992.]]

Digital Library

[7]

A. Deligiannakis and N. Roussopoulos. Extended wavelets for multiple measures. SIGMOD Conference, 2003.]]

Digital Library

[8]

M. Garofalakis and A. Kumar. Deterministic wavelet thresholding for maximum error metric. Proc. of PODS, 2004.]]

Digital Library

[9]

M. N. Garofalakis and P. B. Gibbons. Probabilistic wavelet synopses. ACM TODS (See also SIGMOD 2002), 29:43--90, 2004.]]

Digital Library

[10]

P. Gibbons and Y. Matias. Synopsis data structures for massive data sets. Proc. of SODA, 1999.]]

Digital Library

[11]

P. Gibbons, Y. Matias, and V. Poosala. Fast Incremental Maintenance of Approximate Histograms. VLDB Conference, 1997.]]

Digital Library

[12]

A. Gilbert, Y. Kotadis, S. Muthukrishnan, and M. Strauss. Surfing Wavelets on Streams: One Pass Summaries for Approximate Aggregate Queries. VLDB Conference, 2001.]]

Digital Library

[13]

S. Guha. Space efficiency in optimal, approximation and streaming algorithms for synopsis construction problems. Manuscript (email for copy)., 2005.]]

[14]

S. Guha and B. Harb. Wavelet synopsis for data streams: Minimizing non-euclidean error. Proc. of SIGKDD Conference, 2005.]]

Digital Library

[15]

S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss. Histogramming data streams with fast per-item processing. Proc. of ICALP, 2002.]]

Digital Library

[16]

S. Guha, N. Koudas, and K. Shim. Data Streams and Histograms. Proc. of STOC, (see also the full version of {16}, available at http://www.cis.upenn.edu/~sudipto/mypapers/histjour.pdf.gz), 2001.]]

Digital Library

[17]

S. Guha, K. Shim, and J. Woo. REHIST: Relative error histogram construction algorithms. VLDB Conference, 2004.]]

[18]

J. M. Hellerstein, P. J. Haas, and H. J. Wang. Online aggregation. SIGMOD Conference, 1997.]]

Digital Library

[19]

Y. E. Ioannidis. Universality of serial histograms. VLDB Conference, 1993.]]

Digital Library

[20]

Y. E. Ioannidis and V. Poosala. Balancing Histogram Optimality and Practicality for Query Result Size Estimation. ACM SIGMOD Conference, 1995.]]

Digital Library

[21]

H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal Histograms with Quality Guarantees. VLDB Conference, 1998.]]

Digital Library

[22]

P. Karras and N. Mamoulis. One pass wavelet synopis for maximum error metrics. This proceeding, 2005.]]

Digital Library

[23]

Y. Matias and D. Urieli. Manuscript. 2004.]]

[24]

Y. Matias, J. S. Vitter, and M. Wang. Wavelet-Based Histograms for Selectivity Estimation. SIGMOD Conference, 1998.]]

Digital Library

[25]

M. Muralikrishna and D. J. DeWitt. Equi-depth histograms for estimating selectivity factors for multidimensional queries. SIGMOD Conference, 1998.]]

Digital Library

[26]

S. Muthukrishnan. Workload optimal wavelet synopsis. DIMACS TR, 2004.]]

[27]

S. Muthukrishnan and M. Strauss. Approximate histogram and wavelet summaries of streaming data. DIMACS TR 52, 2003.]]

[28]

V. Poosala, Y. E. Ioannidis, P. Haas, and E. Shekita. Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference, 1996.]]

Digital Library

[29]

P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. SIGMOD Conference, 1979.]]

Digital Library

[30]

J. S. Vitter. External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv., 33(2):209--271, 2001.]]

Digital Library

Cited By

Ciaperoni MGionis AKatsamanis AKarras PIves ZBonifati AEl Abbadi A(2022)SIEVE: A Space-Efficient Algorithm for Viterbi DecodingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526170(1136-1145)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526170
Mytilinis ITsoumakos DKoziris NMaltzahn CMalik T(2019)Maintaining Wavelet Synopses for Sliding-Window AggregatesProceedings of the 31st International Conference on Scientific and Statistical Database Management10.1145/3335783.3335793(73-84)Online publication date: 23-Jul-2019
https://dl.acm.org/doi/10.1145/3335783.3335793
Kim JMin JShim K(2017)Efficient Haar+ synopsis construction for the maximum absolute error measureProceedings of the VLDB Endowment10.14778/3151113.315111711:1(40-52)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.14778/3151113.3151117
Show More Cited By

Index Terms

Space efficiency in synopsis construction algorithms
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

On the space---time of optimal, approximate and streaming algorithms for synopsis construction problems

Synopses construction algorithms have been found to be of interest in query optimization, approximate query answering and mining, and over the last few years several good synopsis construction algorithms have been proposed. These algorithms have mostly ...
Efficient two-dimensional Haar$$^+$$ synopsis construction for the maximum absolute error measure
Abstract
Several wavelet synopsis construction algorithms were previously proposed for optimal Haar$$^+$$ synopses. Recently, we proposed the OptExtHP-EB algorithm to find an optimal one-dimensional $$\hbox {Haar}^+$$ synopsis. By utilizing the novel ...
Efficient Join Synopsis Maintenance for Data Warehouse
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Various sources such as daily business operations and sensors from different IoT applications constantly generate a lot of data. They are often loaded into a data warehouse system to perform complex analysis over. It, however, can be extremely costly if ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '05: Proceedings of the 31st international conference on Very large data bases

August 2005

1392 pages

ISBN:1595931546

General Chair:
Kjell Bratbergsengen
Norwegian University of Science & Technology, Trondheim, Norway

Publisher

VLDB Endowment

Publication History

Published: 30 August 2005

Qualifiers

Article

Conference

ICMI05

ICMI05: Seventh International Conference on Multimodal Interfaces 2005

August 30 - September 2, 2005

Trondheim, Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
304
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ciaperoni MGionis AKatsamanis AKarras PIves ZBonifati AEl Abbadi A(2022)SIEVE: A Space-Efficient Algorithm for Viterbi DecodingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526170(1136-1145)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526170
Mytilinis ITsoumakos DKoziris NMaltzahn CMalik T(2019)Maintaining Wavelet Synopses for Sliding-Window AggregatesProceedings of the 31st International Conference on Scientific and Statistical Database Management10.1145/3335783.3335793(73-84)Online publication date: 23-Jul-2019
https://dl.acm.org/doi/10.1145/3335783.3335793
Kim JMin JShim K(2017)Efficient Haar+ synopsis construction for the maximum absolute error measureProceedings of the VLDB Endowment10.14778/3151113.315111711:1(40-52)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.14778/3151113.3151117
Mytilinis ITsoumakos DKoziris NÖzcan FKoutrika GMadden S(2016)Distributed Wavelet Thresholding for Maximum Error MetricsProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915230(663-677)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915230
Jiang YPang CZhang HWang JLi TZhang QHe J(2013)Finding the minimum number of elements with sum above a thresholdInformation Sciences: an International Journal10.1016/j.ins.2013.02.035238(205-211)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.ins.2013.02.035
Pang CZhang QZhou XHansen DWang SMaeder A(2013)Computing Unrestricted Synopses Under Maximum Error BoundAlgorithmica10.1007/s00453-011-9571-965:1(1-42)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1007/s00453-011-9571-9
Pang CZhang QHansen DMaeder A(2009)Unrestricted wavelet synopses under maximum error boundProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology10.1145/1516360.1516445(732-743)Online publication date: 24-Mar-2009
https://dl.acm.org/doi/10.1145/1516360.1516445
Guha S(2009)Tight results for clustering and summarizing data streamsProceedings of the 12th International Conference on Database Theory10.1145/1514894.1514926(268-275)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1145/1514894.1514926
Sacharidis DDeligiannakis ASellis T(2009)Hierarchically compressed wavelet synopsesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-008-0096-z18:1(203-231)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s00778-008-0096-z
Pang CZhang QHansen DMaeder A(2007)Building data synopses within a known maximum error boundProceedings of the joint 9th Asia-Pacific web and 8th international conference on web-age information management conference on Advances in data and web management10.5555/1769708.1769768(463-470)Online publication date: 16-Jun-2007
https://dl.acm.org/doi/10.5555/1769708.1769768
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents