Tracking Join and Self-Join Sizes in Limited Storage.

@inproceedings{DBLP:conf/pods/AlonGMS99,
  author    = {Noga Alon and
               Phillip B. Gibbons and
               Yossi Matias and
               Mario Szegedy},
  title     = {Tracking Join and Self-Join Sizes in Limited Storage},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {10-20},
  ee        = {http://doi.acm.org/10.1145/303976.303978, db/conf/pods/AlonGMS99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[AGP99]

...

[AGPR99]

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy: Join Synopses for Approximate Query Answering. SIGMOD Conference 1999: 275-286 BibTeX

[AMS96]

Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29 BibTeX

[BDF+97]

Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997) BibTeX

[GGMS96]

Sumit Ganguly, Phillip B. Gibbons, Yossi Matias, Abraham Silberschatz: Bifocal Sampling for Skew-Resistant Join Size Estimation. SIGMOD Conference 1996: 271-281 BibTeX

[GM98a]

Phillip B. Gibbons, Yossi Matias: New Sampling-Based Summary Statistics for Improving Approximate Query Answers. SIGMOD Conference 1998: 331-342 BibTeX

[GM98b]

...

[GMP97a]

...

[GMP97b]

Phillip B. Gibbons, Yossi Matias, Viswanath Poosala: Fast Incremental Maintenance of Approximate Histograms. VLDB 1997: 466-475 BibTeX

[Goo89]

...

[HH99]

Peter J. Haas, Joseph M. Hellerstein: Ripple Joins for Online Aggregation. SIGMOD Conference 1999: 287-298 BibTeX

[HHW97]

Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182 BibTeX

[HNSS93]

Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Fixed-Precision Estimation of Join Selectivity. PODS 1993: 190-201 BibTeX

[HNSS95]

Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Lynne Stokes: Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995: 311-322 BibTeX

[HÖT88]

Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287 BibTeX

[IP95]

Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244 BibTeX

[LN95]

Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. J. Comput. Syst. Sci. 51(1): 18-25(1995) BibTeX

[LNS90]

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11 BibTeX

[MRL98]

Gurmeet Singh Manku, Sridhar Rajagopalan, Bruce G. Lindsay: Approximate Medians and other Quantiles in One Pass and with Limited Memory. SIGMOD Conference 1998: 426-435 BibTeX

[MS99]

...

[Poo97]

Viswanath Poosala: Histogram-Based Estimation Techniques in Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1997
BibTeX

[Vit85]

Jeffrey Scott Vitter: Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11(1): 37-57(1985) BibTeX

[VL93]

Susan V. Vrbsky, Jane W.-S. Liu: APPROXIMATE - A Query Processor that Produces Monotonically Improving Approximate Answers. IEEE Trans. Knowl. Data Eng. 5(6): 1056-1068(1993) BibTeX