Towards terabyte-scale outlier detection using GPUs - Fernando Augusto Freitas Da Silva Da Nova Mussel (2020)
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.