Detecção de exceções em bases de dados massivas usando GPUs
Autor: | Fernando Augusto Freitas Da Silva Da Nova Mussel |
---|---|
Přispěvatelé: | Wagner Meira Júnior, Adriano Alonso Veloso, George Luiz Medeiros Teodoro, Renato Antônio Celso Ferreira |
Jazyk: | angličtina |
Rok vydání: | 2017 |
Předmět: | |
Zdroj: | Repositório Institucional da UFMG Universidade Federal de Minas Gerais (UFMG) instacron:UFMG |
Popis: | Detecção de exceções é um importante método de mineração de dados, utilizado para encontrar registros inesperados em bases de dados. Essas anomalias comumente carregam informações úteis e podem ser utilizadas em diversas aplicações, tais como detecção de intrusões em rede, detecção de fraudes em bases de cartões de crédito e seguro, dentre outras. Existem diversos desafios associados com detecção de exceções e o principal é o custo computacional. Muita pesquisa foi feita para melhorar a complexidade temporal de tais métodos, por meio de particionamento de dados, ordenação e regras de poda. Mesmo assim, o estado-da-arte só é capaz de detectar, em tempo hábil, uma pequena quantidade das top-n exceções. Recentemente, implementações para GPU foram propostas a m de contornar o custo computacional do problema. Os resultados obtidos foram promissores, porém, no melhor do nosso conhecimento, os algoritmos para GPU propostos até o momento estão restritos a processar bases de dados carregados na memória da GPU. Consequentemente, estes métodos têm aplicabilidade limitada pois não podem ser utilizados nos casos onde a GPU seria mais útil: bases de dados de larga escala. O objetivo deste trabalho é utilizar GPUs para acelerar o processo de detecção de exceções em bases de dados de larga escala, residentes em disco. Dessa forma, desenvolvemos algoritmos e estratégias para minimizar a redução do throughput de computação causado por acessos ao disco. Este trabalho possui duas contribuições principais. Primeiro, nós desenvolvemos um conjunto de ferramentas e abstrações que facilitam a implementação algoritmos, para GPUs, de detecção de exceções em bases de dados armazenadas em disco. Entre tais abstrações temos uma nova estratégia de paralelização; algoritmos e kernels para operações essenciais à detecção de exceções; e um novo subsistema de I/O, capaz de reduzir o overhead de transferência de dados e permitir a execução concorrente de computação e I/O. Nossa segunda contribuição é um novo algoritmo, DROIDg, para a detecção de exceções, baseadas em distância, usando GPUs. Ele utiliza uma nova heurística de ordenação, a qual propusemos, que melhora a e ciência de sua regra de poda, dessa forma reduzindo enormemente a quantidade de computação necessária para realizar a detecção. Nossa análise experimental focou em determinar a aceleração que GPUs podem fornecer à detecção de exceções em bases de dados larga escala. Portanto, comparamos DROIDg contra alguns dos melhores algoritmos sequenciais out-of-core disponíveis na literatura: Orca, Diskaware e Dolphin. DROIDg alcançou speedups de 10X até 137X sob o melhor algoritmo para CPUs. Além disso, ele demonstrou escalabilidade consideravelmente maior com relação ao tamanho da base de dados e, também, do número de exceções sendo detectadas. Estes resultados demonstram que GPUs permitem realizar a detecção de exceções em escalas muito além do que, até mesmo, os algoritmos estado-da-arte para CPU são capazes. Outlier detection is an important data mining task for nding unusual data records in datasets. These anomalies often carry useful information that can be employed in a wide range of practical applications, such as network intrusion detection, fraud discovery in credit card or insurance databases, among several others. There are several challenges associated with the outlier detection problem and its computational cost is a major one. Signi cant research has been done to improve these methods' runtime complexity through the use of data partitioning, ordering and pruning rules. Though these advancements allow the outlier detection to be performed in near-linear time, they are not enough to enable processing large-scale datasets in a reasonable time. Even state-of-the-art methods are limited to processing small scale datasets and/or limited to nd just a tiny fraction of the true top-n outliers. Recently, GPU-based implementations have emerged as an alternative to address the computational bottleneck. They have shown promising results but, to the best of our knowledge, all distance-based GPU algorithms currently available are designed for in-memory detection: they require the dataset to t and be loaded into the GPU's memory. Consequently, their applicability is limited because they can not be used in scenarios where the GPU's computational power would the most useful: to process large scale datasets. The goal of this work is to use GPUs to accelerate the outlier detection process in terabyte-scale, disk-resident datasets. To achieve it, we have to develop algorithms and strategies to overcome the massive reductions in the GPU's computation throughput caused by disk accesses. We made two main contributions in this work. First, we developed set of tools and abstractions for out-of-core distance-based outlier detection in GPUs, such as an e ective parallelization strategy; algorithms and high-performance GPU kernels of essential operations for distance-based outlier detection; and an I/O subsystem that reduces data transfer overhead while allowing I/O and computation overlapping. The second main contributions is the development of a novel distancebased outlier detection algorithm for GPUs, DROIDg, capable of processing large scale and disk-resident datasets in reasonable time. It leverages a new ranking heuristic, proposed by ourselves, to improve the e ciency of its pruning rule, thereby massively reducing the amount of computation required by the detection. Our experimental analysis focused on assessing the performance bene ts of using GPUs for outlier detection in large-scale datasets. Thus, we compared DROIDg against some of the best out-of-core outlier detection algorithms available for CPUs: Orca, Diskaware and Dolphin. DROIDg achieved speedups between 10X and 137X over the best sequential algorithm. Moreover, it displayed far superior scalability with regards to the dataset size and number of outliers being detected. These results showed that GPUs enable the outlier detection to be performed at scales far beyond what even state-of-the-art CPU algorithms are capable of. |
Databáze: | OpenAIRE |
Externí odkaz: |