Density Estimations for Approximate Query Processing on SIMD Architectures

Approximate query processing (AQP) is an interesting alternative for exact query processing. It is a tool for dealing with the huge data volumes where response time is more important than perfect accuracy (this is typically the case during initial phase of data exploration). There are many technique...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-05
Main Authors: Andrzejewski, Witold, Gramacki, Artur, Gramacki, Jarosław
Format: Article
Language:English
Subjects:
Algorithms
Mathematical analysis
Parameter sensitivity
Probability density functions
Queries
Query processing
Response time
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Approximate query processing (AQP) is an interesting alternative for exact query processing. It is a tool for dealing with the huge data volumes where response time is more important than perfect accuracy (this is typically the case during initial phase of data exploration). There are many techniques for AQP, one of them is based on probability density functions (PDF). PDFs are typically calculated using nonparametric data-driven methods. One of the most popular nonparametric method is the kernel density estimator (KDE). However, a very serious drawback of using KDEs is the large number of calculations required to compute them. The shape of final density function is very sensitive to an entity called bandwidth or smoothing parameter. Calculating it's optimal value is not a trivial task and in general is very time consuming. In this paper we investigate the possibility of utilizing two SIMD architectures: SSE CPU extensions and NVIDIA's CUDA architecture to accelerate finding of the bandwidth. Our experiments show orders of magnitude improvements over a simple sequential implementation of classical algorithms used for that task.
ISSN:2331-8422