Abstract How to spot outliers in a large, unlabeled dataset with both numerical and categorical attributes? How to do it in a fast and scalable way? Outlier detection has many applications; it is covered therefore by an extensive literature. The distance-based detectors are the most popular ones. However, they still have two major drawbacks: (a) the intensive neighborhood search that takes hours or even days to complete in large data, and; (b) the inability to process categorical attributes. This paper tackles both problems by presenting HySortOD: a new, fast and scalable detector for numerical and categorical data. Our main focus is the analysis of datasets with many instances, and a low-to-moderate number of attributes. We studied dozens of real, benchmark datasets with up to one million instances; HySortOD outperformed nine competitors from the state of the art in runtime, being up to six orders of magnitude faster in large data, while maintaining high accuracy. Finally, we also performed an extensive experimental evaluation that confirms the ability of our method to obtain high-quality results from both real and synthetic datasets with categorical attributes.

Abstract We perform an extensive experimental evaluation of clustering-based outlier detection methods. These methods offer benefits such as efficiency, the possibility to capitalize on more mature evaluation measures, more developed subspace analysis for high-dimensional data and better explainability, and yet they have so-far been neglected in literature. To our knowledge, our work is the first effort to analytically and empirically study their advantages and disadvantages. Our main goal is to evaluate whether or not clustering-based techniques can compete in efficiency and effectiveness against the most studied state-of-the-art algorithms in the literature. We consider the quality of the results, the resilience against different types of data and variations in parameter configuration, the scalability, and the ability to filter out inappropriate parameter values automatically based on internal measures of clustering quality. It has been recently shown that several classic, simple, unsupervised methods surpass many deep learning approaches and, hence, remain at the state-of-the-art of outlier detection. We therefore study 14 of the best classic unsupervised methods, in particular 11 clustering-based methods and 3 non-clustering-based ones, using a consistent parameterization heuristic to identify the pros and cons of each approach. We consider 46 real and synthetic datasets with up to 125k points and 1.5k dimensions aiming to achieve plausibility with the broadest possible diversity of real-world use cases. Our results indicate that the clustering-based methods are on par with (if not surpass) the non-clustering-based ones, and we argue that clustering-based methods like KMeans−− should be included as baselines in future benchmarking studies, as they often offer a competitive quality at a relatively low run time, besides several other benefits.

Digital games are dynamic environments where the players interact with the games and, commonly, also with other players. The interactions generate many types of relationships, such as to be friends or to share games with other players, and to buy, play or like the games. These relationships can be seen as a social network; in this context, a Social Network of Games (SNG). During gameplay, the player produces a vast amount of data continuously, including data that represents his/her experiences, preferences, and even behavioral patterns. These data can be used to understand the players’ preferences, which is known in the literature as Player Modeling, and also to improve the attractiveness of new games. However, both tasks require analyzing a vast amount of data that cannot be done manually; it must be performed by algorithms of a research area known as Knowledge Discovery in Databases (KDD). It is possible to employ KDD techniques in the data of an SNG to model the players, as well as to identify intrinsic features of the games. In our work, we explore a real SNG using a novel KDD technique aimed at identifying common features among popular games, which may represent why the games are popular. To this end, it is necessary to analyze games developed by non-influencer makers, because influencers may receive biased attention that is not necessarily motivated by the quality of their games. Therefore, we first focus on detecting the game influencers to filter their games out; empirical experiments show that a novel approach we developed detects influencers with high accuracy in an automatic manner , even when using data from distinct nationalities for training and testing. Then, we perform a detailed analysis of the features of the games, searching for combinations of objects that occur in the popular games developed by non-influencer makers, where each object can be either a game item or a non-player character, so to support game designers in the elaboration process of new games. This case study introduces a new pattern of design for Platform Games. Additionally, we present an extensive analysis of object combinations that commonly occur in popular games. All experiments were performed on real-world players and games from the worldwide well-known platform of video games Super Mario Maker (Nintendo, Kyoto, Japan).

How could we have an outlier detector that works even with nondimensional data, and ranks together both singleton microclusters (‘one-off’ outliers) and nonsingleton microclusters by their anomaly scores? How to obtain scores that are prin-cipled in one scalable and ‘hands-off’ manner? Microclusters of outliers indicate coalition or repetition in fraud activities, etc.; their identification is thus highly desirable. This paper presents Mccatch: a new algorithm that detects microclusters by leveraging our proposed ‘Oracle’ plot (1NN Distance versus Group 1NN Distance). We study 31 real and synthetic datasets with up to 1M data elements to show that McCatchi's the only method that answers both of the questions above; and, it outperforms 11 other methods, especially when the data has non-singleton microclusters or is nondimensional. We also showcase McCATCH'S ability to detect meaningful microclusters in graphs, fingerprints, logs of network connections, text data, and satellite imagery. For example, it found a 30-elements microcluster of confirmed ‘Denial of Service’ attacks in the network logs, taking only ~3 minutes for 222K data elements on a stock desktop.

How can we detect outliers, both scattered and clustered, and also explicitly assign them to respective micro-clusters, without knowing apriori how many micro-clusters exist? How can we perform both tasks in-house, i.e., without any post-hoc processing, so that both detection and assignment can benefit simultaneously from each other? Presenting outliers in separate micro-clusters is informative to analysts in many real-world applications. However, a naïve solution based on post-hoc clustering of the outliers detected by any existing method suffers from two main drawbacks: (a) appropriate hyperparameter values are commonly unknown for clustering, and most algorithms struggle with clusters of varying shapes and densities; (b) detection and assignment cannot benefit from one another. In this paper, we propose D.MCA to Detect outliers with explicit Micro-Cluster Assignment. Our method performs both detection and assignment iteratively, and in-house, by using a novel strategy that prunes entire micro-clusters out of the training set to improve the performance of the detection. It also benefits from a novel strategy that avoids clustered outliers to mask each other, which is a well-known problem in the literature. Also, D.MCA is designed to be robust to a critical hyperparameter by employing a hyperensemble “warm up” phase. Experiments performed on 16 real-world and synthetic datasets demonstrate that D.MCA outperforms 8 state-of-the-art competitors, especially on the explicit outlier micro-cluster assignment task.

Detecting grooming behavior in online conversations has become a growing problem due to the large number of messaging platforms that children and young people use nowadays. The biggest drawback is the lack of tools focused on the automatic prevention of this risk. This paper proposes seven Behavioral Features (BFs) to be used for early grooming detection. A detailed study is conducted to understand the background that allows these features to contribute to tasks of early classification. Besides, we introduce the Behavioral Feature - Profile Specific Representation (BF-PSR) framework as an extension of the well-known Profile Specific Representation (PSR) framework to properly employ the proposed behavioral features. Experimental results reveal that our proposal outperforms all the concurrent methods and obtains state-of-the-art performance in the area of early grooming detection. Specifically, the new BF-PSR framework achieves a gain of more than 40% in effectiveness over five competitors when only 10% of the SGD conversations content is available, thus it shows a substantial advantage to allow the early detection of grooming; besides, it maintains a similar gain in effectiveness as more data arrives. Furthermore, to the best of our knowledge, this is the first work to employ behavioral features for the early detection of grooming. On the other hand, we have assembled two new datasets called PJZ and PJZC to mitigate the lack of data in the grooming detection area. Both sets are publicly available for download aimed at fostering further researches. Additional experiments reveal that our BF-PSR framework outperforms all state-of-the-art methods when processing these new datasets.

Outlier detection is the task responsible for finding novel or rare phenomena that provide valuable insights in many areas of the industry. The neighborhood-based algorithms are largely used to tackle this problem due to the intuitive interpretation and wide applicability in different domains. Their major drawback is the intensive neighborhood search that takes hours or even days to complete in large data, thus being impractical in many real-world scenarios. This paper proposes HySortOD -- a novel algorithm that uses an efficient hypercube-ordering-and-searching strategy for fast outlier detection. Its main focus is the analysis of data with many instances and a low-to-moderate number of dimensions. We performed comprehensive experiments using real data with up to ~500k instances and ~120 dimensions, where our new algorithm outperformed 7 state-of-the-art competitors in runtime, being up to 4 orders of magnitude faster in large data. Specifically, 12 well-known benchmark datasets were deeply investigated and one case study in the crucial task of breast cancer detection was also performed to demonstrate that our approach can be successfully used as an out-of-the-box solution for real-world, non-benchmark problems. Based on our experiments, we also identified default parameter values that allow us to be parameter-free and yet report high-quality results.

Given a set of millions or even billions of complex objects for descriptive data mining, how to effectively reduce the data dimensionality? It must be performed in an unsupervised way. Unsupervised dimensionality reduction is essential for analytical tasks like clustering and outlier detection because it helps to overcome the drawbacks of the "curse of high dimensionality". The state-of-the-art approach is to preserve the data variance by means of well-known techniques, such as PCA, KPCA, SVD, and other techniques based on those that have been mentioned, such as PUFS. But, is it always the best strategy to follow? This paper presents an exploratory study performed to compare two distinct approaches: (a) the standard variance preservation, and; (b) one alternative, Fractal-based solution that is rarely used, for which we propose one fast and scalable Spark-based algorithm using a novel feature partitioning approach that allows it to tackle data of high dimensionality. Both strategies were evaluated by inserting into 11 real-world datasets, with up to 123.5 million elements and 518 attributes, at most 500 additional attributes formed by correlations of many kinds, such as linear, quadratic, logarithmic and exponential, and verifying their abilities to remove this redundancy. The results indicate that, at least for large datasets of dimensionality with up to ∼1,000 attributes, our proposed Fractal-based algorithm is the best option. It accurately and efficiently removed the redundant attributes in nearly all cases, as opposed to the standard variance-preservation strategy that presented considerably worse results, even when applying the KPCA approach that is made for non-linear correlations.

In Relational Algebra, the operator Division (÷) is an intuitive tool used to write queries with the concept of "for all", and thus, it is constantly required in real applications. However, as we demonstrate here, the division does not support many of the needs common to modern applications, particularly those that involve complex data analysis, such as processing images, audio, genetic data, large graphs, fingerprints, and many other "non-traditional" data types. The main issue is the existence of intrinsic comparisons of attribute values in the operator, which, by definition, are always performed by identity (=), despite the fact that complex data must be compared by similarity. Recent works focus on supporting similarity comparison in relational operators, but no one treats the division. This paper presents the new Similarity-aware Division (÷ˆ) operator. Our novel operator is naturally well suited to answer queries with an idea of "candidate elements and exigencies" to be performed on complex data from modern applications. For example, it is potentially useful to support agriculture, genetic analyses, digital library search, prospective client identification, and even to help controlling the quality of manufactured products in industry. We validate our proposals by studying the first two of these applications.

What if a successful company starts to receive a torrent of low-valued (one or two stars) recommendations in its mobile apps from multiple users within a short (say one month) period of time? Is it legitimate evidence that the apps have lost in quality, or an intentional plan (via lockstep behavior) to steal market share through defamation? In the case of a systematic attack to one's reputation, it might not be possible to manually discern between legitimate and fraudulent interaction within the huge universe of possibilities of user-product recommendation. Previous works have focused on this issue, but none of them took into account the context, modeling, and scale that we consider in this paper. Here, we propose the novel method Online-Recommendation Fraud ExcLuder (ORFEL) to detect defamation and/or illegitimate promotion of online products by using vertex-centric asynchronous parallel processing of bipartite (users-products) graphs. With an innovative algorithm, our results demonstrate both efficacy and efficiency -- over 95% of potential attacks were detected, and ORFEL was at least two orders of magnitude faster than the state-of-the-art. Over a novel methodology, our main contributions are: (1) a new algorithmic solution; (2) one scalable approach; and (3) a novel context and modeling of the problem, which now addresses both defamation and illegitimate promotion. Our work deals with relevant issues of the Web 2.0, potentially augmenting the credibility of online recommendation to prevent losses to both customers and vendors.

Given a data stream with many attributes and high frequency of events, how to cluster similar events? Can it be done in real time? For example, how to cluster decades of frequent measurements of tens of climatic attributes to aid real time alert systems in forecasting extreme climatic events, such as floods and hurricanes? The task of clustering data with many attributes is known as subspace clustering. Today, there exists a need for algorithms of this type well-suited to process multidimensional data streams, for which real time processing is highly desirable. This paper proposes the new algorithm Haliteds – a fast, scalable and highly accurate subspace clustering algorithm for multidimensional data streams. It improves upon an existing technique that was originally designed to process static (not streams) data. Our main contributions are: (1) Analysis of Data Streams: the new algorithm takes advantage of the knowledge obtained from clustering past data to easy clustering data in the present. This fact allows our Haliteds to be considerably faster than its base algorithm, yet obtaining the same accuracy of results; (2) Real Time Processing: as opposed to the state-of-the-art, Haliteds is fast and scalable, making it feasible to analyze streams with many attributes and high frequency of events in real time; (3) Experiments: we ran experiments using synthetic data and a real multidimensional stream with almost one century of climatic data. Our Haliteds was up to 217 times faster than 5 representative works, i.e., its base algorithm plus 4 others from the state-of-the-art, always presenting highly accurate results.

This paper proposes an approach to efficientlyexecute conjunctive queries on big complex data together withtheir related conventional data. The basic idea is to horizontallyfragment the database according to criteria frequently usedin query predicates. The collection of fragments is indexed toefficiently find the fragment(s) whose contents satisfy some querypredicate(s). The contents of each fragment are then indexed aswell, to support efficient filtering of the fragment data according to other query predicate s) conjunctively connected to the former. This strategy has been applied to a collection of more than 106 million images together with their related conventional data. Experimental results show considerable performance gain of the proposed approach for queries with conventional and similaritybasedpredicates, compared to the use of a unique metric index for the entire database contents.

This paper proposes Halite, a novel, fast, and scalable clustering method that looks for clusters in subspaces of multidimensional data. Existing methods are typically superlinear in space or execution time. Halite's strengths are that it is fast and scalable, while still giving highly accurate results. Specifically the main contributions of Halite are: 1) Scalability: it is linear or quasi linear in time and space regarding the data size and dimensionality, and the dimensionality of the clusters' subspaces; 2) Usability: it is deterministic, robust to noise, doesn't take the number of clusters as an input parameter, and detects clusters in subspaces generated by original axes or by their linear combinations, including space rotation; 3) Effectiveness: it is accurate, providing results with equal or better quality compared to top related works; and 4) Generality: it includes a soft clustering approach. Experiments on synthetic data ranging from five to 30 axes and up to 1 \rm million points were performed. Halite was in average at least 12 times faster than seven representative works, and always presented highly accurate results. On real data, Halite was at least 11 times faster than others, increasing their accuracy in up to 35 percent. Finally, we report experiments in a real scenario where soft clustering is desirable.

Given a very large moderate-to-high dimensionality dataset, how could one cluster its points? For datasets that don't fit even on a single disk, parallelism is a first class option. In this paper we explore MapReduce for clustering this kind of data. The main questions are (a) how to minimize the I/O cost, taking into account the already existing data partition (e.g., on disks), and (b) how to minimize the network cost among processing nodes. Either of them may be a bottleneck. Thus, we propose the Best of both Worlds -- BoW method, that automatically spots the bottleneck and chooses a good strategy. Our main contributions are: (1) We propose BoW and carefully derive its cost functions, which dynamically choose the best strategy; (2) We show that BoW has numerous desirable features: it can work with most serial clustering methods as a plugged-in clustering subroutine, it balances the cost for disk accesses and network accesses, achieving a very good tradeoff between the two, it uses no user-defined parameters (thanks to our reasonable defaults), it matches the clustering quality of the serial algorithm, and it has near-linear scale-up; and finally, (3) We report experiments on real and synthetic data with billions of points, using up to 1,024 cores in parallel. To the best of our knowledge, our Yahoo! web is the largest real dataset ever reported in the database subspace clustering literature. Spanning 0.2 TB of multi-dimensional data, it took only 8 minutes to be clustered, using 128 cores.

We propose the Multi-resolution Correlation Cluster detection (MrCC), a novel, scalable method to detect correlation clusters able to analyze dimensional data in the range of around 5 to 30 axes. Existing methods typically exhibit super-linear behavior in terms of space or execution time. MrCC employs a novel data structure based on multi-resolution and gains over previous approaches in: (a) it finds clusters that stand out in the data in a statistical sense; (b) it is linear on running time and memory usage regarding number of data points and dimensionality of subspaces where clusters exist; (c) it is linear in memory usage and quasi-linear in running time regarding space dimensionality; and (d) it is accurate, deterministic, robust to noise, does not require stating the number of clusters as input parameter, does not perform distance calculation and is able to detect clusters in subspaces generated by original axes or linear combinations of original axes, including space rotation. We performed experiments on synthetic data ranging from 5 to 30 axes and from 12 k to 250 k points, and MrCC outperformed in time five of the recent and related work, being in average 10 times faster than the competitors that also presented high accuracy results for every tested dataset. Regarding real data, MrCC found clusters at least 9 times faster than the competitors, increasing their accuracy in up to 34 percent.

Given a large collection of images, very few of which have labels, how can we guess the labels of the remaining majority, and how can we spot those images that need brand new labels, different from the existing ones? Current automatic labeling techniques usually scale super linearly with the data size, and/or they fail when only a tiny amount of labeled data is provided. In this paper, we propose QMAS (Querying, Mining And Summarization of Multi-modal Databases), a fast solution to the following problems: (i) low-labor labeling (L3) – given a collection of images, very few of which are labeled with keywords, find the most suitable labels for the remaining ones, and (ii) mining and attention routing – in the same setting, find clusters, the top-NO outlier images, and the top-NR representative images. We report experiments on real satellite images, two large sets (1.5GB and 2.25GB) of proprietary images and a smaller set (17MB) of public images. We show that QMAS scales linearly with the data size, being up to 40 times faster than top competitors (GCap), obtaining better or equal accuracy. In contrast to other methods, QMAS does low-labor labeling (L3), that is, it works even with tiny initial label sets. It also solves both presented problems and spots tiles that potentially require new labels.