Towards estimation error guarantees for distinct values

ABSTRACT

We consider the problem of estimating the number of distinct values in a column of a table. For large tables without an index on the column, random sampling appears to be the only scalable approach for estimating the number of distinct values. We establish a powerful negative result stating that no estimator can guarantee small error across all input distributions, unless it examines a large fraction of the input data. In fact, any estimator must incur a significant error on at least some of a natural class of distributions. We then provide a new estimator which is provably optimal, in that its error is guaranteed to essentially match our negative result. A drawback of this estimator is that while its worst-case error is reasonable, it does not necessarily give the best possible error bound on any given distribution. Therefore, we develop heuristic estimators that are optimized for a class of typical input distributions. While these estimators lack strong guarantees on distribution-independent worst-case error, our extensive empirical comparison indicate their effectiveness both on real data sets and on synthetic data sets.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: Morton M. Astrahan , Mario Schkolnick , Kyu-Young Whang, Approximating the number of unique values of an attribute without sorting, Information Systems, v.12 n.1, p.11-15, Jan. 1987 [doi>10.1016/0306-4379(87)90014-7]
• 3: J. Bunge and M. Fitzpatrick. Estimating the Number of Species: A Review. Journal of the American Statistical Association 88(1993): 364-373.
• 4: K.P. Burnham and W.S. Overton. Estimation of the size of a closed population when capture possibilities vary among animals. Biometrika 65(1978): 625-633.
• 5: K.P. Burnham and W.S. Overton. Robust estimation of population size when capture possibilities vary among animals. Ecology 60(1979): 927-936.
• 6: A. Chao. Nonparametric estimation of the number of classes in a population. Scandinavian Journal of Statistical Theory and Applications 11(1984): 265-270.
• 7: A. Chao and S. Lee. Estimating the number of classes via sample coverage. Journal of the American Statistical Association 87(1992): 210-217.
• 8: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 9: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 11: S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988 [doi>10.1145/42201.42205]
• 12: P. Flajolet and G.N. Martin. Probabilistic counting. In Proceedings of the IEEE Symposium on the Foundations of Computer Science, 1983, pp. 76-82.
• 13: Information and Computer Science, University of California, Irvine. ftp://ftp.ics.uci.edu/pub/machinele arnin g-d at abases
• 14: L.A. Goodman. On the estimation of the number of classes in a population. Annals of Mathematical Statistics 20(1949): 572-579.
• 15: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 16: P.J. Haas and L. Stokes. Estimating the number of classes in a finite population. In Journal of the American Statistical Association, 93(1998): 1475-1487.
• 17: J.F. Heltshe and N.E. Forrester. Estimating species richness using the jackknife procedure. Biometrics 39(1983): 1-11.
• 18: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• 19: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
• 20: D.E. Knuth. Sorting and Searching, Volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1971.
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: Jeffrey F. Naughton , S. Seshadri, On estimating the size of projections, Proceedings of the third international conference on database theory on Database theory, p.499-513, November 1990, Paris, France
• 23: F. Olken. Random Sampling from Databases. PhD Thesis, Computer Science, U.C. Berkeley, 1993.
• 24: F. Olken and D. Rotem. Random Sampling from Databases- A Survey. Manuscript, 1995.
• 25: G. Ozsoyoglu, K. Du, a. Tjahjana, W. Hou, and D.Y. Rowland. On estimating COUNT, SUM, and AV- ERAGE relational algebra queries. In Proceedings of the Conference on Database and Ezpert Systems Applications, pages 406-412, 1991.
• 26: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 27: A. Shlosser. On estimation of the size of the dictionary of a long text on the basis of a sample. Engineering Cybernetics 19(1981): 97-102.
• 28: H. S. Sichel, Anatomy of the generalized inverse Gaussian-Poisson distribution with special applications to bibliometric studies, Information Processing and Management: an International Journal, v.28 n.1, p.5-17, Jan. 1992 [doi>10.1016/0306-4573(92)90088-H]
• 29: E.P. Smith and G. Belle. Nonparametric estimation of species richness. Biometrics 40(1984):119-129.
• 30: Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990 [doi>10.1145/78922.78925]
• 31: G.E. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley Press, Inc, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Languages