NDLI: Wavelet synopses with error guarantees

Please wait, while we are loading the content...

Archiving scientific data

Rate-based query optimization for streaming information sources

Best-effort cache synchronization with source cooperation

Accelerating XPath location steps

Implementing database operations using SIMD instructions

StatiX: making XML count

Executing SQL over encrypted data in the database-service-provider model

A scalable hash ripple join algorithm

Approximate XML joins

Efficient k-NN search on vertically decomposed data

Statistical synopses for graph-structured XML databases

Clustering by pattern similarity in large data sets

Dynamic multidimensional histograms

Dwarf: shrinking the PetaCube

Coordinating backup/recovery and data consistency between database and file systems

A compact B-tree

Automating physical database design in a parallel database

Mid-tier caching: the TimesTen approach

DBCache: database caching for web application servers

ACDN: a content delivery network for applications

CubeExplorer: online exploration of data cubes

Data streams: fresh current or stagnant backwater? (panel)

Going public: open-source databases and database research

Implementing XQuery

Querying and mining data streams: you only get one look a tutorial

Tutorial: application servers and associated technologies

Database tuning: principles, experiments, and troubleshooting techniques (part I)

Software as a service: ASP and ASP aggregation

Efficient integration and aggregation of historical information

Continuously adaptive continuous queries over streams

Efficient evaluation of queries in a mediator for WebSources

APEX: an adaptive path index for XML data

Fractal prefetching $B^{+}-Trees:$ optimizing both cache and disk performance

QURSED: querying and reporting semistructured data

Workflow management with service quality guarantees

Exploiting statistics on query expressions for optimization

Efficient algorithms for minimizing tree pattern queries

Time-parameterized queries in spatio-temporal databases

Continually evaluating similarity-based pattern queries on a streaming time series

Mining long sequential patterns in a noisy environment

Selectivity estimation for spatio-temporal queries to moving objects

Wavelet synopses with error guarantees

An ebXML infrastructure implementation through UDDI registries and RosettaNet PIPs

Efficient execution of joins in a star schema

The SDSS skyserver: public access to the sloan digital sky server data

Web caching for database applications with Oracle Web Cache

Learning table access cardinalities with LEO

COMMIX: towards effective web information extraction, integration and query answering

DBXplorer: enabling keyword search over relational databases

Database tuning: principles, experiments, and troubleshooting techniques (part II)

An adaptive peer-to-peer network for distributed caching of OLAP results

Processing complex aggregate queries over data streams

Proxy-based acceleration of dynamically generated content on the world wide web: an approach and implementation

Covering indexes for branching path queries

Skew handling techniques in sort-merge join

Storing and querying ordered XML using a relational database system

Mining database structure; or, how to build a data quality browser

Partial results for online query processing

Holistic twig joins: optimal XML pattern matching

Minimal probing: supporting expensive predicates for top-k queries

General match: a subsequence matching method in time-series databases based on generalized windows

A Monte Carlo algorithm for fast projective clustering

Hierarchical subspace sampling: a unified framework for high dimensional data reduction, selectivity estimation and nearest neighbor search

Compressing SQL workloads

Garlic: a new flavor of federated query processing for DB2

Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data

TPC-DS, taking decision support benchmarking to the next level

Middle-tier database caching for e-business

Rainbow: mapping-driven XQuery processing system

COUGAR: the network is the database

GEA: a toolkit for gene expression analysis

The XXL search engine: ranked retrieval of XML data using indexes and ontologies

Distributing queries over low-power wireless sensor networks

HD-Eye: visual clustering of high dimensional data

ToXgene: a template-based data generator for XML

Gigascope: high performance network monitoring with an SQL interface

XBase: making your gigabyte disk queriable

Visual COKO: a debugger for query optimizer development

RoadRunner: automatic data extraction from data-intensive web sites

XmdvTool: visual interactive data exploration and trend discovery of high-dimensional data sets

XCache: a semantic caching system for XML queries

XL: a platform for web services

Wavelet synopses with error guarantees

Content Provider	ACM Digital Library
Author	Garofalakis, Minos Gibbons, Phillip B.
Abstract	Recent work has demonstrated the effectiveness of the wavelet decomposition in reducing large amounts of data to compact sets of wavelet coefficients (termed "wavelet synopses") that can be used to provide fast and reasonably accurate approximate answers to queries. A major criticism of such techniques is that unlike, for example, random sampling, conventional wavelet synopses do not provide informative error guarantees on the accuracy of individual approximate answers. In fact, as this paper demonstrates, errors can vary widely (without bound) and unpredictably, even for identical queries on nearly-identical values in distinct parts of the data. This lack of error guarantees severely limits the practicality of traditional wavelets as an approximate query-processing tool, because users have no idea of the quality of any particular approximate answer. In this paper, we introduce Probabilistic Wavelet Synopses, the first wavelet-based data reduction technique with guarantees on the accuracy of individual approximate answers. Whereas earlier approaches rely on deterministic thresholding for selecting a set of "good" wavelet coefficients, our technique is based on a novel, probabilistic thresholding scheme that assigns each coefficient a probability of being retained based on its importance to the reconstruction of individual data values, and then flips coins to select the synopsis. We show how our scheme avoids the above pitfalls of deterministic thresholding, providing highly-accurate answers for individual data values in a data vector. We propose several novel optimization algorithms for tuning our probabilistic thresholding scheme to minimize desired error metrics. Experimental results on real-world and synthetic data sets evaluate these algorithms, and demonstrate the effectiveness of our probabilistic wavelet synopses in providing fast, highly-accurate answers with error guarantees.
Starting Page	476
Ending Page	487
Page Count	12
File Format	PDF
ISBN	1581134975
DOI	10.1145/564691.564746
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-06-03
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in