Login | Register

rK-Hist : an R-Tree based histogram for multi-dimensional selectivity estimation


rK-Hist : an R-Tree based histogram for multi-dimensional selectivity estimation

Lopez, John Alexander (2007) rK-Hist : an R-Tree based histogram for multi-dimensional selectivity estimation. Masters thesis, Concordia University.

Text (application/pdf)
MR34636.pdf - Accepted Version


Database query engines typically rely upon query size estimators in order to evaluate the potential cost of alternate query plans. In multi-dimensional database systems, such as those typically found in large data warehousing environments, these selectivity estimators often take the form of multi-dimensional histograms. But while single dimensional histograms have proven to be quite accurate, even in the presence of data skew, the multi-dimensional variations have generally been far less reliable. In this thesis, we present a new histogram model that is based upon an r-tree space partitioning. The localization of the r-tree boxes is in turn controlled by a Hilbert space filling curve, while a series of efficient area equalization heuristics restructures the initial boxes to provide improved bucket representation. The proposed histogram works on an existing multi-processor platform that targets the relational database model (ROLAP). Experimental results on real and synthetic data demonstrate significantly improved estimation accuracy relative to state of the art alternatives, as well as superior consistency across a variety of record distributions.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Lopez, John Alexander
Pagination:xii, 96 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Eavis, Todd
ID Code:975746
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:14
Last Modified:18 Jan 2018 17:41
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top