Abstract
Optimal histograms are computed for hierarchical range queries. It is shown that optimal histograms for equality queries are sub-optimal for hierarchical range queries. Polynomial time, dynamic programming algorithms are presented for computing optimal histograms that would provably minimize expected error for a given amount of space. The algorithm for the case of one-sided ranges is proved to be as efficient in running time as the V-optimal algorithm, which computes optimal histograms for equality series.
Original language | English (US) |
---|---|
Pages | 196-204 |
Number of pages | 9 |
State | Published - 2000 |
Event | PODS 2000 - 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - Dallas, TX, USA Duration: May 15 2000 → May 17 2000 |
Conference
Conference | PODS 2000 - 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems |
---|---|
City | Dallas, TX, USA |
Period | 5/15/00 → 5/17/00 |
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture