Article

Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries

Authors:

Anna C. Gilbert,

Yannis Kotidis,

S. Muthukrishnan,

Martin StraussAuthors Info & Claims

VLDB '01: Proceedings of the 27th International Conference on Very Large Data Bases

Pages 79 - 88

Published: 11 September 2001 Publication History

Get Access

Abstract

No abstract available.

References

[1]

{1} A. Aboulnaga and S. Chaudhuri Self-tuning Histograms: Building Histograms Without Looking at Data. In Proceedings of the ACM SIGMOD Conference, June 1999.

Digital Library

Google Scholar

[2]

{2} N. Alon, P. Gibbons, Y. Matias and M. Szegedy. Tracking join and self-join sizes in limited storage. In ACM Symposium on Principles of Database Systems (PODS), 1999.

Digital Library

Google Scholar

[3]

{3} N. Alon, Y. Matias and M. Szegedy The Space Complexity of Approximating the Frequency Moments. In ACM Symp on Theory of Computing (STOC), pages 20-29, 1996.

Digital Library

Google Scholar

[4]

{4} S. Chaudhuri and L. Gravano. Evaluating Top-k Selection Queries. In Proceedings of VLDB Conference, 1999.

Digital Library

Google Scholar

[5]

{5} K. Chan and A. Fu. Efficient Time Series Matching by Wavelets. In Proceedings of ICDE, pages 126-133, 1999.

Digital Library

Google Scholar

[6]

{6} C. K. Chui. An Introduction to Wavelets Wavelet Analysis and its Applications, Vol 1, Academic Press, 1992.

Digital Library

Google Scholar

[7]

{7} C. Cortes and D. Pregibon. Signature-based Methods for Data Streams. KDD, to appear.

Digital Library

Google Scholar

[8]

{8} C. Cortes, K. Fisher, D. Pregibon, A. Rogers and F. Smith. Hancock: A Language for Extracting Signatures from Data Streams. In KDD, pages 9-17, August 2000.

Digital Library

Google Scholar

[9]

{9} K. Chakrabarti, M. Garofalakis, R. Rastogi and K. Shim. Approximate Query Processing Using Wavelets. In Proceedings of VLDB, pages 111-122, September 2000.

Digital Library

Google Scholar

[10]

{10} P. Domingos and G. Hulten. Mining High-Speed Data Streams, P. Domingos, G. Hulten. In KDD, August 2000.

Digital Library

Google Scholar

[11]

{11} M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani and J. Ullman. Computing Iceberg Queries Efficiently. In Proceedings of VLDB Conference, pages 299-310, 1998.

Digital Library

Google Scholar

[12]

{12} J. Feigenbaum, S. Kannan, M. Strauss and M. Viswanathan. An Approximate L ¹-Difference Algorithm for Massive Data Streams. In FOCS, pages 501-511, 1999.

Digital Library

Google Scholar

[13]

{13} J. Feigenbaum, S. Kannan, M. Strauss and M. Viswanathan Testing and Spot-Checking of Data Streams. In SODA, pages 165-174, January 2000.

Digital Library

Google Scholar

[14]

{14} V. Ganti, J. Gehrke and R. Ramakrishnan. Mining Very Large Databases. In IEEE Computer 32(8), 1999.

Digital Library

Google Scholar

[15]

{15} J. Gehrke, F. Korn and D. Srivastava. On Computing Correlated Aggregates Over Continual Data Streams. In Proceedings of the ACM SIGMOD Conference, May 2001.

Digital Library

Google Scholar

[16]

{16} A. Gilbert, Y. Kotidis, S. Muthukrishnan and M. Strauss. Optimal and Approximate Computation of Summary Statistics for Range Aggregates. In Proceedings of PODS, pages 227-236, May 2001.

Digital Library

Google Scholar

[17]

{17} M. Greenwald and S. Khanna. Space-Efficient Online Computation of Quantile Summaries. In SIGMOD, 2001.

Digital Library

Google Scholar

[18]

{18} P. Gibbons, Y. Matias and V. Poosala. Fast Incremental Maintenance of Approximate Histograms. In Proceedings of VLDB, Athens, Greece, pages 466-475, August 1997.

Digital Library

Google Scholar

[19]

{19} P. Gibbons and Y. Matias. New Sampling-Based Summary Statistics for Improving Approximate Query Answers. In Proceedings of the ACM SIGMOD Conference, June 1998.

Digital Library

Google Scholar

[20]

{20} S. Guha, N. Mishra, R. Motwani and L. O'Callaghan. Clustering Data Streams. In FOCS, pages 359-366, Nov. 2000.

Digital Library

Google Scholar

[21]

{21} M. Henzinger, P. Raghavan and S. Rajagopalan. Computing on Data Streams. DEC SRC TR 1998-011, 1998.

Google Scholar

[22]

{22} P. Indyk. Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. FOCS, 2000.

Digital Library

Google Scholar

[23]

{23} J. Lee, D. Kim and C. Chung. Multi-dimensional Selectivity Estimation Using Compressed Histogram Information In Proceedings of the ACM SIGMOD Conference, June 1999.

Digital Library

Google Scholar

[24]

{24} F. MacWilliams and N. Sloane. The Theory of Error-Correcting Codes. North Holland Mathematical Library, Vol. 16, North Holland, New York, 1977.

Google Scholar

[25]

{25} G. Manku, S. Rajagopalan and B. Lindsay. Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. In SIGMOD, 1999.

Digital Library

Google Scholar

[26]

{26} Y. Matias, J. S. Vitter, and M. Wang. Wavelet-Based Histograms for Selectivity Estimation. In SIGMOD, 1998.

Digital Library

Google Scholar

[27]

{27} Y. Matias, J. Vitter and M.Wang. Dynamic Maintenance of Wavelet-based Histograms. In Proc. of VLDB, Sept. 2000.

Digital Library

Google Scholar

[28]

{28} V. Poosala. Histogram-Based Estimation Techniques in Database Systems. Ph. D. dissertation, University of Wisconsin-Madion, 1997.

Digital Library

Google Scholar

[29]

{29} Y. Wu, D. Agrawal and A. Abbadi. Using the Golden Rule of Sampling for Query Estimation. In SIGMOD, May 2001.

Digital Library

Google Scholar

[30]

{30} J. Vitter and M. Wang. Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets. In Proceedings of ACM SIGMOD Conference, June 1999.

Digital Library

Google Scholar

[31]

{31} J. Vitter, M. Wang and B. Iyer. Data Cube Approximation and Histograms via Wavelets. In CIKM, November 1998.

Digital Library

Google Scholar

[32]

{32} http://www-db.stanford.edu/stream/

Google Scholar

[33]

{33} http://www.cs.cornell.edu/database/Himalaya/

Google Scholar

Cited By

View all

Heddes MNunes IGivargis TNicolau A(2024)Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join QueriesProceedings of the ACM on Management of Data10.1145/36549322:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654932
Mytilinis ITsoumakos DKoziris N(2021)Workload-aware wavelet synopses for sliding window aggregatesDistributed and Parallel Databases10.1007/s10619-020-07307-w39:2(445-482)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10619-020-07307-w
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
Show More Cited By

Recommendations

Punctuated data streams
Sliding-window top-k queries on uncertain streams

Recently, due to the imprecise nature of the data generated from a variety of streaming applications, such as sensor networks, query processing on uncertain data streams has become an important problem. However, all the existing works on uncertain data ...
Condensative stream query language for data streams
ADC '07: Proceedings of the eighteenth conference on Australasian database - Volume 63

In contrast to traditional database queries, a query on stream data is continuous in that it is periodically evaluated over fractions (sliding windows) of the data stream. This introduces challenges beyond those encountered when processing traditional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VLDB '01: Proceedings of the 27th International Conference on Very Large Data Bases

September 2001

709 pages

ISBN:1558608044

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 11 September 2001

Qualifiers

Article

Conference

VLDB01

VLDB01: 27th International Conference on Very Large Data Bases

September 11 - 14, 2001

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Heddes MNunes IGivargis TNicolau A(2024)Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join QueriesProceedings of the ACM on Management of Data10.1145/36549322:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654932
Mytilinis ITsoumakos DKoziris N(2021)Workload-aware wavelet synopses for sliding window aggregatesDistributed and Parallel Databases10.1007/s10619-020-07307-w39:2(445-482)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10619-020-07307-w
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
Levchenko OYagoubi DAkbarinia RMasseglia FKolev BShasha DCuzzocrea AAllan JPaton NSrivastava DAgrawal RBroder AZaki MCandan SLabrinidis ASchuster AWang H(2018)Spark-parSketchProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3269226(1951-1954)Online publication date: 17-Oct-2018
https://dl.acm.org/doi/10.1145/3269206.3269226
Zitouni MAkbarinia RYahia SMasseglia FHaddad HWainwright RChbeir R(2018)Maximally informative k-itemset mining from massively distributed data streamsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167187(502-509)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167187
Tolosana-Calasanz RDiaz-Montes JRana OParashar M(2017)Feedback-Control & Queueing Theory-Based Resource Management for Streaming ApplicationsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.260351028:4(1061-1075)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2603510
Hegde CIndyk PSchmidt L(2016)Fast recovery from a union of subspacesProceedings of the 30th International Conference on Neural Information Processing Systems10.5555/3157382.3157589(4401-4409)Online publication date: 5-Dec-2016
https://dl.acm.org/doi/10.5555/3157382.3157589
Gál AJang JLimaye NMahajan MSreenivasaiah K(2016)Space-Efficient Approximations for Subset SumACM Transactions on Computation Theory10.1145/28948438:4(1-28)Online publication date: 29-Jun-2016
https://dl.acm.org/doi/10.1145/2894843
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
Roy PKhan AAlonso GÖzcan FKoutrika GMadden S(2016)Augmented SketchProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882948(1449-1463)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882948
Show More Cited By

View Options

Get Access

Login options

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

Abstract

References

Cited By

Recommendations

Punctuated data streams

Sliding-window top-k queries on uncertain streams

Condensative stream query language for data streams

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations