Real-world datasets commonly arise from mixtures of multiple, potentially overlapping subdistributions. Traditional anomaly detection methods often use rigid assumptions or global thresholds and, as a result, struggle to identify anomalies within complex multimodal data. We propose ADM-Anomalies Detection through Local Maxima and Mutual Nearest Neighbors-an unsupervised approach that systematically identifies dense, mode-like structures without imposing a single global model. Specifically, ADM constructs a mutual nearest neighbor (MNN) graph and takes its transitive closure to reveal groups of high-density points, which converge to the true modes under mild assumptions. A “double-knee” procedure then refines these groups: (i) it separates large, high-density modes from small, fringe-like clusters, and (ii) within each major mode, it pinpoints local maxima to accommodate internal multimodality. Finally, ADM assigns an anomaly score to every point by calculating its distance to the closest local maxima, thereby identifying both globally isolated anomalies and subtle boundary anomalies. Extensive evaluations on diverse real-world datasets show that ADM consistently outperforms or matches leading baselines, all while requiring only a single hyperparameter k.

Process mining aims to extract and analyze insights from event logs, yet algorithm metric results vary widely depending on structural event log characteristics. Existing work often evaluates algorithms on a fixed set of real-world event logs but lacks a systematic analysis of how event log characteristics impact algorithms individually. Moreover, since event logs are generated from processes, where characteristics co-occur, we focus on associational rather than causal effects to assess how strong the overlapping individual characteristic affects evaluation metrics without assuming isolated causal effects, a factor often neglected by prior work. We introduce SHAining, the first approach to quantify the marginal contribution of varying event log characteristics to process mining algorithms’ metrics. Using process discovery as a downstream task, we analyze over 22,000 event logs covering a wide span of characteristics to uncover which affect algorithms across metrics (e.g., fitness, precision, complexity) the most. Furthermore, we offer novel insights about how the value of event log characteristics correlates with their contributed impact, assessing the algorithm’s robustness.

Business processes from many domains like manufacturing, healthcare, or business administration suffer from different amounts of uncertainty concerning the execution of individual activities and their order of occurrence. As long as a process is not entirely serial, i.e., there are no forks or decisions to be made along the process execution, we are - in the absence of exhaustive domain knowledge - confronted with the question whether and in what order activities should be executed or left out for a given case and a desired outcome. As the occurrence or non-occurrence of events has substantial implications regarding process key performance indicators like throughput times or scrap rate, there is ample need for assessing and modeling that process-inherent uncertainty. We propose a novel way of handling the uncertainty by leveraging the probabilistic mechanisms of Bayesian Networks to model processes from the structural and temporal information given in event log data and offer a comprehensive evaluation of uncertainty by modelling cases in their entirety. In a thorough analysis of well-established benchmark datasets, we show that our Process-aware Bayesian Network is capable of answering process queries concerned with any unknown process sequence regarding activities and/or attributes enhancing the explainability of processes. Our method can infer execution probabilities of activities at different stages and can query probabilities of certain process outcomes. The key benefit of the Process-aware Query System over existing approaches is the ability to deliver probabilistic, case-diagnostic information about the execution of activities via Bayesian inference.

Abstract Financial portfolio managers typically face multi-period optimization tasks such as short-selling or investing at least a particular portion of the portfolio in a specific industry sector. A common approach to tackle these problems is to use constrained Markov decision process (CMDP) methods, which may suffer from sample inefficiency, hyperparameter tuning, and lack of guarantees for constraint violations. In this paper, we propose Action Space Decomposition Based Optimization (ADBO) for optimizing a more straightforward surrogate task that allows actions to be mapped back to the original task. We examine our method on two real-world data portfolio construction tasks. The results show that our new approach consistently outperforms state-of-the-art benchmark approaches for general CMDPs.

Active learning has the power to significantly reduce the amount of labeled data needed to build strong classifiers. Existing active pseudo-labeling methods show high potential in integrating pseudo-labels within the active learning loop but heavily depend on the prediction accuracy of the model. In this work, we propose VERIPS, an algorithm that significantly outperforms existing pseudo-labeling techniques for active learning. At its core, VERIPS uses a pseudo-label verification mechanism that consists of a second network only trained on data approved by the oracle and helps to discard questionable pseudo-labels. In particular, the verifier model eliminates all pseudo-labels for which it disagrees with the actual task model. VERIPS overcomes the problems of poorly performing initial models, e.g., due to imbalanced or too small initial pools, where previous methods select too many incorrect pseudo-labels and recovering takes long or is not possible. Moreover, VERIPS is particularly insensitive to parameter choices that existing approaches suffer from. Our code is available at https://github.com/lmu-dbs/VERIPS.

Spectral clustering is one of the most advantageous clustering approaches. However, standard Spectral Clustering is sensitive to noisy input data and has a high runtime complexity. Tackling one of these problems often exacerbates the other. As real-world datasets are often large and compromised by noise, we need to improve both robustness and runtime at once. Thus, we propose Spectral Clustering - Accelerated and Robust (SCAR), an accelerated, robustified spectral clustering method. In an iterative approach, we achieve robustness by separating the data into two latent components: cleansed and noisy data. We accelerate the eigendecomposition - the most time-consuming step - based on the Nyström method. We compare SCAR to related recent state-of-the-art algorithms in extensive experiments. SCAR surpasses its competitors in terms of speed and clustering quality on highly noisy data.

Malicious software (malware) poses an increasing threat to the security of communication systems as the number of interconnected mobile devices increases exponentially. While some existing malware detection and classification approaches successfully leverage network traffic data, they treat network flows between pairs of endpoints independently and thus fail to leverage rich communication patterns present in the complete network. Our approach first extracts flow graphs and subsequently classifies them using a novel edge feature-based graph neural network model. We present three variants of our base model, which support malware detection and classification in supervised and unsupervised settings. We evaluate our approach on flow graphs that we extract from a recently published dataset for mobile malware detection that addresses several issues with previously available datasets. Experiments on four different prediction tasks consistently demonstrate the advantages of our approach and show that our graph neural network model can boost detection performance by a significant margin.

Data Mining and Process Mining – is one just a variant of the other, or do worlds separate the two areas from each other? The notions sound so similar but the contents sometimes look differently, so respective researchers may get confused in their mutual perception, be it authors or reviewers. The talk recalls commonalities like model-based supervised and unsupervised learning approaches, and it also sheds light to peculiarities in process data and process mining tasks as seen from a data mining perspective. When considering trace data from event log files as time series, as sequences, or as activity sets, quite different data mining techniques apply and may be extended and improved. A particular example is rare pattern mining, which fills a gap between frequent patterns and outlier detection. The task aims at identifying patterns that occur with low frequency but above single outliers. Structural deficiences may cause malfunctions or other undesired behavior which get discarded as outliers in event logs, since they are observed infrequently only. Rare pattern mining may identify these situations, and recent approaches include clustering or ordering non-conformant traces.The talk concludes with some remarks on how to sell process mining papers to the data mining community, and vice versa, in order to improve mutual acceptance, and to increase synergies in the fields.

Outlier detection is one of the most important tasks to keep your processes in control. Unawareness of critical anomalies can lead to exhausting expenses, hence, it is highly beneficial to treat process failures as soon as possible. However, anomalies are difficult to detect due to their rarity though they occur too often to neglect the necessity of its detection. Even if the detection problem is solved, the treatment of singular anomalies and the adjustment of the process based on each abnormal trace is tedious and costly regarding time and money. To increase the efficiency of later anomaly treatment, we propose a novel strategy to detect collective anomalies. However, this is not equivalent to anomaly clustering as a post-processing step. TOAD orders process instances by similarity and detects abnormal accumulations of deviating cases. These collections are abnormal due to their aggregated behavior. Assuming that similar deviations are caused by the same reason, the treatment of such an anomaly is more cost-efficient than the handling of deviating singletons. Applying TOAD to an event log yields a ranking of significant, temporally abnormal trace collections, that provide a baseline for further analysis.

Density-based clustering algorithms are commonly adopted when arbitrarily shaped clusters exist. Usually, they do not need to know the number of clusters in prior, which is a big advantage. Conventional density-based approaches such as DBSCAN, utilize two parameters to define density. Recently, novel density-based clustering algorithms are proposed to reduce the problem complexity to the use of a single parameter k by utilizing the concepts of k Nearest Neighbor (kNN) and Reverse k Nearest Neighbor (RkNN) to define density. However, those kNN-based approaches are either ineffective or inefficient. In this paper, we present a new clustering algorithm KNNAC, which only requires computing the densities for a chosen subset of points due to the use of active core detection. We empirically show that, compared to other nearest neighbor based clustering approaches (e.g., RECORD, IS-DBSCAN, etc.), KNNAC can provide competitive performance while taking a fraction of the runtime.

As data processing techniques get more and more sophisticated every day, many of us researchers often get lost in the details and subtleties of the algorithms we are developing and far too easily seem to forget to look also at the very first steps of every algorithm: the input of the data. Since there are plenty of library functions for this task, we indeed do not have to think about this part of the pipeline anymore. But maybe we should. All data is stored and loaded into a program in some order. In this vision paper we study how ignoring this order can (1) lead to performance issues and (2) make research results unreproducible. We furthermore examine desirable properties of a data ordering and why current approaches are often not suited to tackle the two mentioned problems.

Abstract OPTICS is a popular tool to analyze the clustering structure of a dataset visually. The created two-dimensional plots indicate very dense areas and cluster candidates in the data as troughs. Each horizontal slice represents an outcome of a density-based clustering specified by the height as the density threshold for clusters. However, in very dynamic and rapidly changing applications, a complex and finely detailed visualization slows down the knowledge discovery. Instead, a framework that provides fast but coarse insights is required to point out structures in the data quickly. The user can then control the direction he wants to put emphasize on for refinement. We develop AMTICS as a novel and efficient divide-and-conquer approach to pre-cluster data in distributed instances and align the results in a hierarchy afterward. An interactive online phase ensures a low complexity while giving the user full control over the partial cluster instances. The offline phase reveals the current data clustering structure with low complexity and at any time.

As the ordering of data, particularly of graphs, can influence the result of diverse Data Mining tasks performed on it heavily, we introduce the Circle Index, the first internal quality measurement for orderings of graphs. It is based on a circular arrangement of nodes, but takes in contrast to similar arrangements from the field of, e.g., visual analytics, the edge lengths in this arrangement into account. The minimization of the Circle Index leads to an arrangement which not only offers a simple way to cluster the data using a constrained MinCut in only linear time, but is also visually convincing. We developed the clustering algorithm CirClu, which implements this minimization and MinCut, and compared it with several established clustering algorithms achieving very good results. Simultaneously we compared the Circle Index with several internal quality measures for clusterings. We observed a strong coherence between the Circle Index and the matching of achieved clusterings to the respective ground truths in diverse real world datasets.

LUCK allows to use any distance-based clustering algorithm to find linear correlated data. For that a novel distance function is introduced, which takes the distribution of the kNN of points into account and corresponds to the probability of two points being part of the same linear correlation. In this work in progress we tested the distance measure with DBSCAN and k-Means comparing it to the well-known linear correlation clustering algorithms ORCLUS, 4C, COPAC, LMCLUS, and CASH, receiving good results for difficult synthetic data sets containing crossing or non-continuous correlations.

In publications where a clustering method is described, the chosen hyperparameters are in many cases to our current observation empirically determined. In this work in progress we discuss and propose one approach on how hyperparameters can be systematically explored and their effects regarding the data set analyzed. We further introduce in the context of hyperparameter analysis a modified definition of the resilience term, which refers here to a subset of data points which persists to be in the same cluster over different hyperparameter settings. In order to analyze relations among different hyperparameters we further introduce the concept of dynamic intersection computing.

Periodicities are omnipresent: In nature in the cycles of predator and prey populations, reoccurring patterns regarding our power consumption over the days, or the presence of flu diseases over the year. With regards to the importance of periodicities we ask: Is there a way to detect periodic correlated clusters which are hidden in event series? We propose as a work in progress a method for detecting sinusoidal periodic correlated clusters on event series which relies on parameter space transformation. Our contributions are: Providing the first non-linear correlation clustering algorithm for detecting periodic correlated clusters. Further our method provides an explicit model giving domain experts information on parameters such as amplitude, frequency, phase-shift and vertical-shift of the detected clusters. Beyond that we approach the issue of determining an adequate frequency and phase-shift of the detected correlations given a frequency and phase-shift boundary.

In this work we address the problem of argument search. The purpose of argument search is the distillation of pro and contra arguments for requested topics from large text corpora. In previous works, the usual approach is to use a standard search engine to extract text parts which are relevant to the given topic and subsequently use an argument recognition algorithm to select arguments from them. The main challenge in the argument recognition task, which is also known as argument mining, is that often sentences containing arguments are structurally similar to purely informative sentences without any stance about the topic. In fact, they only differ semantically. Most approaches use topic or search term information only for the first search step and therefore assume that arguments can be classified independently of a topic. We argue that topic information is crucial for argument mining, since the topic defines the semantic context of an argument. Precisely, we propose different models for the classification of arguments, which take information about a topic of an argument into account. Moreover, to enrich the context of a topic and to let models understand the context of the potential argument better, we integrate information from different external sources such as Knowledge Graphs or pre-trained NLP models. Our evaluation shows that considering topic information, especially in connection with external information, provides a significant performance boost for the argument mining task.

In this work, we investigate the opposite question of frequent itemset mining: what patterns occurred less than a given minimum support in a transactional database? This question, known as infrequent itemset mining, is important in fields such as medical science, security, finance and scientific research. Frequent patterns represent expected or obvious information while infrequent patterns are those unexpected behaviors and are more interesting in some applications. For example, health-care needs to identify sporadic but lethal crossover effects. Security agents have to uncover infrequent associative fraud indicators. Existing infrequent itemset mining approaches are time-consuming. Furthermore, extracting all infrequent patterns might suffer from the redundant problem. In this paper, we study the two factors that affect the performance of itemset mining tasks. The concept of closed itemset is applied for infrequent patterns to reduce the number of returned patterns. An efficient closed infrequent itemset mining approach is proposed which combines both bottom-up and top-down traversing strategies. Extensive experimental results show that a simple algorithm based on our framework, without using advanced data structure or pruning techniques, can still be significantly more efficient when compared with other approaches.

Many algorithms have been developed for detecting clusters of various kinds over the past decades. However, just few attempts have been made to provide an interactive setting for the clustering algorithms. In this paper, we present PARADISO, an interactive Mean Shift method. It enables the user to get back to any arbitrary iteration point of the run observing the evolution of the clusters after each iteration and to set different bandwidth parameters. The user gets a clustering result with this method which emerged through multiple bandwidths while the user can see the full chain of effects of the chosen bandwidths over all iterations. Further, our method provides so-called Points-Shifted-Distance plots (PSD plots) for the Mean Shift algorithm which aim to facilitate the choice of a different bandwidth for the user. Beyond the mentioned features, PARADISO provides a visualization method which lets the user see the different bandwidth choices made in form of pathways.

Correlation clustering detects complex and intricate relationships in high-dimensional data by identifying groups of data points, each characterized by differents correlation among a (sub)set of features. Current correlation clustering methods generally limit themselves to linear correlations only. In this paper, we introduce a method for detecting global non-linear correlated clusters focusing on quadratic relations. We introduce a novel Hough transform for the detection of hyperparaboloids and apply it to the detection of hyperparaboloid correlated clusters in arbitrary high-dimensional data spaces. Non-linear correlation clustering like our method can reveal valuable insights which are not covered by current linear versions. Our empirical results on synthetic and real world data reveal that the proposed method is robust against noise, jitter and irregular densities.

This paper address the problem of temporal pattern mining from multiple data streams containing temporal events. Temporal events are considered as real world events aligned with comprehensive starting and ending timing information rather than simple integer timestamps. Predefined relations, such as "before" and "after", describe the heterogeneous relationships hidden in temporal data with limited diversity. In this work, the relationships among events are learned dynamically from the temporal information. Each event is treated as an object with a label and numerical attributes. An online-offline model is used as the primary structure for analyzing the evolving multiple streams. Different distance functions on temporal events and sequences can be applied depending on the application scenario. A prefix tree is introduced for a fast incremental pattern update.

This tutorial aims at providing a unified and comprehensive overview of the state-of-the-art approaches to distance-based multimedia indexing.

Almost all activities observed in nowadays applications are correlated with a timing sequence. Users are mainly looking for interesting sequences out of such data. Sequential pattern mining algorithms aim at nding frequent sequences. Usually, the mined activities have timing durations that represent time intervals between their starting and ending points. Most sequential pattern mining approaches dealt with such activities as a single point event and thus lost many valuable information in the collected patterns. We present the PIVOTMiner, an ecient interval-based sequential pattern mining algorithm using a geometric representation of intervals. The interestingness level is not necessarily positively correlated with the frequency of the patterns. In many applications, users are seeking for rare patterns that considerably deviate from the majority. Simply delivering the bottom-k patterns does not guarantee their high outlierness (or deviation) from the frequent ones. We propose additionally the PIVOTRanker, the rst scalable algorithm for ranking rare interval-based sequential patterns based on their outlierness. Our experimental results on both synthetic and real-world datasets show that PIVOTMiner spends considerably less time than two state-of-the-art competitors, and that PIVOTRanker delivers a meaningful and useful ranking of rare patterns.

The rapid increase in generation and dissemination of online video data has recently raised the demand on efficient and effective query processing techniques in large video databases. In this paper, we first introduce a novel compact video representation model to achieve high effectiveness, and then propose to alleviate computational time complexity of the well-known Earth Mover’s Distance by introducing a filter approximation analyzing earth flows locally and restricting the number of flows globally, ensuring completeness .M oreover, extensive experimental evaluation performed on high dimensional real world datasets points out high efficiency and effectiveness of the proposals, significantly reducing the number of Earth Mover’s Distance computations and outperforming the state of the art by up to two orders of magnitude with respect to selectivity and query processing time.

The analysis of the temporal evolution of dynamic networks is a key challenge for understanding complex processes hidden in graph structured data. Graph evolution rules capture such processes on the level of small subgraphs by describing frequently occurring structural changes within a network. Existing rule discovery methods make restrictive assumptions on the change processes present in networks. We propose EvoMine, a frequent graph evolution rule mining method that, for the first time, supports networks with edge insertions and deletions as well as node and edge relabelings. EvoMine defines embedding-based and event-based support as two novel measures to assess the frequency of rules. These measures are based on novel mappings from dynamic networks to databases of union graphs that retain all evolution information relevant for rule mining. Using these mappings the rule mining problem can be solved by frequent subgraph mining. We evaluate our approach and two baseline algorithms on several real datasets. To the best of our knowledge, this is the first empirical comparison of rule mining algorithmsfor dynamic networks.

An overwhelming volume of geo-social data is generated daily. This data could be analyzed and used to predict or expose valuable vivid patterns that would be imperative to society. However, prediction on sparse check-in data in Location-Based Social Networks (LBSN) is still challenging. In this paper, we propose a novel technique that utilizes matrix factorization to predict the top-k future locations for check-in data. Specifically, we introduce a new approach to capture the unique mobility behaviors of users by crafting Geo-Recency based Gaussian mixture models. Then, we determine users or friends with similar check-in preferences by computing the Cross Likelihood Ratio (CLR) similarity from each user's Geo-Recency Gaussian model. These CLR scores are leveraged during matrix factorization to learn and predict future locations. In addition, we present a new technique that employs these Geo-Recency Gaussian mixture models to effectively quantify social influence. We conduct numerous experiments on real datasets and compare our empirical results to that of state-of-the-art works. Our experiments reveal that our future location prediction technique performs better than that of state-of-the-art works.

With the continuous increase of heterogeneous multimedia data, the question of how to access big multimedia data efficiently has become of crucial importance. In order to provide fast access to complex multimedia data, we propose to approximate content-based features of multimedia objects by means of generative models. The proposed gradient-based signatures epitomize a high quality content-based approximation of multimedia objects and facilitate efficient indexing and query processing at large scale.

With the continuous rise of multimedia, the question of how to access large-scale multimedia databases efficiently has become of crucial importance. Given a multimedia database comprising millions of multimedia objects, how to approximate the content-based properties of the corresponding feature representations in order to carry out similarity search efficiently and with high accuracy? In this paper, we propose the concept of gradient-based signatures in order to aggregate content-based features of multimedia objects by means of generative models. We provide theoretical insights into our approach including closed-form expressions for the computation of gradient-based signatures with respect to Gaussian mixture models and additionally investigate different binarization methods for gradient-based signatures in order to query databases comprising millions of multimedia objects with high accuracy in less than one second.

The recent rapid growth of scientific data necessitates efficient similarity search techniques for which convenient object representation models are of vital importance. Feature signatures denoting highly flexible object feature representations have increasingly gained attention for which corresponding efficiency improvement techniques are developed. In this paper, we focus on efficient query processing with the well-known Earth Mover's Distance (EMD) on databases of feature signatures, and propose efficient approximation techniques successfully applicable to high-dimensional feature signatures via dimensionality reduction, guaranteeing both completeness and no false-dismissal within a filter-and-refine architecture. Rigorous experiments on real world data indicate a considerable reduction in the number of EMD computations and high efficiency of the proposed techniques which significantly reduce the query processing time.

The Earth Mover's Distance, proposed in computer vision as a distance-based similarity model reflecting the human perceptual similarity, has been widely utilized in numerous domains for similarity search applicable on both feature histograms and signatures. While efficiency improvement methods towards the Earth Mover's Distance were frequently investigated on feature histograms, not much work is known to study this similarity model on feature signatures denoting object-specific feature representations. Given a very large multimedia database of features signatures, how can k-nearest-neighbor queries be processed efficiently by using the Earth Mover's Distance? In this paper, we propose an efficient filter approximation technique to lower bound the Earth Mover's Distance on feature signatures by restricting the number of earth flows locally. Extensive experiments on real world data indicate the high efficiency of the proposal, attaining order-of-magnitude query processing time cost reduction for high dimensional feature signatures.

Fast growing data sets with a very high number of attributes become a common situation in social, industry and scientific areas. A meaningful analysis of these data sets requires sophisticated data mining techniques as projected clustering that are able to deal with such complex data. In this work, we investigate solutions for extending the state-of-theart projected clustering algorithm P3C for large data sets in highdimensional spaces. We show that the original model of the P3C algorithm is not suitable to deal with huge data sets. Therefore, we propose the necessary changes of the underlying clustering model and then present an efficient MapReduce-based implementation our novel P3C + -MR algorithm. The effectiveness of the proposed changes on large data sets and the efficiency of the P3C + -MR algorithm are comprehensively evaluated on synthetic and real-world data sets. Additionally, we propose the P3C + -MR-Light algorithm, a simplified version of P3C + -MR that shows extraordinary good results in terms of runtime and result quality on large data sets. In the end, we compare our solutions to existing approaches.

Join processing on large-scale vector data is an important problem in many applications, as vectors are a common representation for various data types. Especially, several data analysis tasks like near duplicate detection, density-based clustering or data cleaning are based on similarity self-joins, which are a special type of join. For huge data sets, MapReduce proved to be a suitable, error-tolerant framework for parallel join algorithms. Recent approaches exploit the vector-space properties for low-dimensional vector data for an efficient join computation. However, so far no parallel similarity self-join approaches aiming at high-dimensional vector data were proposed. In this work we propose the novel similarity self-join algorithm PHiDJ (Parallel High-Dimensional Join) for the MapReduce framework. PHiDJ is well suited for medium to high-dimensional data and exploits multiple filter techniques for reducing communication and computational costs. We provide a solution for efficient join computation for skewed distributed data. Our experimental evaluation on medium- to high-dimensional data shows that our approach outperforms existing techniques.

The widespread adoption of ubiquitous devices does not only facilitate the connection of billions of people, but has also fuelled a culture of sharing rich, high resolution locations through check-ins. Despite the profusion of GPS and WiFi driven location prediction techniques, the sparse and random nature of check-in data generation have ushered diverse problems, which have prompted the prediction of future check-ins to be very challenging. In this paper, we propose a novel enhanced location predictor for check-in data that is crafted using Poisson distribution, Wavelets and Conditional Random Fields (CRF). Specifically, we show that check-in generation is governed by the Poisson distribution. In addition, among others, we utilize wavelets to rigorously analyze social influence and learn elusive underlying patterns, as well as human mobility behaviors embedded in check-in data. We utilize this knowledge to institute CRF features, which capture latent trends that govern users' mobility. These CRF features are employed to build a robust predictive model that predicts future locations with enhanced accuracy. We demonstrate the effectiveness of our predictive model on two real datasets. Furthermore, our experiments reveal that our approach outperforms a state-of-the-art work with an accuracy of 36%.

Since data is often multi-faceted in its very nature, it might not adequately be summarized by just a single clustering. To better capture the data's complexity, methods aiming at the detection of multiple, alternative clusterings have been proposed. Independent of this research area, semi-supervised clustering techniques have shown to substantially improve clustering results for single-view clustering by integrating prior knowledge. In this paper, we join both research areas and present a solution for integrating prior knowledge in the process of detecting multiple clusterings.

Networks entail vulnerable and sensitive information that pose serious privacy threats. In this paper, we introduce, k-core attack, a new attack model which stems from the k-core decomposition principle. K-core attack undermines the privacy of some state-of-the-art techniques. We propose a novel structural anonymization technique called (k, δ)-Core Anonymity, which harnesses the k-core attack and structurally anonymizes small and large networks. In addition, although real-world social networks are massive in nature, most existing works focus on the anonymization of networks with less than one hundred thousand nodes. (k, δ)-Core Anonymity is tailored for massive networks. To the best of our knowledge, this is the first technique that provides empirical studies on structural network anonymization for massive networks. Using three real and two synthetic datasets, we demonstrate the effectiveness of our technique on small and large networks with up to 1.7 million nodes and 17.8 million edges. Our experiments reveal that our approach outperforms a state-of-the-art work in several aspects.

Clustering of high dimensional streaming data is an emerging field of research. A real life data stream imposes many challenges on the clustering task, as an endless amount of data arrives constantly. A lot of research has been done in the full space stream clustering. To handle the varying speeds of the data stream, "anytime" algorithms are proposed but so far only in full space stream clustering. However, data streams from many application domains contain abundance of dimensions; the clusters often exist only in specific subspaces (subset of dimensions) and do not show up in the full feature space. In this paper, the first algorithm that considers both the high dimensionality and the varying speeds of streaming data, is proposed. The algorithm, called SubClusTree, can flexibly adapt to the different stream speeds and makes the best use of available time to provide a high quality subspace clustering. The experimental results prove the effectiveness of our anytime subspace concept.

Using continuous models in scientific databases has received an increased attention in the last years. It allows for a more efficient and accurate querying, as well as predictions of the outputs even where no measurements were performed. The most common queries are on how the output looks like for a given input setting. In this paper we study inverse model-based queries on continuous models, where one specifies a desired output and searches for the appropriate input setting, which falls into the reverse engineering category. We propose two possible approaches. The first one is an extension of the inverse regression paradigm. But simply switching the roles of input and output variables poses new challenges, which we overcome by using partial least squares. The second approach formulates the inverse prediction queries as linear optimization problems. We show that even though these two approaches seem completely different, they are closely related, and that the latter is more general. It facilitates the formulation of a wide range of queries, with specifications of fixed values and ranges in both input and output space, enabling the intuitive exploration of the experimental data and understanding the underlying process.

Clustering graph data has gained much attention in recent years, as data represented as graphs is ubiquitous in today's applications. For many applications, besides the mere graph data also further information about the vertices of a graph is available, which can be represented as attribute vectors. Recently, combined clustering approaches were introduced, which consider graph information and attribute vectors simultaneously for clustering. The visualization of clustering results can help users to get a better understanding of the results. In this paper, we introduce the GC-Viz system, which is implemented as a plugin for the Gephi platform. GC-Viz allows the user to test the combined clustering methods GAMer and DB-CSC on their data and to visualize and explore the clustering results. Furthermore, GC-Viz enables the user to visually compare the results of different clustering algorithms on the same dataset.

Clustering graphs annotated with feature vectors has recently gained much attention. The goal is to detect groups of vertices that are densely connected in the graph as well as similar with respect to their feature values. While early approaches treated all dimensions of the feature space as equally important, more advanced techniques consider the varying relevance of dimensions for different groups. In this work, we propose a novel clustering method for graphs with feature vectors based on the principle of spectral clustering. Following the idea of subspace clustering, our method detects for each cluster an individual set of relevant features. Since spectral clustering is based on the eigendecomposition of the affinity matrix, which strongly depends on the choice of features, our method simultaneously learns the grouping of vertices and the affinity matrix. To tackle the fundamental challenge of comparing the clustering structures for different feature subsets, we define an objective function that is unbiased regarding the number of relevant features. We develop the algorithm SSCG and we show its application for multiple real-world datasets.

With an ever-growing availability of data streams the interest in and need for efficient techniques dealing with such data increases. A major challenge in this context is the accurate online prediction of continuous values in the presence of concept drift. In this paper, we introduce a new adaptive model tree (AMT), designed to incrementally learn from the data stream, adapt to the changes, and to perform real time accurate predictions at anytime. To deal with sub models lying in different subspaces, we propose a new model clustering algorithm able to identify subspace models, and use it for computing splits in the input space. Compared to state of the art, our AMT allows for oblique splits, delivering more compact and accurate models.

We propose a simple yet effective approach to content-based image retrieval: the signature matching distance. While recent approaches to content-based image retrieval utilize the bag-of-visual-words model, where image descriptors are matched through a common visual vocabulary, signature-based approaches use a distance between signatures, i.e. between image-specific bags of locally aggregated descriptors, in order to quantify image dissimilarity. In this paper, we focus on the signature-based approach to content-based image retrieval and propose a novel distance function, the signature matching distance. This distance matches coincident visual properties of images based on their signatures. In particular, by investigating different descriptor matching strategies and their suitability to match signatures, we show that our approach is able to outperform other signature-based approaches to content-based image retrieval. Moreover, in combination with a simple color and texture-based image descriptor, our approach is able to compete with the majority of bag-of-visual-words approaches.

Detecting dense subgraphs in a large graph is an important graph mining problem and various approaches have been proposed for its solution. While most existing methods only consider unlabeled and one-dimensional graph data, many real-world applications provide far richer information. Thus, in our work, we consider graphs that contain different types of edges -- represented as different layers/dimensions of a graph -- as well as edge labels that further characterize the relations between two vertices. We argue that exploiting this additional information supports the detection of more interesting clusters. In general, we aim at detecting clusters of vertices that are densely connected by edges with similar labels in subsets of the graph layers.

Cluster tracing algorithms are used to mine temporal evolutions of clusters. Generally, clusters represent groups of objects with similar values. In a temporal context like tracing, similar values correspond to similar behavior in one snapshot in time. Recently, tracing based on object-value-similarity was introduced. In this new paradigm, the decision whether two clusters are considered similar is based on the similarity of the clusters' object values. Existing approaches of this paradigm, however, have a severe limitation. The mapping of clusters between snapshots in time is performed pairwise, i.e. global connections between a temporal snapshot's clusters are ignored; thus, impacts of other clusters that may affect the mapping are not considered and incorrect cluster tracings may be obtained.

Data sources representing social networks with additional attribute information about the nodes are widely available in today's applications. Recently, combined clustering methods were introduced that consider graph information and attribute information simultaneously to detect meaningful clusters in such networks. In many cases, such attributed graphs also evolve over time. Therefore, there is a need for clustering methods that are able to trace clusters over different time steps and analyze their evolution over time. In this paper, we extend our combined clustering method DB-CSC to the analysis of evolving combined clusters.

Testing algorithms and systems involves trying different sets of parameter values on different domains or data sets. Even for a moderate number of parameters and domains the number of possible experiments can get very large due to the combinatorial explosion. Evaluating the outcome of these experiments requires comparing the results, which is often done by writing a script or inspecting the result files manually. For a new algorithm or version, the work has to be done over again. With hundreds, thousands, or even more possible experiments, both the preparation and the evaluation can become complex and tedious. In this demonstrator we present a software tool, called ET, for evaluating the parameters of an algorithm or system, either automatically or controlled by the user. It allows to launch large numbers of experiments in just a few clicks, visually explore the results and analyze the performance of the algorithm.

Traditional clustering algorithms identify just a single clustering of the data. Today's complex data, however, allow multiple interpretations leading to several valid groupings hidden in different views of the database. Each of these multiple clustering solutions is valuable and interesting as different perspectives on the same data and several meaningful groupings for each object are given. Especially for high dimensional data, where each object is described by multiple attributes, alternative clusters in different attribute subsets are of major interest. In this tutorial, we describe several real world application scenarios for multiple clustering solutions. We abstract from these scenarios and provide the general challenges in this emerging research area. We describe state-of-the-art paradigms, we highlight specific techniques, and we give an overview of this topic by providing a taxonomy of the existing clustering methods. By focusing on open challenges, we try to attract young researchers for participating in this emerging research field.

Mining temporal multivariate data by clustering is an important research topic. In today's complex data, interesting patterns are often neither bound to the whole dimensional nor temporal extent of the data domain. This challenge is met by temporal subspace clustering methods. Their effectiveness, however, is impeded by aspects unavoidable in real world data: Misalignments between time series, for example caused by out-of-sync sensors, and measurement errors. Under these conditions, existing temporal subspace clustering approaches miss the patterns contained in the data. In this paper, we propose a novel clustering method that mines temporal subspace clusters reflected by sets of objects and relevant intervals. We enable flexible handling of misaligned time series by adaptively shifting time series in the time domain, and we achieve robustness to measurement errors by allowing certain fractions of deviating values in each relevant point in time. We show the effectiveness of our method in experiments on real and synthetic data.

Mining dense subgraphs such as cliques or quasi-cliques is an important graph mining problem and closely related to the notion of graph clustering. In various applications, graphs are enriched by additional information. For example, we can observe graphs representing different types of relations between the vertices. These multiple edge types can also be viewed as different "layers" of the same graph, which is denoted as a "multi-layer graph" in this work. Additionally, each edge might be annotated by a label characterizing the given relation in more detail. By exploiting all these different kinds of information, the detection of more interesting clusters in the graph can be supported.

Detecting multiple clustering solutions is an emerging research field. While data is often multi-faceted in its very nature, traditional clustering methods are restricted to find just a single grouping. To overcome this limitation, methods aiming at the detection of alternative and multiple clustering solutions have been proposed. In this work, we present a Bayesian framework to tackle the problem of multi-view clustering. We provide multiple generalizations of the data by using multiple mixture models. Each mixture describes a specific view on the data by using a mixture of Beta distributions in subspace projections. Since a mixture summarizes the clusters located in similar subspace projections, each view highlights specific aspects of the data. In addition, our model handles overlapping views, where the mixture components compete against each other in the data generation process. For efficiently learning the distributions, we propose the algorithm MVGen that exploits the ICM principle and uses Bayesian model selection to trade-off the cluster model's complexity against its goodness of fit. With experiments on various real-world data sets, we demonstrate the high potential of MVGen to detect multiple, overlapping clustering views in subspace projections of the data.

The necessity to analyze subspace projections of complex data is a well-known fact in the clustering community. While the full space may be obfuscated by overlapping patterns and irrelevant dimensions, only certain subspaces are able to reveal the clustering structure. Subspace clustering discards irrelevant dimensions and allows objects to belong to multiple, overlapping clusters due to individual subspace projections for each set of objects. As we will demonstrate, the observations, which originate the need to consider subspace projections for traditional clustering, also apply for the task of correlation analysis.

Analysis of temporal climate data is an active research area. Advanced data mining methods designed especially for these temporal data support the domain expert’s pursuit to understand phenomena as the climate change, which is crucial for a sustainable world. Important solutions for mining temporal data are cluster tracing approaches, which are used to mine temporal evolutions of clusters. Generally, clusters represent groups of objects with similar values. In a temporal context like tracing, similar values correspond to similar behavior in one snapshot in time. Each cluster can be interpreted as a behavior type and cluster tracing corresponds to tracking similar behaviors over time. Existing tracing approaches are for datasets satisfying two specific conditions: The clusters appear in all attributes, i.e., fullspace clusters , and the data objects have unique identifiers. These identifiers are used for tracking clusters by measuring the number of objects two clusters have in common, i.e. clusters are traced based on similar object sets . These conditions, however, are strict: First, in complex data, clusters are often hidden in individual subsets of the dimensions . Second, mapping clusters based on similar objects sets does not reflect the idea of tracing similar behavior types over time, because similar behavior can even be represented by clusters having no objects in common. A tracing method based on similar object values is needed. In this paper, we introduce a novel approach that traces subspace clusters based on object value similarity . Neither subspace tracing nor tracing by object value similarity has been done before.

Knowledge discovery in databases requires not only development of novel mining techniques but also fair and comparable quality assessment based on objective evaluation measures. Especially in young research areas where no common measures are available, researchers are unable to provide a fair evaluation. Typically, publications glorify the high quality of one approach only justified by an arbitrary evaluation measure. However, such conclusions can only be drawn if the evaluation measures themselves are fully understood. In this paper, we provide the basis for systematic evaluation in the emerging research area of subspace clustering. We formalize general quality criteria for subspace clustering measures not yet addressed in the literature. We compare the existing external evaluation methods based on these criteria and pinpoint limitations. We propose a novel external evaluation measure which meets the requirements in form of quality properties. In thorough experiments we empirically show characteristic properties of evaluation measures. Overall, we provide a set of evaluation measures that fulfill the general quality criteria as recommendation for future evaluations. All measures and datasets are provided on our website and are integrated in our evaluation framework.

The Signature Quadratic Form Distance on feature signatures represents a flexible distance-based similarity model for effective content-based multimedia retrieval. Although metric indexing approaches are able to speed up query processing by two orders of magnitude, their applicability to large-scale multimedia databases containing billions of images is still a challenging issue. In this paper, we propose the utilization of GPUs for efficient query processing with the Signature Quadratic Form Distance. We show how to process multiple distance computations in parallel and demonstrate efficient query processing by comparing many-core GPU with multi-core CPU implementations.

For knowledge discovery in high dimensional databases, subspace clustering detects clusters in arbitrary subspace projections. Scalability is a crucial issue, as the number of possible projections is exponential in the number of dimensions. We propose a scalable density-based subspace clustering method that steers mining to few selected subspace clusters. Our novel steering technique reduces subspace processing by identifying and clustering promising subspaces and their combinations directly. Thereby, it narrows down the search space while maintaining accuracy. Thorough experiments on real and synthetic databases show that steering is efficient and scalable, with high quality results. For future work, our steering paradigm for density-based subspace clustering opens research potential for speeding up other subspace clustering approaches as well.

Fast similarity search in high dimensional feature spaces is crucial in today's applications. Since the performance of traditional index structures degrades with increasing dimensionality, concepts were developed to cope with this curse of dimensionality. Most of the existing concepts exploit global correlations between dimensions to reduce the dimensionality of the feature space. In high dimensional data, however, correlations are often locally constrained to a subset of the data and every object can participate in several of these correlations. Accordingly, discarding the same set of dimensions for each object based on global correlations and ignoring the different correlations of single objects leads to significant loss of information. These aspects are relevant due to the direct correspondence between the degree of information preserved and the achievable query performance.

Outlier mining is an important data analysis task to distinguish exceptional outliers from regular objects. For outlier mining in the full data space, there are well established methods which are successful in measuring the degree of deviation for outlier ranking. However, in recent applications traditional outlier mining approaches miss outliers as they are hidden in subspace projections. Especially, outlier ranking approaches measuring deviation on all available attributes miss outliers deviating from their local neighborhood only in subsets of the attributes. In this work, we propose a novel outlier ranking based on the objects deviation in a statistically selected set of relevant subspace projections. This ensures to find objects deviating in multiple relevant subspaces, while it excludes irrelevant projections showing no clear contrast between outliers and the residual objects. Thus, we tackle the general challenges of detecting outliers hidden in subspaces of the data. We provide a selection of subspaces with high contrast and propose a novel ranking based on an adaptive degree of deviation in arbitrary subspaces. In thorough experiments on real and synthetic data we show that our approach outperforms competing outlier ranking approaches by detecting outliers in arbitrary subspace projections.

In today's applications, data analysis tasks are hindered by many attributes per object as well as by faulty data with missing values. Subspace clustering tackles the challenge of many attributes by cluster detection in any subspace projection of the data. However, it poses novel challenges for handling missing values of objects, which are part of multiple subspace clusters in different projections of the data. In this work, we propose a general fault tolerance definition enhancing subspace clustering models to handle missing values. We introduce a flexible notion of fault tolerance that adapts to the individual characteristics of subspace clusters and ensures a robust parameterization. Allowing missing values in our model increases the computational complexity of subspace clustering. Thus, we prove novel monotonicity properties for an efficient computation of fault tolerant subspace clusters. Experiments on real and synthetic data show that our fault tolerance model yields high quality results even in the presence of many missing values. For repeatability, we provide all datasets and executables on our website.

Due to the ever growing presence of data streams, there has been a considerable amount of research on stream mining algorithms. While many algorithms have been introduced that tackle the problem of clustering on evolving data streams, hardly any attention has been paid to appropriate evaluation measures. Measures developed for static scenarios, namely structural measures and ground-truth-based measures, cannot correctly reflect errors attributable to emerging, splitting, or moving clusters. These situations are inherent to the streaming context due to the dynamic changes in the data distribution. In this paper we develop a novel evaluation measure for stream clustering called Cluster Mapping Measure (CMM). CMM effectively indicates different types of errors by taking the important properties of evolving data streams into account. We show in extensive experiments on real and synthetic data that CMM is a robust measure for stream clustering evaluation.

Context prediction is an emerging topic in the fields of data mining and information management which is both promising and challenging. Predicting the location of mobile objects was a frequently tackled subtask of mobile context prediction in recent researches. For scenarios of managing health information of mobile persons, the prediction of near future health status of persons is at least equally important to predicting their location. We introduce in this paper, to the best of our knowledge, a first method for predicting a next health context of mobile persons equipped with body sensors and a mobile device. The suggested Prefix Span-based method searches for sequential patterns within multiple streaming inputs from the body sensors as well as other contextual streams that influence the health context. We discuss additionally the implementation of our method in an energy aware mobile-server environment.

The Signature Quadratic Form Distance has been introduced as an adaptive similarity measure coping with flexible content representations of various multimedia data. Although the Signature Quadratic Form Distance has shown good retrieval performance with respect to their qualities of effectiveness and efficiency, its applicability to index structures remains a challenging issue due to its dynamic nature. In this paper, we investigate the indexability of the Signature Quadratic Form Distance regarding metric access methods. We show how the distance's inherent parameters determine the indexability and analyze the relationship between effectiveness and efficiency on numerous image databases.

We introduce a distance-based similarity model with application to the optimization of the fuel injection process. Our model allows for an automatic evaluation of huge and complex amount of experimental data originated from optical measurement techniques analyzing the fuel injection process. The goal is to enable researchers to get deeper insight into this process based on an automatically driven analysis.

The Earth Mover's Distance is a well-known distance measure employed in various domains, especially for content-based retrieval in multimedia databases. However, the distance evaluation is a considerably expensive task and thus for large multimedia databases, efficient query processing becomes a challenging problem. In this paper, we introduce a parameterized version of the Earth Mover's Distance that can be used by database experts to change the distance distribution in the derived distance space in order to improve the indexability. We empirically show, that we can significantly improve the indexability of the distance space and that we can tune the retrieval quality by adapting the parameterized Earth Mover's Distance.

Outlier mining is an important data analysis task to distinguish exceptional outliers from regular objects. However, in recent applications traditional outlier mining approaches miss outliers as they are hidden in subspace projections.

Detecting emerging problems in information and manufacturing systems is the goal of monitoring tools. Good and timely detection of problematic conditions from measured indicators requires efficient and effective detection of critical patterns in a stream of incoming observations.

Today's applications deal with multiple types of information: graph data to represent the relations between objects and attribute data to characterize single objects. Analyzing both data sources simultaneously can increase the quality of mining methods. Recently, combined clustering approaches were introduced, which detect densely connected node sets within one large graph that also show high similarity according to all of their attribute values. However, for attribute data it is known that this full-space clustering often leads to poor clustering results. Thus, subspace clustering was introduced to identify locally relevant subsets of attributes for each cluster. In this work, we propose a method for finding homogeneous groups by joining the paradigms of subspace clustering and dense sub graph mining, i.e. we determine sets of nodes that show high similarity in subsets of their dimensions and that are as well densely connected within the given graph. Our twofold clusters are optimized according to their density, size, and number of relevant dimensions. Our developed redundancy model confines the clustering to a manageable size of only the most interesting clusters. We introduce the algorithm Gamer for the efficient calculation of our clustering. In thorough experiments on synthetic and real world data we show that Gamer achieves low runtimes and high clustering qualities.

Traditional clustering algorithms identify just a single clustering of the data. Today's complex data, however, allow multiple interpretations leading to several valid groupings hidden in different views of the database. Each of these multiple clustering solutions is valuable and interesting as different perspectives on the same data and several meaningful groupings for each object are given. Especially for high dimensional data where each object is described by multiple attributes, alternative clusters in different attribute subsets are of major interest. In this tutorial, we describe several real world application scenarios for multiple clustering solutions. We abstract from these scenarios and provide the general challenges in this emerging research area. We describe state-of-the-art paradigms, we highlight specific techniques, and we give an overview of this topic by providing a taxonomy of the existing methods. By focusing on open challenges, we try to attract young researchers for participating in this emerging research field.

Analyzing uncertain databases is a challenge in data mining research. Usually, data mining methods rely on precise values. In scenarios where uncertain values occur, e.g. due to noisy sensor readings, these algorithms cannot deliver high-quality patterns. Beside uncertainty, data mining methods face another problem: high dimensional data. For finding object groupings with locally relevant dimensions in this data, subspace clustering was introduced. For high dimensional uncertain data, however, deciding whether dimensions are relevant for a subspace cluster is even more challenging; thus, approaches for effective subspace clustering on uncertain databases are needed. In this paper, we develop a method for subspace clustering for uncertain data that delivers high-quality patterns; the information provided by the individual distributions of objects is used in an effective manner. Because in uncertain scenarios a strict assignment of objects to single clusters is not appropriate, we enrich our model with the concept of membership degree. Subspace clustering for uncertain data is computationally expensive; thus, we propose an efficient algorithm. In thorough experiments we show the effectiveness and efficiency of our new subspace clustering method.

Large data resources are ubiquitous in science and business. For these domains, an intuitive view on the data is essential to fully exploit the hidden knowledge. Often, these data can be semantically structured by concepts. Since the determination of concepts requires a thorough analysis of the data, data mining methods have to be applied. In the field of subspace clustering, some techniques have recently shown to be effective for this task. Although these methods generate concept-based patterns, the user has to provide domain knowledge to gain reasonable concepts out of the data. Our demonstration CoDA (Concept Determination and Analysis) is a tool that supports the user in the final step of concept definition. More concretely, the user is guided through an iterative, interactive process in which concepts are suggested, analyzed, and potentially refined. The core aspect of CoDA is an intuitive, concept-driven presentation of subspace clusters such that concepts can be visually captured.

In the knowledge discovery process, clustering is an established technique for grouping objects based on mutual similarity. However, in today's applications for each object very many attributes are provided. As multiple concepts described by different attributes are mixed in the same data set, clusters do not appear in all dimensions. In these high dimensional data spaces, each object can be clustered in several projections of the data. However, recent clustering techniques do not succeed in detection of these orthogonal concepts hidden in the data. They either miss multiple concepts for each object by partitioning approaches or provide redundant clusters in very similar subspaces.

Determining similar objects is a fundamental operation both in data mining tasks such as clustering and in query-driven object retrieval. By definition of similarity search, query objects can only be imprecise descriptions of what users are looking for in a database, and even high-quality similarity measures can only be approximations of the users' notion of similarity. To overcome these shortcomings, iterative query refinement systems have been proposed. They utilize user feedback regarding the relevance of intermediate results to adapt the query object and/or the similarity measure.

In this work we concentrate on categorization of relational attributes based on their data type. Assuming that attribute type/characteristics are unknown or unidentifiable, we analyze and compare a variety of type-based signatures for classifying the attributes based on the semantic type of the data contained therein (e.g., router identifiers, social security numbers, email addresses). The signatures can subsequently be used for other applications as well, like clustering and index optimization/compression. This application is useful in cases where very large data collections that are generated in a distributed, ungoverned fashion end up having unknown, incomplete, inconsistent or very complex schemata and schema level meta-data. We concentrate on heuristically generating type-based attribute signatures based on both local and global computation approaches. We show experimentally that by decomposing data into q-grams and then considering signatures based on q-gram distributions, we achieve very good classification accuracy under the assumption that a large sample of the data is available for building the signatures. Then, we turn our attention to cases where a very small sample of the data is available, and hence accurately capturing the q-gram distribution of a given data type is almost impossible. We propose techniques based on dimensionality reduction and soft-clustering that exploit correlations between attributes to improve classification accuracy.

Classification of streaming data faces three basic challenges: it has to deal with huge amounts of data, the varying time between two stream data items must be used best possible (anytime classification) and additional training data must be incrementally learned (anytime learning) for applying the classifier consistently to fast data streams. In this work, we propose a novel index-based technique that can handle all three of the above challenges using the established Bayes classifier on effective kernel density estimators. Our novel Bayes tree automatically generates (adapted efficiently to the individual object to be classified) a hierarchy of mixture densities that represent kernel density estimators at successively coarser levels. Our probability density queries together with novel classification improvement strategies provide the necessary information for very effective classification at any point of interruption. Moreover, we propose a novel evaluation method for anytime classification using Poisson streams and demonstrate the anytime learning performance of the Bayes tree.

Clustering streaming data requires algorithms which are capable of updating clustering results for the incoming data. As data is constantly arriving, time for processing is limited. Clustering has to be performed in a single pass over the incoming data and within the possibly varying inter-arrival times of the stream. Likewise, memory is limited, making it impossible to store all data. For clustering, we are faced with the challenge of maintaining a current result that can be presented to the user at any given time. In this work, we propose a parameter free algorithm that automatically adapts to the speed of the data stream. It makes best use of the time available under the current constraints to provide a clustering of the objects seen up to that point. Our approach incorporates the age of the objects to reflect the greater importance of more recent data. Moreover, we are capable of detecting concept drift, novelty and outliers in the stream. For efficient and effective handling, we introduce the ClusTree, a compact and self-adaptive index structure for maintaining stream summaries. Our experiments show that our approach is capable of handling a multitude of different stream characteristics for accurate and scalable anytime stream clustering.

Subspace clustering aims at detecting clusters in any subspace projection of a high dimensional space. As the number of possible subspace projections is exponential in the number of dimensions, the result is often tremendously large. Recent approaches fail to reduce results to relevant subspace clusters. Their results are typically highly redundant, i.e. many clusters are detected multiple times in several projections. In this work, we propose a novel model for relevant subspace clustering (RESCU). We present a global optimization which detects the most interesting non-redundant subspace clusters. We prove that computation of this model is NP-hard. For RESCU, we propose an approximative solution that shows high accuracy with respect to our relevance model. Thorough experiments on synthetic and real world data show that RESCU successfully reduces the result to manageable sizes. It reliably achieves top clustering quality while competing approaches show greatly varying performance.

Subspace clustering and frequent itemset mining via “step-by-step” algorithms that search the subspace/pattern lattice in a top-down or bottom-up fashion do not scale to large high dimensional data bases. Recent “jump” algorithms directly choose candidate subspace regions or patterns. Their scalability and quality depend heavily on the rating of these candidates as mislead jumps incur poor results and costly candidate refinements. Existing techniques rely on simple statistics with low estimation quality or on inefficient data base scans. In this work, we propose DensEst, an efficient density estimator with significantly improved accuracy. It efficiently provides rough estimates of object counts in selective subspace regions. Furthermore, by incorporating correlations between dimensions DensEst achieves not only efficient but also highly accurate estimations. We show how this density estimation technique can be easily integrated into subspace clustering and frequent itemset mining algorithms to improve both their efficiency and accuracy. We demonstrate the performance of our density estimation technique in thorough experiments and show its efficiency and accuracy improvement for existing algorithms.

Time series arise in many different applications in the form of sensor data, stocks data, videos, and other time-related information. Analysis of this data typically requires searching for similar time series in a database. Dynamic Time Warping (DTW) is a widely used high-quality distance measure for time series. As DTW is computationally expensive, efficient algorithms for fast computation are crucial. In this paper, we propose a novel filter-and-refine DTW algorithm called Anticipatory DTW. Existing algorithms aim at efficiently finding similar time series by filtering the database and computing the DTW in the refinement step. Unlike these algorithms, our approach exploits previously unused information from the filter step during the refinement, allowing for faster rejection of false candidates. We characterize a class of applicable filters for our approach, which comprises state-of-the-art lower bounds of the DTW. Our novel anticipatory pruning incurs hardly any over-head and no false dismissals. We demonstrate substantial efficiency improvements in thorough experiments on synthetic and real world time series databases and show that our technique is highly scalable to multivariate, long time series and wide DTW bands.

Clustering high dimensional data is an emerging research field.Subspace clusteringorprojected clusteringgroup similar objects in subspaces, i.e. projections, of the full space. In the past decade, several clustering paradigms have been developed in parallel, without thorough evaluation and comparison between these paradigms on a common basis. Conclusive evaluation and comparison is challenged by three major issues. First, there is no ground truth that describes the "true" clusters in real world data. Second, a large variety of evaluation measures have been used that reflect different aspects of the clustering result. Finally, in typical publications authors have limited their analysis to their favored paradigm only, while paying other paradigms little or no attention. In this paper, we take a systematic approach to evaluate the major paradigms in a common framework. We study representative clustering algorithms to characterize the different aspects of each paradigm and give a detailed comparison of their properties. We provide a benchmark set of results on a large variety of real world and synthetic data sets. Using different evaluation measures, we broaden the scope of the experimental analysis and create a common baseline for future developments and comparable evaluations in the field. For repeatability, all implementations, data sets and evaluation measures are available on our website.

Subspace clustering mines clusters hidden in subspaces of high-dimensional data sets. Density-based approaches have been shown to successfully mine clusters of arbitrary shape even in the presence of noise in full space clustering. Exhaustive search of all density-based subspace clusters, however, results in infeasible runtimes for large high-dimensional data sets. This is due to the exponential number of possible subspace projections in addition to the high computational cost of density-based clustering.

Continuous growth in sensor data and other temporal data increases the importance of retrieval and similarity search in time series data. Efficient time series query processing is crucial for interactive applications. Existing multidimensional indexes like the R-tree provide efficient querying for only relatively few dimensions. Time series are typically long which corresponds to extremely high dimensional data in multidimensional indexes. Due to massive overlap of index descriptors, multidimensional indexes degenerate for high dimensions and access the entire data by random I/O. Consequently, the efficiency benefits of indexing are lost.

Multimedia similarity search in large databases requires efficient query processing. The Earth mover's distance, introduced in computer vision, is successfully used as a similarity model in a number of small-scale applications. Its computational complexity hindered its adoption in large multimedia databases. We enable directly indexing the Earth mover's distance in structures such as the R-tree and the VA-file by providing the accurate 'MinDist' function to any bounding rectangle in the index. We exploit the computational structure of the new MinDist to derive a new lower bound for the EMD MinDist which is assembled from quantized partial solutions yielding very fast query processing times. We prove completeness of our approach in a multistep scheme. Extensive experiments on real world data demonstrate the high efficiency.

Subspace clustering aims at detecting clusters in any subspace projection of a high dimensional space. As the number of projections is exponential in the number of dimensions, efficiency is crucial. Moreover, the resulting subspace clusters are often highly redundant, i.e. many clusters are detected multiply in several projections. We propose a novel index for efficient subspace clustering in a novel depth-first processing with in-process-removal of redundant clusters for better pruning. Thorough experiments on real and synthetic data show that INSCY yields substantial efficiency and quality improvements.

Data mining techniques extract interesting patterns out of large data resources. Meaningful visualization and interactive exploration of patterns are crucial for knowledge discovery. Visualization techniques exist for traditional clustering in low dimensional spaces. In high dimensional data, clusters typically only exist in subspace projections. This subspace clustering, however, lacks interactive visualization tools. Challenges arise from typically large result sets in different subspace projections that hinder comparability, visualization and understandability.

Health and mobility of elderly people is gaining importance in aging societies. New communication-based methods to provide health services with personal health care devices are considered promising elements of first-class medical care services for everybody. To achieve this vision, several technological issues have to be solved: (i) body sensors to monitor vital functions have to be developed; (ii) these sensors should be integrated into textile structures to guarantee ease of use and patient acceptance; (iii)the collected sensor data has to be analyzed to detect emergency situations and to reduce the data volume; (iv) relevant data has to be integrated with other information systems in the work environment of medical experts. These challenges are addressed within the HealthNet project at RWTH Aachen University. The goal of the project is to develop a framework in which health professional scan remotely monitor and diagnose mobile patients. The described demonstration presents our results of the first three issues mentioned above while focusing on the employed data mining and management techniques.

The Earth Mover's Distance (EMD) was developed in computer vision as a flexible similarity model that utilizes similarities in feature space to define a high quality similarity measure in feature representation space. It has been successfully adopted in a multitude of applications with low to medium dimensionality. However, multimedia applications commonly exhibit high-dimensional feature representations for which the computational complexity of the EMD hinders its adoption. An efficient query processing approach that mitigates and overcomes this effect is crucial. We propose novel dimensionality reduction techniques for the EMD in a filter-and-refine architecture for efficient lossless retrieval. Thorough experimental evaluation on real world data sets demonstrates a substantial reduction of the number of expensive high-dimensional EMD computations and thus remarkably faster response times. Our techniques are fully flexible in the number of reduced dimensions, which is a novel feature in approximation techniques for the EMD.

In a project, customers are attracted by a video streaming application. A video camera records people passing by, and a monitor shows an alienated version of the setting accordingly. The idea is to replace the image on the video screen by a mosaic of similar images to draw their attention to the location. For successful implementation, several aspects are of key importance: the images chosen in the mosaic should be similar enough for easy recognition, and the result of the alienation should be computed fast enough for display on the screen in real time.

To gain insight into today's large data resources, data mining provides automatic aggregation techniques. Clustering aims at grouping data such that objects within groups are similar while objects in different groups are dissimilar. In scenarios with many attributes or with noise, clusters are often hidden in subspaces of the data and do not show up in the full dimensional space. For these applications, subspace clustering methods aim at detecting clusters in any subspace. Existing subspace clustering approaches fall prey to an effect we call dimensionality bias. As dimensionality of subspaces varies, approaches which do not take this effect into account fail to separate clusters from noise. We give a formal definition of dimensionality bias and analyze consequences for subspace clustering. A dimensionality unbiased subspace clustering (DUSC) definition based on statistical foundations is proposed. In thorough experiments on synthetic and real world data, we show that our approach outperforms existing subspace clustering algorithms.

Todays abundance of storage coupled with digital technologies in virtually any scientific or commercial application such as medical and biological imaging or music archives deal with tremendous quantities of images, videos or audio files stored in large multimedia databases. For content-based data mining and retrieval purposes suitable similarity models are crucial. The Earth Mover’s Distance was introduced in Computer Vision to better approach human perceptual similarities. Its computation, however, is too complex for usage in interactive multimedia database scenarios. In order to enable efficient query processing in large databases, we propose an index-supported multistep algorithm. We therefore develop new lower bounding approximation techniques for the Earth Mover’s Distance which satisfy high quality criteria including completeness (no false drops), index-suitability and fast computation. We demonstrate the efficiency of our approach in extensive experiments on large image databases

We present a novel algorithm called CLICKS, that finds clusters in categorical datasets based on a search for k-partite maximal cliques. Unlike previous methods, CLICKS mines subspace clusters. It uses a selective vertical method to guarantee complete search. CLICKS outperforms previous approaches by over an order of magnitude and scales better than any of the existing method for high-dimensional datasets. These results are demonstrated in a comprehensive performance study on real and synthetic datasets.

We implemented our new approach for efficient similarity search in large databases of tree structures. Our experiments show that filtering significantly accelerates the complex task of similarity search for tree-structured objects. Moreover, they show that no single feature of a tree is sufficient for effective filtering, but only the combination of structural and content-based filters yields good results.

The increasing use of temporal and spatial data in present-day relational systems necessitates an efficient support of joins on interval-valued attributes. Standard join algorithms do not support those data types adequately, whereas special approaches for interval joins usually require an augmentation of the internal access methods which is not supported by existing relational systems. To overcome these problems we introduce new join algorithms for interval data. Based on the Relational Interval Tree, these algorithms can easily be implemented on top of any relational database system while providing excellent performance on joining intervals. As experimental results on an Oracle9i server show, the new techniques outperform existing relational methods for joining intervals significantly.

Similarity search in database systems is becoming an increasingly important task in modern application domains such as multimedia, molecular biology, medical imaging and many others. Especially for CAD applications, suitable similarity models and a clear representation of the results can help to reduce the cost of developing and producing new parts by maximizing the reuse of existing parts. In this paper, we adapt two known similarity models to voxelized 3-D CAD data and introduce a new model based on eigenvectors. The experimental evaluation of our three similarity models is based on two real-world test datasets. Furthermore, we introduce hierarchical clustering as a new and effective way to analyse and compare similarity models. We show that both our similarity model as well as our evaluation procedure are suitable for industrial use.

Modern database applications including computer-aided design (CAD), medical imaging, or molecular biology impose new requirements on spatial query processing. Particular problems arise from the need of high resolutions for very large spatial objects, including cars, space stations, planes and industrial plants, and from the design goal to use general purpose database management systems in order to guarantee industrial-strength. In the past two decades, various stand-alone spatial index structures have been proposed but their integration into fully-fledged database systems is problematic. Most of these approaches are based on decomposition of spatial objects leading to replicating index structures. In contrast to common black-and-white decompositions which suffer from the lack of intermediate solutions, we introduce grey approximations as a new and general concept. We demonstrate the benefits of grey approximations in the context of encoding spatial objects by space filling curves resulting in grey interval sequences. Spatial intersection queries are then processed by a filter and refine architecture which, as an important design goal, can purely be expressed by means of the SQL: 1999 standard. Our new High Resolution Indexing (HRI) method can easily be integrated into general purpose DBMSs. The experimental evaluation on real-world test data from car and plane design projects points out that our new concept outperforms competitive techniques that are implementable on top of a standard object-relational DBMS by an order of magnitude with respect to secondary storage space and overall query response time.

The efficient management of interval data represents a core requirement for many temporal and spatial database applications. With the relational interval tree (RI-tree), an efficient access method has been proposed to process interval intersection queries on top of existing object-relational database systems. The paper complements that approach by effective and efficient models to estimate the selectivity and the I/O cost of interval intersection queries in order to guide the cost-based optimizer whether and how to include the RI-tree into the execution plan. By design, the models immediately fit to common extensible indexing/optimization frameworks, and their implementations exploit the built-in statistics facilities of the database server. According to our experimental evaluation on an Oracle database, the average relative error of the estimated cost to the actual cost of index scans ranges from 0% to 23%, depending on the resolution of the persistent statistics and the size of the query objects.

This demonstration presents a spatial database integration for novel CAD applications into off-the-shelf database systems. Spatial queries on even large product databases for digital mockup or haptic rendering are performed at interactive response times.

Similarity search in multimedia databases requires an efficient support of nearest-neighbor search on a large set of high-dimensional points as a basic operation for query processing. As recent theoretical results show, state of the art approaches to nearest-neighbor search are not efficient in higher dimensions. In our new approach, we therefore precompute the result of any nearest-neighbor search which corresponds to a computation of the Voronoi cell of each data point. In a second step, we store conservative approximations of the Voronoi cells in an index structure efficient for high-dimensional data spaces. As a result, nearest neighbor search corresponds to a simple point query on the index structure. Although our technique is based on a precomputation of the solution space, it is dynamic, i.e., it supports insertions of new data points. An extensive experimental evaluation of our technique demonstrates the high efficiency for uniformly distributed as well as real data. We obtained a significant reduction of the search time compared to nearest neighbor search in other index structures such as the X-tree.

Similarity search in multimedia databases requires an efficient support of nearest neighbor search on a large set of high dimensional points as a basic operation for query processing. As recent theoretical results show, state of the art approaches to nearest neighbor search are not efficient in higher dimensions. In our new approach, we therefore precompute the result of any nearest neighbor search which corresponds to a computation of the voronoi cell of each data point. In a second step, we store the voronoi cells in an index structure efficient for high dimensional data spaces. As a result, nearest neighbor search corresponds to a simple point query on the index structure. Although our technique is based on a precomputation of the solution space, it is dynamic, i.e. it supports insertions of new data points. An extensive experimental evaluation of our technique demonstrates the high efficiency for uniformly distributed as well as real data. We obtained a significant reduction of the search time compared to nearest neighbor search in the X tree (up to a factor of 4).

For an increasing number of modern database applications, efficient support of similarity search becomes an important task. Along with the complexity of the objects such as images, molecules and mechanical parts, also the complexity of the similarity models increases more and more. Whereas algorithms that are directly based on indexes work well for simple medium-dimensional similarity distance functions, they do not meet the efficiency requirements of complex high-dimensional and adaptable distance functions. The use of a multi-step query processing strategy is recommended in these cases, and our investigations substantiate that the number of candidates which are produced in the filter step and exactly evaluated in the refinement step is a fundamental efficiency parameter. After revealing the strong performance shortcomings of the state-of-the-art algorithm for k-nearest neighbor search [Korn et al. 1996], we present a novel multi-step algorithm which is guaranteed to produce the minimum number of candidates. Experimental evaluations demonstrate the significant performance gain over the previous solution, and we observed average improvement factors of up to 120 for the number of candidates and up to 48 for the total runtime.

Shape similarity searching is a crucial task in image databases, particularly in the presence of errors induced by segmentation or scanning images. The resulting slight displacements or rotations have not been considered so far in the literature. We present a new similarity model that flexibly addresses this problem. By specifying neighborhood influence weights, the user may adapt the similarity distance functions to his or her own requirements or preferences. Technically, the new similarity model is based on quadratic forms for which we present a multi-step query processing architecture, particularly for high dimensions as they occur in image databases. Our algorithm to reduce the dimensionality of quadratic form-based similarity queries results in a lower-bounding distance function that is proven to provide an optimal filter selectivity. Experiments on our test database of 10,000 images demonstrate the applicability and the performance of our approach, even in dimensions as high as 1,024.

Describes a query system that provides visual relevance feedback in querying large databases. The goal is to support the process of data mining by representing as many data items as possible on the display. By arranging and coloring the data items as pixels according to their relevance for the query, the user gets a visual impression of the resulting data set. Using an interactive query interface, the user may change the query dynamically and receives immediate feedback by the visual representation of the resulting data set. Furthermore, by using multiple windows for different parts of a complex query, the user gets visual feedback for each part of the query and, therefore, may easier understand the overall result. The system allows one to represent the largest amount of data that can be visualized on current display technology, provides valuable feedback in querying the database, and allows the user to find results which would otherwise remain hidden in the database.>