The democratization of electronic devices over the years encouraged individuals and industries to produce data at a cheap price. As a consequence of this phenomenon, the data production increased globally at a fast pace. With this ever-growing data production, industries demanded better tools to find patterns in the large volume of data available and improve their decisionmaking processes. Some particular events might not fit in any existing pattern and yet bring important business insights. They are usually rare events that do not conform with the majority of the data, often classified as anomalies, exceptions or outliers. They can represent failures, frauds, scamming, invasions or abnormal conditions in systems. Detecting this type of event as soon as possible is crucial for real-world applications such as in finance, healthcare, social networks and quality control. Several algorithms have been introduced in the literature providing outstanding results in terms of effectivity, but, in practice, the existing alternatives are still very much expensive in terms of runtime. The most efficient approaches assume that an outlier can be identified by searching for similar instances, also known as neighbors due to their close proximity in the feature space. Data structures are used to store the instances and perform successive neighborhood search operations as a way to take advantage of neighborhood properties and detect outliers. Such type of operation has been strongly researched in the community of similarity search over the years. It is well-known by this community that successive neighborhood searches can be replaced by a single similarity join operation, but this observation does not seem obvious in the outlier detection literature because virtually all algorithms develop their own strategies to search for similar instances. Similarity join is a fundamental operation in database systems; given two datasets and a similarity threshold, the goal is to find all pairs of similar instances. When only one dataset is given, this operation is named similarity self-join; it returns a set of similar pairs for each instance. In this context, since outliers are rare events and diverge from the majority, the instances with few similar pairs are potential outliers. Many join-based algorithms aim to improve the efficiency of the operation in a diverse range of applications. In this work, we investigate how this overlap of concepts can improve the runtime and scalability of outlier detection algorithms. We propose two novel outlier detection algorithms that use join-based techniques - ODSSJ and HySortOD. Our experimental results suggests that our solutions are 3 orders of magnitude faster than existing state-of-the-art algorithms.

A democratização dos dispositivos eletrônicos ao longo dos anos incentivou indivíduos e indústrias a produzirem dados a um baixo custo. Como consequência, a produção de dados aumentou globalmente em ritmo acelerado. Com essa produção de dados cada vez maior, as indústrias exigiram melhores ferramentas para encontrar padrões e melhorar seus processos de tomada de decisão. Alguns eventos em particular podem não encaixar em nenhum padrão e ainda assim trazerem informações importantes. São usualmente eventos raros que não correspondem à maioria dos dados, também conhecidos como anomalias, exceções ou outliers. Eles podem representar falhas, fraudes, invasões ou condições anormais em sistemas. Detectar esses eventos o quanto antes é crucial em aplicações reais, como finanças, redes sociais e controle de qualidade. Vários algoritmos fornecem excelentes resultados em termos de qualidade, porém na prática, se mostram ineficientes para lidar com dados volumosos. Abordagens mais eficientes pressupõem que uma exceção pode ser identificada buscando por instâncias similares, também conhecidas como vizinhas devido à proximidade espacial entre as instâncias. As estruturas de dados armazenam dados e realizam sucessivas operações de busca por vizinhança para obter informações sobre a densidade da vizinhança, a qual é usada na detecção de exceções. Essa operação tem sido muito pesquisada na comunidade de busca por similaridade ao longo dos anos. Nessa comunidade, é sabido que essas sucessivas operações podem ser substituídas por uma junção por similaridade, mas essa observação não parece óbvia na literatura de detecção de casos de exceção porque praticamente todos algoritmos criam suas próprias estratégias de busca por similaridade. A junção por similaridade é uma operação que, dado dois conjuntos de dados e um limite de similaridade, o objetivo é encontrar todos os pares de instâncias similares. Porém, quando apenas um conjunto de dados é fornecido, essa operação é denominada auto-junção por similaridade. Os algoritmos para essa operação visam melhorar a eficiência em uma ampla gama de aplicações. Como casos de exceção são eventos raros e divergentes da maioria, instâncias com poucos pares podem ser uma exceção. Neste trabalho, propomos investigar como essa sobreposição de conceitos pode ser benéfica para melhorar o desempenho e a escalabilidade de algoritmos de detecção de exceção. Propomos dois novos algoritmos baseados em técnicas de junção por similaridade - ODSSJ e HySortOD. Os resultados experimentais sugerem que as soluções são 3 ordens de magnitude mais rápida que os algoritmos estado da arte existentes.