Statistical Profile Estimation

Survey

• Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988)

• Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34

1980

• Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63

1983

• Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983)
• Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54

1984

• Stavros Christodoulakis: Estimating Block Selectivities. Inf. Syst. 9(1): 69-79,(1984)
• Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276

1985

• Neil C. Rowe: Antisampling for Estimation: An Overview. IEEE Trans. Software Eng. 11(10): 1081-1091(1985)

1986

• Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127

1987

• 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)

1988

• Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287
• M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988: 28-36
• Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251
• Neil C. Rowe: Absolute Bounds on Set Intersection and Union Sizes from Distribution Information. IEEE Trans. Software Eng. 14(7): 1033-1048(1988)

1989

• Meng Chang Chen, Lawrence McNamee: On the Data Model and Access Method of Summary Data Management. IEEE Trans. Knowl. Data Eng. 1(4): 519-529(1989)
• Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
• Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989: 68-77
• Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
• Rafiul Ahad, K. V. Bapa Rao, Dennis McLeod: On Estimating the Cardinality of the Projection of a Database Relation. ACM Trans. Database Syst. 14(1): 28-40(1989)
• Danièle Gardy, Claude Puech: On the Effects of Join Operations on Relation Sizes. ACM Trans. Database Syst. 14(4): 574-603(1989)

1990

• Meng Chang Chen, Lawrence McNamee, Norman S. Matloff: Selectivity Estimation Using Homogeneity Measurement. ICDE 1990: 304-310
• Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
• Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513

1991

• Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277

1992

• Peter J. Haas, Arun N. Swami: Sequential Sampling Procedures for Query Size Estimation. SIGMOD Conference 1992: 341-350

1993

• Allen Van Gelder: Multiple Join Size Estimation by Virtual Domains. PODS 1993: 180-189
• Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Fixed-Precision Estimation of Join Selectivity. PODS 1993: 190-201
• Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267
• Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88
• HweeHwa Pang, Michael J. Carey, Miron Livny: Partially Preemptive Hash Joins. SIGMOD Conference 1993: 59-68
• Yannis E. Ioannidis, Stavros Christodoulakis: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM Trans. Database Syst. 18(4): 709-748(1993)
• Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1&2): 195-226(1993)

1994

• Peter J. Haas, Jeffrey F. Naughton, Arun N. Swami: On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994: 14-24
• Chung-Min Chen, Nick Roussopoulos: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994: 161-172
• Arun N. Swami, K. Bernhard Schiefer: Estimating Page Fetches for Index Scans with Finite LRU Buffers. SIGMOD Conference 1994: 173-184
• Arun N. Swami, K. Bernhard Schiefer: On the Estimation of Join Result Sizes. EDBT 1994: 287-300

1995

• Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310
• 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
• Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244
• Peter J. Haas, Arun N. Swami: Sampling-Based Selectivity Estimation for Joins Using Augmented Frequent Value Statistics. ICDE 1995: 522-531