Paper Info
Title
On Linear-Spline Based Histograms
Abstract
Approximation is a very effective paradigm to speed up query processing in large databases. One popular approximation mechanism is data size reduction. There are three reduction techniques: sampling, histograms, and wavelets. Histogram techniques are supported by many commercial database systems, and have been shown very effective for approximately processing aggregation queries. In this paper, we will investigate the optimal models for building histograms based on linear spline techniques. We will firstly propose several novel models. Secondly, we will present efficient algorithms to achieve these proposed optimal models. Our experiment results showed that our new techniques can greatly improve the approximation accuracy comparing to the existing techniques.
Year
DOI
Venue
2002
10.1007/3-540-45703-8_33
WAIM
Keywords
Field
DocType
proposed optimal model,effective paradigm,optimal model,data size reduction,aggregation query,approximation accuracy,reduction technique,commercial database system,query processing,popular approximation mechanism,database system
Spline (mathematics),Data mining,Histogram,Computer science,Range query (data structures),Algorithm,Size reduction,Sampling (statistics),Data reduction,Speedup,Wavelet
Conference
ISBN
Citations 
PageRank 
3-540-44045-3
2
0.38
References 
Authors
14
2
Name
Order
Citations
PageRank
Qing Zhang156725.85
Xuemin Lin25585307.32