Towards Estimation Error Guarantees for Distinct Values.

@inproceedings{DBLP:conf/pods/CharikarCMN00,
  author    = {Moses Charikar and
               Surajit Chaudhuri and
               Rajeev Motwani and
               Vivek R. Narasayya},
  title     = {Towards Estimation Error Guarantees for Distinct Values},
  booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
               on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
               USA},
  publisher = {ACM},
  year      = {2000},
  isbn      = {1-58113-214-X},
  pages     = {268-279},
  ee        = {http://doi.acm.org/10.1145/335168.335230, db/conf/pods/CharikarCMN00.html},
  crossref  = {DBLP:conf/pods/00},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 2000 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.

Printed Edition

Online Edition: ACM Digital Library

References

[1]

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

[2]

Morton M. Astrahan, Mario Schkolnick, Kyu-Young Whang: Approximating the number of unique values of an attribute without sorting. Inf. Syst. 12(1): 11-15(1987)

[3]

...

[4]

...

[5]

...

[6]

...

[7]

...

[8]

Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998: 436-447

[9]

Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: On Random Sampling over Joins. SIGMOD Conference 1999: 263-274

[10]

Surajit Chaudhuri, Vivek R. Narasayya: An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server. VLDB 1997: 146-155

[11]

Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)

[12]

Philippe Flajolet, G. Nigel Martin: Probabilistic Counting. FOCS 1983: 76-82

[13]

...

[14]

...

[15]

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

[16]

...

[17]

...

[18]

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

[19]

Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989: 68-77

[20]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X

[21]

Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press 1995, ISBN 0-521-47465-5

[22]

Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513

[23]

Frank Olken: Random Sampling from Databases. Ph.D. thesis, University of California at Berkeley LBL Technical Report 1993

[24]

...

[25]

Gultekin Özsoyoglu, Kaizheng Du, A. Tjahjana, Wen-Chi Hou, D. Y. Rowland: On Estimating COUNT, SUM, and AVERAGE. DEXA 1991: 406-412

[26]

Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305

[27]

...

[28]

H. S. Sichel: Anatomy of the Generalized Inverse Gaussian-Poisson Distribution with Special Applications to Bibliometric Studies. Inf. Process. Manage. 28(1): 5-18(1992)

[29]

...

[30]

Kyu-Young Whang, Brad T. Vander Zanden, Howard M. Taylor: A Linear-Time Probabilistic Counting Algorithm for Database Applications. ACM Trans. Database Syst. 15(2): 208-229(1990)

[31]

George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949