Efficient two-dimensional Haar+ synopsis construction for the maximum absolute error measure

Several wavelet synopsis construction algorithms were previously proposed for optimal Haar + synopses. Recently, we proposed the OptExtHP-EB algorithm to find an optimal one-dimensional Haar + synopsis. By utilizing the novel properties of optimal synopses, OptExtHP-EB represents the set of optimal...

Full description

Saved in:
Bibliographic Details
Published in:The VLDB journal 2019-10, Vol.28 (5), p.675-701
Main Authors: Kim, Jinhyun, Min, Jun-Ki, Shim, Kyuseok
Format: Article
Language:English
Subjects:
Algorithms
Coefficients
Computer Science
Database Management
Error analysis
Nodes
Regular Paper
Wavelet analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Several wavelet synopsis construction algorithms were previously proposed for optimal Haar + synopses. Recently, we proposed the OptExtHP-EB algorithm to find an optimal one-dimensional Haar + synopsis. By utilizing the novel properties of optimal synopses, OptExtHP-EB represents the set of optimal synopses in a node of a Haar + tree by a set of extended synopses. While it is much faster than the previous Haar + synopsis construction algorithms, it can handle only one-dimensional data. In this paper, we propose the OptExtHP-EB2D algorithm for two-dimensional Haar + synopses by extending OptExtHP-EB. While a one-dimensional Haar + tree has only two child nodes and three coefficients in a node, a two-dimensional Haar + tree is much more complex in that it has four child nodes and seven coefficients per node. Thus, for each possible subset of the coefficients selected in a node, we develop the efficient methods to compute a set of optimal synopses denoted by extended synopses. Our experiments confirm the effectiveness of our proposed OptExtHP-EB2D algorithm.
ISSN:1066-8888
0949-877X
DOI:10.1007/s00778-019-00551-2