Optimal histograms for limiting worst-case error propagation in the size of join results

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal histograms for limiting worst-case error propagation in the size of join results

Full text

Pdf (2.44 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 18 , Issue 4 (December 1993) table of contents

Pages: 709 - 748

Year of Publication: 1993

ISSN:0362-5915

Authors

Yannis E. Ioannidis	University of Wisconsin
Stavros Christodoulakis	Technical University of Crete

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 71, Citation Count: 36

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/169725.169708 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stavros Christodoulakis, Estimating block transfers and join sizes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
	2	S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
	3	CHRISTODOULAKIS, S. On the estimation and use of selectivities in database performance evaluation. Res. Rep. CS-89-24, Dept. of Computer Science, Univ. of Waterloo, June 1989.
	4	Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
	5	IOANNIDIS, Y, AND CHRISTODOULAKIS, S. Error propagation under the uniform distribution assumption. In preparation, 1993.
	6	Nabil Kamel , Roger King, A model of data distribution based on texture analysis, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.319-325, May 1985, Austin, Texas, United States
	7	Robert Philip Kooi, The optimization of queries in relational databases, 1980
	8	Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
	9	Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
	10	Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
	11	MAI~SHALL, A. W., AND OLKIN, I. Inequalities: Theory of Majorzzatzo~ and Its Appl~cattons. Academic Press, New York, 1979.
	12	MERRET% T. H., AND OTOO, E. Distribution models of relations. In Proceedings of the 5th Internatwnal VLDB Conference (Rio de Janiero, Oct. 1979), 418-425.
	13	M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
	14	B. Muthuswamy , Larry Kerschberg, A detailed statistical model for relational query optimization, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.439-448, October 1985, Denver, Colorado, United States [doi>10.1145/320435.320564]
	15	Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	16	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	17	SELINGER, P.G. June 1989. Personal communication.
	18	ZmF, G.K. Human Behavior and the Principle of Least Effort. Addison-Wesley, Reading, Mass., 1949.

CITED BY 36

	Amol Deshpande , Minos Garofalakis , Rajeev Rastogi, Independence is good: dependency-based histogram synopses for high-dimensional data, ACM SIGMOD Record, v.30 n.2, p.199-210, June 2001
	Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, ACM SIGMOD Record, v.24 n.2, p.233-244, May 1995
	Parke Godfrey , Jarek Gryz , Calisto Zuzarte, Exploiting constraint-like data characterizations in query optimization, ACM SIGMOD Record, v.30 n.2, p.582-592, June 2001
	Sudipto Guha , Nick Koudas , Divesh Srivastava, Fast algorithms for hierarchical range histogram construction, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, ACM SIGMOD Record, v.28 n.2, p.239-250, June 1999
	Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
	Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996
	Martin Staudt , René Soiron , Christoph Quix , Matthias Jarke, Query optimization for repository-based applications, Proceedings of the 1999 ACM symposium on Applied computing, p.197-203, February 28-March 02, 1999, San Antonio, Texas, United States
	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California
	Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998
	Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003
	Yibei Ling , Wei Sun , Naphtali D. Rishe , Xianjing Xiang, A Hybrid Estimator for Selectivity Estimation, IEEE Transactions on Knowledge and Data Engineering, v.11 n.2, p.338-354, March 1999
	Hai Wang , Ken Sevcik, Utilizing histogram information, Proceedings of the 2001 conference of the Centre for Advanced Studies on Collaborative research, p.16, November 05-07, 2001, Toronto, Ontario, Canada
	Paolo Ciaccia , Dario Maio, Domains and Active Domains: What This Distinction Implies for the Estimation of Projection Sizes in Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.641-655, August 1995
	Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Optimal histograms for hierarchical range queries (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.196-204, May 15-18, 2000, Dallas, Texas, United States
	Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece
	Ram D. Gopal , R. Ramesh , Stanley Zionts, Criss-Cross Hash Joins: Design and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.637-653, July 2001
	Juliana Freire , Jayant R. Haritsa , Maya Ramanath , Prasan Roy , Jérôme Siméon, StatiX: making XML count, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Raghav Kaushik , Jeffrey F. Naughton , Raghu Ramakrishnan , Venkatesan T. Chakravarthy, Synopses for query optimization: A space-complexity perspective, ACM Transactions on Database Systems (TODS), v.30 n.4, p.1102-1127, December 2005
	Hang T. A. Pham , Kenneth C. Sevcik, Structure choices for two-dimensional histogram construction, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.13-27, October 04-07, 2004, Markham, Ontario, Canada
	Alin Dobra, Histograms revisited: when are histograms the best approximation method for aggregates over joins?, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005
	Raghav Kaushik , Raghu Ramakrishnan , Venkatesan T. Chakaravarthy, Synopses for query optimization: a space-complexity perspective, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Carlo Dell'aquila , Ezio Lefons , Filippo Tangorra, Analytic-based estimation of query result sizes, Proceedings of the 4th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering Data Bases, p.1-7, February 13-15, 2005, Salzburg, Austria
	Xuemin Lin , Qing Zhang , Yidong Yuan , Qing Liu, Error minimization in approximate range aggregates, Data & Knowledge Engineering, v.62 n.1, p.156-176, July, 2007
	Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
	Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
	Daniela Florescu , Daphne Koller , Alon Y. Levy, Using Probabilistic Information in Data Integration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.216-225, August 25-29, 1997
	Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
	Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
	Arnd Christian König , Gerhard Weikum, Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.423-434, September 07-10, 1999
	Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
	Christos Faloutsos , Yossi Matias , Abraham Silberschatz, Modeling Skewed Distribution Using Multifractals and the `80-20' Law, Proceedings of the 22th International Conference on Very Large Data Bases, p.307-317, September 03-06, 1996
	CORPORATE Univ. of Wisconsin, Database research at Wisconsin, ACM SIGMOD Record, v.22 n.1, p.74-81, March 1993
	Chaitanya Mishra , Nick Koudas, Interactive query refinement, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Chaitanya Mishra , Nick Koudas, The design of a query monitoring system, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-51, April 2009