Abstract:
We present new algorithms on commodity graphics processors to perform fast computation of several common database operations. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA’s GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.
 

Abstract:
We present a fast sorting algorithm using graphics processors (GPUs) that adapts well to database and data mining applications. Our algorithm uses texture mapping and blending functionalities of GPUs to implement an efficient bitonic sorting network. We take into account the communication bandwidth overhead to the video memory on the GPUs and reduce the memory bandwidth requirements. We also present strategies to exploit the tile-based computational model of GPUs. Our new algorithm has a memoryefficient data access pattern and we describe an efficient instruction dispatch mechanism to improve the overall sorting performance. We have used our sorting algorithm to accelerate join-based queries and stream mining algorithms. Our results indicate up to an order of magnitude improvement over prior CPU-based and GPU-based sorting algorithms. 

Abstract:

The Graphics Processing Unit (GPU) has extended its applications from its original graphic rendering to more general scientific computation. Through massive parallelization, state-of-the-art GPUs can deliver 200 billion floating-point operations per second (0.2 TFLOPS) on a single consumer-priced graphics card. This paper describes our attempt in leveraging GPUs for efficient HMM model training. We show that using GPUs for a specific example of Gaussian clustering, as required in fMPE, or feature-domain Minimum Phone Error discriminative training, can be highly desirable. The clustering of huge number of Gaussians is very time consuming due to the enormous model size in current LVCSR systems. Comparing an NVidia Geforce 8800 Ultra GPU against an Intel Pentium 4 implementation, we find that our brute-force GPU implementation is 14 times faster overall than a CPU implementation that uses approximate speed-up heuristics. GPU accelerated fMPE reduces the WER 6% relatively, compared to the maximum likelihood trained baseline on two conversational-speech recognition tasks.

The Local Outlier Factor (LOF) is a very powerful anomaly detection method available in machine learning and classification.
The algorithm defines the notion of local outlier in which the degree to which an object is outlying is dependent
on the density of its local neighborhood, and each object can be assigned an LOF which represents the likelihood of that
object being an outlier. Although this concept of a local outlier is a useful one, the computation of LOF values for every
data object requires a large number of k-nearest neighbor queries – this overhead can limit the use of LOF due to the
computational overhead involved.

Due to the growing popularity of Graphics Processing Units (GPU) in general-purpose computing domains, and equipped
with a high-level programming language designed specifically for general-purpose applications (e.g., CUDA), we look
to apply this parallel computing approach to accelerate LOF. In this paper we explore how to utilize a CUDA-based GPU
implementation of the k-nearest neighbor algorithm to accelerate LOF classification. We achieve more than a 100X
speedup over a multi-threaded dual-core CPU implementation. We also consider the impact of input data set size, the
neighborhood size (i.e., the value of k) and the feature space dimension, and report on their impact on execution time. 

We describe a method for implementing the evaluation and training of decision trees and forests entirely on a GPU, and show how
this method can be used in the context of object recognition. Our strategy for evaluation involves mapping the data structure describing
a decision forest to a 2D texture array. We navigate through the forest for each point of the input data in parallel using an efficient, nonbranching
pixel shader. For training, we compute the responses of the training data to a set of candidate features, and scatter the responses
into a suitable histogram using a vertex shader. The histograms thus computed can be used in conjunction with a broad range of tree learning
algorithms.

We demonstrate results for object recognition which are identical to those obtained on a CPU, obtained in about 1% of the time.
To our knowledge, this is the first time a method has been proposed which is capable of evaluating or training decision trees on a GPU. Our
method leverages the full parallelism of the GPU. Although we use features common to computer vision to demonstrate
object recognition, our framework can accommodate other kinds of features for more general utility within computer science.