Tracking Join and Self-Join Sizes in Limited Storage

Noga Alon; Phillip B. Gibbons; Yossi Matias; Mario Szegedy

doi:10.1006/jcss.2001.1813

journal article Open Access May 01, 2002

Tracking Join and Self-Join Sizes in Limited Storage

Noga Alon

Phillip B. Gibbons Yossi Matias

Mario Szegedy

Journal of Computer and System Sciences Vol. 64 No. 3 pp. 719-747 · Elsevier BV

View at Publisher Save 10.1006/jcss.2001.1813

Topics

No keywords indexed for this article. Browse by subject →

References

31

[1]

Acharya "Congressional samples for approximate answering of group-by queries" (2000)

[2]

Acharya "Join synopses for approximate query answering" (1999)

[3]

Alon "The space complexity of approximating the frequency moments" J. Comput. System Sci. (1999) 10.1006/jcss.1997.1545

[4]

Barbará "The New Jersey data reduction report" Bull. Tech. Comm. Data Engrg. (1997)

[5]

Charikar "Towards estimation error guarantees for distinct values" (2000)

[6]

Chaudhuri "A robust, optimization-based approach for approximate answering of aggregate queries" (2001)

[7]

Chakrabarti "Approximate query processing using wavelets" (2000)

[8]

Ganguly "Bifocal sampling for skew-resistant join size estimation" (1996)

[9]

Gibbons "Distinct sampling for highly-accurate answers to distinct values queries and event reports" (2001)

[10]

Gilbert "Surfing wavelets on streams: One-pass summaries for approximate aggregate queries" (2001)

[11]

Ganti "ICICLES: Self-tuning samples for approximate query answering" (2000)

[12]

Gibbons "New sampling-based summary statistics for improving approximate query answers" (1998)

[13]

Gibbons "Synopsis data structures for massive data sets" (1999)

[14]

Gibbons "Fast incremental maintenance of approximate histograms" (1997)

[15]

Good "Surprise indexes and p-values" J. Statist. Comput. Simul. (1989) 10.1080/00949658908811160

[16]

Haas "Ripple joins for online aggregation" (1999)

[17]

Hellerstein "Online aggregation" (1997)

[18]

Haas "Fixed-precision estimation of join selectivity" (1993)

[19]

Haas "Sampling-based estimation of the number of distinct values of an attribute" (1995)

[20]

Hou "Statistical estimators for relational algebra expressions" (1988)

[21]

Ioannidis "Balancing histogram optimality and practicality for query result size estimation" (1995)

[22]

Ioannidis "Histogram-based techniques for approximating set-valued query-answers" (1999)

[23]

Lazaridis "Progressive approximate aggregate queries with a multi-resolution tree structure" (2001)

[24]

Lipton "Query size estimation by adaptive sampling" J. Comput. System Sci. (1995) 10.1006/jcss.1995.1050

[25]

Lipton "Practical selectivity estimation through adaptive sampling" (1990)

[26]

Matias "Dynamic maintenance of wavelet-based histograms" (2000)

[27]

Olken (1993)

[28]

Poosala (1997)

[29]

Vitter "Random sampling with a reservoir" ACM Trans. Math. Software (1985) 10.1145/3147.3165

[30]

Vrbsky "Approximate—A query processor that produces monotonically improving approximate answers" IEEE Trans. Knowledge Data Engrg. (1993) 10.1109/69.250091

[31]

Vitter "Approximate computation of multidimensional aggregates of sparse data using wavelets" (1999)

Cited By

51

JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation

Feiyu Wang, Qizhi Chen · 2023

Proceedings of the ACM on Managemen...

Sketches for size of join estimation

Florin Rusu, Alin Dobra · 2008

ACM Transactions on Database System...

Metrics

51

Citations

31

References

Details

Published: May 01, 2002
Vol/Issue: 64(3)
Pages: 719-747
License: View

Authors

Cite This Article

Noga Alon, Phillip B. Gibbons, Yossi Matias, et al. (2002). Tracking Join and Self-Join Sizes in Limited Storage. Journal of Computer and System Sciences, 64(3), 719-747. https://doi.org/10.1006/jcss.2001.1813

Tracking Join and Self-Join Sizes in Limited Storage

You May Also Like