Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Multi-dimensional histograms with tight bounds for the error |
| Organization Unit | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| ISBN | 0-7695-2577-6 |
| Page Range | 105 - 112 |
| Event Title | IDEAS 2006 |
| Event Type | conference |
| Event Location | Delhi, India |
| Event Start Date | December 11 - 2006 |
| Event End Date | December 14 - 2006 |
| Publisher | IEEE |
| Abstract Text | Histograms are being used as non-parametric selectivity estimators for one-dimensional data. For highdimensional data it is common to either compute onedimensional histograms for each attribute or to compute a multi-dimensional equi-width histogram for a set of attributes. This either yields small low-quality or large highquality histograms.In this paper we introduce HIRED (High-dimensional histograms with dimensionality REDuction): small highquality histograms for multi-dimensional data. HIRED histograms are adaptive, and they are based on the shape error and directional splits. The shape error permits a precise control of the estimation error of the histogram and, together with directional splits, yields a memory complexity that does not depend on the number of uniform attributes in the dataset. We provide extensive experimental results with synthetic and real world datasets. The experiments confirm that our method is as precise as state-of-the-art techniques and uses orders of magnitude less memory. |
| Digital Object Identifier | 10.1109/IDEAS.2006.31 |
| Other Identification Number | merlin-id:6160 |
| Export |
BibTeX
EP3 XML (ZORA)
|