Treffer: Optimal workload-based weighted wavelet synopses

Title:
Optimal workload-based weighted wavelet synopses
Authors:
MATIAS, Yossi, URIELI, Daniel
Source:
Database theoryTheoretical computer science. 371(3):227-246
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 23 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Organisation des mémoires. Traitement des données, Memory organisation. Data processing, Systèmes d'information. Bases de données, Information systems. Data bases, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Charge travail, Workload, Carga trabajo, Erreur absolue, Absolute error, Error absoluto, Erreur relative, Relative error, Error relativo, Estimation erreur, Error estimation, Estimación error, Informatique théorique, Computer theory, Informática teórica, Ondelette, Wavelets, Requête, Query, Pregunta documental, Résultat expérimental, Experimental result, Resultado experimental, Temps linéaire, Linear time, Tiempo lineal, Théorie approximation, Approximation theory, Ensemble données massives, Massive data set, Ondelette pondérée, Weighted wavelet, Produit intérieur pondéré, Weighted inner product, Massive data sets, Wavelet synopses, Weighted wavelets, Workload-based
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18568767
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18568767
Database:
PASCAL Archive

Weitere Informationen

In recent years wavelets were shown to be effective data synopses. We are concerned with the problem of finding efficiently wavelet synopses for massive data sets, in situations where information about query workload is available. We present linear time, I/O optimal algorithms for building optimal workload-based wavelet synopses for point queries. The synopses are based on a novel construction of weighted inner products and use weighted wavelets that are adapted to those products. The synopses are optimal in the sense that the subset of retained coefficients is the best possible for the bases in use with respect to either the mean-squared absolute or relative errors. For the latter, this is the first optimal wavelet synopsis even for the regular, non-workload-based case. Experimental results demonstrate the advantage obtained by the new optimal wavelet synopses.