English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation

König, A. C., & Weikum, G. (1999). Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation. In M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, & M. L. Brodie (Eds.), Proceedings of 25th International Conference on Very Large Data Bases (VLDB 99) (pp. 423-434). San Francisco, USA: Morgan Kaufmann.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-36F1-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-36F2-4
Genre: Conference Paper

Files

show Files
hide Files
:
KonigW99.pdf (Any fulltext), 367KB
 
File Permalink:
-
Name:
KonigW99.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
König, Arnd Christian, Author
Weikum, Gerhard1, Author           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: -
 Abstract: This paper aims to improve the accuracy of query result-size estimations in query optimizers by leveraging the dynamic feedback obtained from observations on the executed query workload. To this end, an approximate "synopsis" of data-value distributions is devised that combines histograms with parametric curve fitting, leading to a specific class of linear splines. The approach reconciles the benefits of histograms, simplicity and versatility, with those of parametric techniques especially the adaptivity to statistically biased and dynamically evolving query workloads. The paper presents efficient algorithms for constructing the linear-spline synopsis for data-value distributions from a moving window of the most recent observations on (the most critical) query executions. The approach is worked out in full detail for capturing frequency as well as density distributions of data values, and it is shown how result size estimations are inferred for exact-match and range queries as well as projections and grouping. To a large extent, the developed methods can be generalized to multi-dimensional distributions, thus bearing the ability to capture correlations among attributes as well. Experimental studies underline the accuracy of the developed estimation methods, outperforming the best known classes of histograms.

Details

show
hide
Language(s): eng - English
 Dates: 2007-02-131999
 Publication Status: Issued
 Pages: -
 Publishing info: San Francisco, USA : Morgan Kaufmann
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 520343
Other: Local-ID: C1256DBF005F876D-F57646812730C1BCC125714C0055CC8B-KonigW99
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Edinburgh, Scotland, UK
Start-/End Date: 2002-10-07 - 2002-10-10

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of 25th International Conference on Very Large Data Bases (VLDB 99)
Source Genre: Proceedings
 Creator(s):
P. Atkinson, Malcolm, Editor
Orlowska, Maria E., Editor
Valduriez, Patrick, Editor
Zdonik, Stanley B., Editor
Brodie, Michael L., Editor
Affiliations:
-
Publ. Info: San Francisco, USA : Morgan Kaufmann
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 423 - 434 Identifier: ISBN: 1-55860-615-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -