As explainable artificial intelligence (XAI) becomes more prevalent, concerns arise about the unintended privacy risks associated with model explanations. In this paper, we study the antagonism between explainability and privacy by evaluating the extent to which post-hoc explanations can leak sensitive data. We perform a comparative analysis of three popular XAI methods (SHAP, LIME, and DiCE) applied to Decision Trees, Random Forests, and Neural Networks. We focus on two types of privacy attacks: Membership Inference Attacks and Training Data Extraction. Using datasets of varying complexity, we measure attack success rates and information leakage from explanations. Our results shows that each proposed membership inference attack and training data extraction attack are feasible. These findings highlight the urgent need to design privacy-preserving explainability tools that balance interpretability with user data protection.

Future sustainable energy systems require the integration of local renewable energy sources (RES) into decentralized micro-grids, each containing RES, energy storage systems, and local loads. A substantial challenge associated with micro-grids is the optimization of energy flows to minimize operating costs. This is particularly complex due to (a) the fluctuating power generation of RES, (b) the variability of local loads, and (c) the possibility of energy trade between a micro-grid and a larger ‘utility grid’ that it connects to. Existing methods struggle to manage these sources of uncertainty effectively. To address this, we propose MicroPPO, a reinforcement learning approach for real-time management of power flows in such small-scale energy systems. MicroPPO introduces a novel definition of the environment as a Markov Decision Process (MDP) with a continuous and multi-dimensional action space. This enables more precise control of power flows compared to discrete methods. Additionally, MicroPPO employs an innovative actor network architecture featuring multiple network branches to reflect the individual action dimensions. It further integrates a differentiable projection layer that enforces the feasibility of actions. We assess the performance of our approach against state-of-the-art methods using real-world data. Our results demonstrate MicroPPO's superior convergence towards near-optimal policies.

We study the stochastic Budgeted Multi-Armed Bandit (MAB) problem, where a player chooses from K arms with unknown expected rewards and costs. The goal is to maximize the total reward under a budget constraint. A player thus seeks to choose the arm with the highest reward-cost ratio as often as possible. Current approaches for this problem have several issues, which we illustrate. To overcome them, we propose a new upper confidence bound (UCB) sampling policy, ømega-UCB, that uses asymmetric confidence intervals. These intervals scale with the distance between the sample mean and the bounds of a random variable, yielding a more accurate and tight estimation of the reward-cost ratio compared to our competitors. We show that our approach has sublinear instance-dependent regret in general and logarithmic regret for parameter ρ ≥ 1, and that it outperforms existing policies consistently in synthetic and real settings.

Dynamic graphs are often the initial data for scientific analyses. However, existing methods designed for static graphs struggle with efficiency and accuracy when applied dynamically. One challenge occurs when local interactions in dynamic graphs influence global phenomena. Practitioners then follow the evolution of relationships between individual elements in local structures. Such structures are called Durable Graph Patterns or evolving subgraphs. This work introduces the Durable Graph Pattern Query Language (DPQGL), which allows for user-friendly querying of durable graph patterns on dynamic graphs. DPGQL is, by design, agnostic to the underlying durable pattern-matching algorithm. We base our proposed language on the widely used Cypher Query Language. In our experiments with seven pattern shapes in 24 variations on real-world materials science data, we explore the impact on query runtimes from query complexity and the frequency of graph changes.

Abstract Change detection is of fundamental importance when analyzing data streams. Detecting changes both quickly and accurately enables monitoring and prediction systems to react, e.g., by issuing an alarm or by updating a learning algorithm. However, detecting changes is challenging when observations are high-dimensional. In high-dimensional data, change detectors should not only be able to identify when changes happen, but also in which subspace they occur. Ideally, one should also quantify how severe they are. Our approach, ABCD, has these properties. ABCD learns an encoder-decoder model and monitors its accuracy over a window of adaptive size. ABCD derives a change score based on Bernstein’s inequality to detect deviations in terms of accuracy, which indicate changes. Our experiments demonstrate that ABCD outperforms its best competitor by up to 20% in F1-score on average. It can also accurately estimate changes’ subspace, together with a severity measure that correlates with the ground truth.

Outlier generation is a popular technique used to solve important outlier detection tasks. Generating outliers with realistic behavior is challenging. Popular existing methods tend to disregard the “multiple views” property of outliers in high-dimensional spaces. The only existing method accounting for this property falls short in efficiency and effectiveness. We propose Bisect , a new outlier generation method that creates realistic outliers mimicking said property. To do so, Bisect employs a novel proposition introduced in this article stating how to efficiently generate said realistic outliers. Our method has better guarantees and complexity than the current method for recreating “multiple views.” We use the synthetic outliers generated by Bisect to effectively enhance outlier detection in diverse datasets for multiple use cases. For instance, oversampling with Bisect reduced the error by up to 3 times when compared with the baselines.

Storing, querying, predicting, and interpolating trajectories of moving objects is a topic which the database community has studied for decades. We study a new variant of this problem in this article: We deal with a set of moving objects which do not have an identity, i.e., one does not know whether an object is identical to one observed earlier at another position. Our use case is a stream of images of cells of developing embryos. There exist so-called tracking tools. They match cells in such image sequences, to build trajectory vectors. However, these trackers have certain weaknesses, including counter-intuitive parameters and the expectation of users manually correcting trajectories. In this paper, we propose fully automatic tracking algorithms. They rely on space partitioning heuristics to match cells. This gives way to much cheaper data-analysis pipelines, as we will explain. We also propose two algorithms predicting the next positions of cells, given earlier ones. Experiments over 12 datasets show that our new approaches reduce the execution time by up to 7.8 times for tracking and 6.2 times for prediction. Prediction quality increases by up to 5.6% over the best tracker. • Cells can be modeled as moving objects without identity that move under uncertainty. • Predictors establish cell motion accurately based on observed cell positions. • Cell prediction avoids computationally costly steps of the tracking pipeline.

Scenario discovery is the process of finding areas of interest, known as scenarios, in data spaces resulting from simulations. For instance, one might search for conditions, i.e., inputs of the simulation model, where the system is unstable. Subgroup discovery methods are commonly used for scenario discovery. They find scenarios in the form of hyperboxes, which are easy to comprehend. Given a computational budget, results tend to get worse as the number of inputs of the simulation model and the cost of simulations increase. We propose a new procedure for scenario discovery from few simulations, dubbed REDS. A key ingredient is using an intermediate machine learning model to label data for subsequent use by conventional subgroup discovery methods. We provide statistical arguments why this is an improvement. In our experiments, REDS reduces the number of simulations required by 50--75% on average, depending on the quality measure. It is also useful as a semi-supervised subgroup discovery method and for discovering better scenarios from third-party data, when a simulation model is not available.

Abstract Estimating dependencies from data is a fundamental task of Knowledge Discovery. Identifying the relevant variables leads to a better understanding of data and improves both the runtime and the outcomes of downstream Data Mining tasks. Dependency estimation from static numerical data has received much attention. However, real-world data often occurs as heterogeneous data streams: On the one hand, data is collected online and is virtually infinite. On the other hand, the various components of a stream may be of different types, e.g., numerical, ordinal or categorical. For this setting, we propose Monte Carlo Dependency Estimation (MCDE), a framework that quantifies multivariate dependency as the average statistical discrepancy between marginal and conditional distributions, via Monte Carlo simulations. MCDE handles heterogeneity by leveraging three statistical tests: the Mann–Whitney U, the Kolmogorov–Smirnov and the Chi-Squared test. We demonstrate that MCDE goes beyond the state of the art regarding dependency estimation by meeting a broad set of requirements. Finally, we show with a real-world use case that MCDE can discover useful patterns in heterogeneous data streams.

Abstract Database outsourcing is a challenge concerning data secrecy. Even if an adversary, including the service provider, accesses the data, she should not be able to learn any information from the accessed data. In this paper, we address this problem for graph-structured data. First, we define a secrecy notion for graph-structured data based on the concepts of indistinguishability and searchable encryption. To address this problem, we propose an approach based on bucketization. Next to bucketization, it makes use of obfuscated indexes and encryption. We show that finding an optimal bucketization tailored to graph-structured data is NP-hard; therefore, we come up with a heuristic. We prove that the proposed bucketization approach fulfills our secrecy notion. In addition, we present a performance model for scale-free networks which consists of (1) a number-of-buckets model that estimates the number of buckets obtained after applying our bucketization approach and (2) a query-cost model. Finally, we demonstrate with a set of experiments the accuracy of our number-of-buckets model and the efficiency of our approach with respect to query processing.

By definition, outliers are rarely observed in reality, making them difficult to detect or analyze. Artificial outliers approximate such genuine outliers and can, for instance, help with the detection of genuine outliers or with benchmarking outlier-detection algorithms. The literature features different approaches to generate artificial outliers. However, systematic comparison of these approaches remains absent. This surveys and compares these approaches. We start by clarifying the terminology in the field, which varies from publication to publication, and we propose a general problem formulation. Our description of the connection of generating outliers to other research fields like experimental design or generative models frames the field of artificial outliers. Along with offering a concise description, we group the approaches by their general concepts and how they make use of genuine instances. An extensive experimental study reveals the differences between the generation approaches when ultimately being used for outlier detection. This survey shows that the existing approaches already cover a wide range of concepts underlying the generation, but also that the field still has potential for further development. Our experimental study does confirm the expectation that the quality of the generation approaches varies widely, for example, in terms of the dataset they are used on. Ultimately, to guide the choice of the generation approach in a specific context, we propose an appropriate general-decision process. In summary, this survey comprises, describes, and connects all relevant work regarding the generation of artificial outliers and may serve as a basis to guide further research in the field.

Benchmarking unsupervised outlier detection is difficult. Outliers are rare, and existing benchmark data contains outliers with various and unknown characteristics. Fully synthetic data usually consists of outliers and regular instances with clear characteristics and thus allows for a more meaningful evaluation of detection methods in principle. Nonetheless, there have only been few attempts to include synthetic data in benchmarks for outlier detection. This might be due to the imprecise notion of outliers or to the difficulty to arrive at a good coverage of different domains with synthetic data. In this work, we propose a generic process for the generation of datasets for such benchmarking. The core idea is to reconstruct regular instances from existing real-world benchmark data while generating outliers so that they exhibit insightful characteristics. We propose and describe a generic process for the benchmarking of unsupervised outlier detection, as sketched so far. We then describe three instantiations of this generic process that generate outliers with specific characteristics, like local outliers. To validate our process, we perform a benchmark with state-of-the-art detection methods and carry out experiments to study the quality of data reconstructed in this way. Next to showcasing the workflow, this confirms the usefulness of our proposed process. In particular, our process yields regular instances close to the ones from real data. Summing up, we propose and validate a new and practical process for the benchmarking of unsupervised outlier detection.

In this work, we address the problem of making decisions based on data streams, i.e., choosing an action when a new value is recorded. For instance, actions can be trading decisions in financial markets, choices of controllers in dynamic systems or perturbations of the data stream itself. To start with, we propose a language that allows individuals to formulate requirements on the action space. We use prediction techniques to identify the best possible action. However, for many scenarios there is not just one technique that predicts the future precisely, and different techniques behave quite differently. Thus, since there is no technique that dominates all the others, our conclusion is to take multiple predictions generated by different techniques into account. While ensemble techniques aggregating the predictions seem promising, existing techniques have issues, such as unnecessary information losses or the need for a predefined quality measure. Thus, we propose a new ensemble approach that weights predictions techniques according to requirements and solves an optimization problem that derives decisions directly from weighted predictions. We apply our solution to data privacy on data streams. For this setting, the benefits provided by prediction techniques have not been studied yet. In three case studies, we show that our solution consistently achieves better decision-making quality than approaches from related work.

Support Vector Data Description (SVDD) is a popular one-class classifier, and well-suited for outlier detection. However, the effectiveness of SVDD depends on selecting good hyperparameter values - a difficult problem that has received significant attention in the literature. Since SVDD is an unsupervised classifier, tuning of hyperparameter values is difficult. This has motivated several methods to estimate hyperparameter values based on data characteristics. But existing methods are purely heuristic, and the conditions under which they work well are largely unclear. This has created a situation where instead of selecting hyperparameter values, one has to choose among several, equally plausible heuristics.In this article, we make some strides towards a principled approach to estimate SVDD hyperparameter values. We propose LAMA (Local Active Min-Max Alignment), the first method to select SVDD hyperparameter values by active learning. The core idea is based on kernel alignment, which we adapt to active learning with small sample sizes. LAMA provides estimates for both of the SVDD hyperparameters. These estimates are evidence-based, i.e., rely on actual class labels, and come with a quality score. This eliminates the need for manual validation, an issue with current heuristics. LAMA outperforms state-of-theart competitors in extensive experiments on real-world data. In several cases, LAMA even yields results close to the empirical upper bound.

Nowadays, it is common to classify collections of documents into (human-generated, domain-specific) directory structures, such as email or document folders. But documents may be classified wrongly, for a multitude of reasons. Then they are outlying w.r.t. the folder they end up in. Orthogonally to this, and more specifically, two kinds of errors can occur: (O) Out-of-distribution: the document does not belong to any existing folder in the directory; and (M) Misclassification: the document belongs to another folder. It is this specific combination of issues that we address in this article, i.e., we mine text outliers from massive document directories, considering both error types. We propose a new proximity-based algorithm, which we dub kj-Nearest Neighbours (kj-NN). Our algorithm detects text outliers by exploiting semantic similarities and introduces a self-supervision mechanism that estimates the relevance of the original labels. Our approach is efficient and robust to large proportions of outliers. kj-NN also promotes the interpretability of the results by proposing alternative label names and by finding the most similar documents for each outlier. Our real-world experiments demonstrate that our approach outperforms the competitors by a large margin.

The quality of a classifier hinges on the availability of training data. In scenarios where data collection is restricted or expensive, e.g., compute-intensive simulations, training data may be small and/or biased. In principle, data synthesis then allows to extend the data set. Yet it is difficult for a user to extend the data without any guidance when the data space is unbound or of high dimensionality. In this article we target at the domain expansion problem, i.e., expanding the classifier knowledge beyond an initial sample that completely falls into one class. We first propose a general framework for query synthesis in the one-class setting. Then we present a new query synthesis strategy to quickly explore the data space beyond the initial sample. For the evaluation we derive three options to simulate an oracle in the one-class setting that can answer arbitrary queries. Experiments on both synthetic and real world data demonstrate that our new query strategy indeed expands the knowledge of a one-class classifier beyond a small and biased initial sample. Our strategy outperforms realistic baselines on most domain expansion problems.

Active learning methods collect annotations in the form of class labels, often from human experts, to improve upon some classification task. In many cases, one can collect annotations for a batch of observations at a time, e.g., when several annotators are available. This can make the annotation process more efficient, both regarding human and computational resources. However, selecting a good batch is difficult. It requires to understand several trade-offs between the costs of classifier training, batch selection, annotation effort, and classification accuracy. For one-class classification, a very important application of active learning, batch selection has not received any attention in the literature so far. In this article, we strive to find a sweet spot between the costs of batch-mode learning and classification accuracy. To this end, we first frame batch selection as an optimization problem. We then propose several strategies to identify good batches, discuss their properties, and evaluate them on real-world data. A core result is that a sweet spot indeed exists, with active learning costs reduced by up to an order of magnitude compared to a sequential procedure, without sacrificing accuracy.

In the sciences and elsewhere, the use of relational databases has become ubiquitous. An important challenge is finding hot spots of user interests. In principle, one can discover user interests by clustering the queries in the query log. Such a clustering requires a notion of query similarity. This, in turn, raises the question of what features of SQL queries are meaningful. We have studied the query representations proposed in the literature and corresponding similarity functions and have identified shortcomings of all of them. To overcome these limitations, we propose new similarity functions for SQL queries. They rely on the so-called access area of a query and, more specifically, on the overlap and the closeness of the access areas. We have carried out experiments systematically to compare the various similarity functions described in this article. The first series of experiments measures the quality of clustering and compares it to a ground truth. In the second series, we focus on the query log from the well-known SkyServer database. Here, a domain expert has interpreted various clusters by hand. We conclude that clusters obtained with our new measures of similarity seem to be good indicators of user interests.

Active learning for outlier detection involves users in the process, by asking them for annotations of observations, in the form of class labels. The usual assumption is that users can provide such feedback, regardless of the nature and the presentation of the results. This is a simplification, which may not hold in practice. To overcome it, we propose SubSVDD, a semi-supervised classifier, that learns decision boundaries in low-dimensional projections of the data. SubSVDD de-constructs the outlier classification so that users can comprehend and interpret results more easily. For active learning, SubSVDD features a new update mechanism that adjusts decision boundaries based on user feedback. In particular, it considers that outliers may only occur in some of the low-dimensional projections. We conduct systematic experiments to show the effectiveness of our approach. In a comprehensive benchmark, SubSVDD outperforms alternative approaches on several data sets.

Mutual Information (MI) is an established measure for linear and nonlinear dependencies between two variables. Estimating MI is nontrivial and requires notable computation power for high estimation quality. While some estimation techniques allow trading result quality for lower runtimes, this tradeoff is fixed per task and cannot be adjusted. If the available time is unknown in advance or is overestimated, one may need to abort the estimation without any result. Conversely, when there are several estimation tasks, and one wants to budget computation time between them, there currently is no efficient way to adjust it dynamically based on certain targets, e.g., high MI values or MI values close to a constant. In this article, we present an iterative estimator of MI. Our method offers an estimate with low quality near-instantly and improves this estimate in fine grained steps with more computation time. The estimate also converges towards the result of a conventional estimator. We prove that the time complexity for this convergence is only slightly slower than non-iterative estimation. Additionally, with each step our estimator also tightens statistical guarantees regarding the convergence result, i.e., confidence intervals, progressively. These also serve as quality indicators for early estimates and allow to reliably discern between attribute pairs with weak and strong dependencies. Our experiments show that these guarantees can also be used to execute threshold queries faster compared to non-iterative estimation.

The Multi-Armed Bandit (MAB) is a fundamental model capturing the dilemma between exploration and exploitation in sequential decision making. At every time step, the decision maker selects a set of arms and observes a reward from each of the chosen arms. In this paper, we present a variant of the problem, which we call the Scaling MAB (S-MAB): The goal of the decision maker is not only to maximize the cumulative rewards, i.e., choosing the arms with the highest expected reward, but also to decide how many arms to select so that, in expectation, the cost of selecting arms does not exceed the rewards. This problem is relevant to many real-world applications, e.g., online advertising, financial investments or data stream monitoring. We propose an extension of Thompson Sampling, which has strong theoretical guarantees and is reported to perform well in practice. Our extension dynamically controls the number of arms to draw. Furthermore, we combine the proposed method with ADWIN, a state-of-the-art change detector, to deal with non-static environments. We illustrate the benefits of our contribution via a real-world use case on predictive maintenance.

Similarity search on time series from large temporal text corpora is interesting in many settings. Our use case is the Google Books Ngram corpus and historians interested in the changes of word frequencies over time. More specifically, users are interested in similarity search in a specific period of time, aka. interval-focused similarity search. Related work formalizes interval-focused similarity search, but the sparsely existing approaches are limited to metric distance measures, like the Euclidean distance. Most other approaches in this area, that address the usage of warping distance measures, focus on whole matching similarity search. In this work, we present a novel search tree that uses so-called time series envelopes to group objects. To speed up the tree traversal, our search tree approximates the envelopes based on the node height, i. e., envelopes are tighter further down in the tree. We combine this with various time series pruning techniques, mainly to reduce the number of expensive distance computations. Our experimental evaluation shows that this combination is worthwhile and indeed decisive for a significant speedup, compared to less sophisticated adaptations of known approaches. We, first, show that a combination of both pruning groups of time series and single time series outperforms the usage of a single pruning technique. Secondly, we compare the wall-clock run times of our data structure to existing approaches and determine a significant speed up for focused-interval similarity search queries on large temporal data sets, like the Google Books Ngram corpus.

Mutual information is a measure for both linear and non-linear associations between variables. There exist several estimators of mutual information for static data. In the dynamic case, one needs to apply these estimators to samples of points from data streams. The sampling should be such that more detailed information on the recent past is available. We formulate a list of natural requirements an estimator of mutual information on data streams should fulfill, and we propose two approaches which do meet all of them. Finally, we compare our algorithms to an existing method both theoretically and experimentally. Our findings include that our approaches are faster and have lower bias and better memory complexity.

Estimating dependency is a fundamental task in data management. Identifying the relevant variables leads to better understanding and improves both the runtime and outcome of data analysis. In this paper, we propose Monte Carlo Dependency Estimation (MCDE), a framework to estimate multivariate dependency. MCDE quantifies dependency as the average discrepancy between marginal and conditional distributions via Monte Carlo simulations. Based on this framework, we present Mann-Whitney P (MWP), a novel dependency estimator. We show that MWP satisfies a number of desirable properties and demonstrate the superiority of our estimator against the state-of-the-art multivariate dependency measures.

We consider the following data summarization problem. We are given a dataset including ordinal or numeric explanatory attributes and an outcome attribute. We want to produce a summary of how the explanatory attributes affect the outcome attribute. The summary must be human-interpretable, concise, and informative in the sense that it can accurately approximate the distribution of the outcome attribute. We propose a solution that addresses the fundamental challenge of this problem--handling large numeric domains--and we experimentally show the effectiveness and efficiency of our approach on real datasets.

Sequences of microscopic images feature the dynamics of developing embryos. Automatically tracking the cells from such sequences of images allows understanding the dynamics which a living element demands to know its cells movement, which ideally should take place in real-time. The traditional tracking pipeline starts with image acquisition, data transfer, image segmentation to separate cells from the background, and then the actual tracking step. To speed up this pipeline, we hypothesize that a process capable of predicting the cell motion according to previous observations is useful. The solution must be accurate, fast and lightweight, and be able to iterate between the various components. In this work we propose CM-Predictor, which takes advantage of previous positions of cells to estimate their motion. When estimation takes place, we can omit costly acquisition, transfer and process of images, speeding up the tracking pipeline. The designed solution monitors the error of prediction, adapting the model whenever needed. For validation, we use four different datasets with sequences of images with developing embryos. Then we compare the estimated motion vectors of CM-Predictor with traditional tracking methods. Experimental results show that CM-Predictor is able to accurately estimate the motion vectors. In fact, CM-Predictor maintains the prediction quality of other algorithms and performs faster than them.

Simulations let scientists study properties of complex systems. At first sight, data mining is a good choice when evaluating large numbers of simulations. But it is currently unclear whether there are general principles that might guide the deployment of respective methods to simulation data. In other words, is it worthwhile to target at simulation-data science as a distinct subdiscipline of data science? To identify a respective research agenda and to structure the research questions, we conduct a case study from the domain of materials science. One insight that simulation data may be different from other data regarding its structure and quality, which entails focal points different from the ones of conventional data-analysis projects. It also turns out that interpretability and usability are important notions in our context as well. More attention is needed to gather the various meanings of these terms to align them with the needs and priorities of domain scientists. Finally, we propose extensions to our case study which we deem necessary to generalize our insights towards the guidelines envisioned for simulation-data science.

Mutual Information (MI) is an established measure for the dependence of two variables and is often used as a generalization of correlation measures. Existing methods to estimate MI focus on static data. However, dynamic data is ubiquitous as well, and MI estimates on it are useful for stream mining and advanced monitoring tasks. In dynamic data, small changes (e.g., insertion or deletion of a value) may often invalidate the previous estimate. In this article, we study how to efficiently adjust an existing MI estimate when such a change occurs. As a first step, we focus on the well-known nearest-neighbor based estimators for static data and derive a tight lower bound for their computational complexity, which is unknown so far. We then propose two dynamic data structures that can update existing estimates asymptotically faster than any approach that computes the estimates independently, i.e., from scratch. Next, we infer a lower bound for the computational complexity of such updates, irrespective of the data structure and the algorithm, and present an algorithm that is only a logarithmic factor slower than this bound. In absolute numbers, these solutions offer fast and accurate estimates of MI on dynamic data as well.

Today, many scientific data sets are open to the public. For their owners, it is important to know what the information needs of the users are. In this paper, we study the problem of extracting and analyzing patterns from the query log of a database. We focus on design errors (antipatterns). Antipatterns do not only have a negative effect on query performance, they also might introduce bias on any subsequent analysis of the SQL log. We propose a framework to discover patterns and antipatterns in SQL query logs and to clean antipatterns. To study the usefulness of our approach and to reveal insights on antipatterns in logs of real-world systems, we examine the SQL log of the SkyServer project, with more than 40 million queries. Among the top 15 patterns, we found 6 antipatterns. Altogether, our results give way to the conclusion that antipatterns might falsify refactoring and any other downstream analyses.

When mining data, organizations rely on service providers to carry out the analyses. However, data owners often are only willing to transfer their data when it is encrypted. So encryption must preserve the mining results. Since many mining algorithms are distance-based, we propose the notion of distance-preserving encryption (DPE). Designing a DPE-scheme is challenging, as it depends both on the data and the distance measure in use. We propose a procedure to engineer DPE-schemes, dubbed KIT-DPE. In a case study, we instantiate KIT-DPE for SQL query logs. We design DPE-schemes for all SQL query-distance measures from the literature. For all these measures, we prove that one can use a combination of existing property-preserving encryption schemes with known security characteristics to guarantee the same mining result.

The increasing size of the available data and database volumes represents a real challenge for the data management community. In general, current approaches in data mining require the data to be first extracted from an underlying database. From a practical point of view, this presents many drawbacks. In this short article, we present a possible solution to bridge the gap between data repositories and end user analysis. We demonstrate the interestingness of this approach with ibmdbpy, an open source Python interface developed by IBM for database administration and data analytics.

Mining complex data is an essential and at the same time challenging task. Therefore, organizations pass on their encrypted data to service providers carrying out such analyses. Thus, encryption must preserve the mining results. Many mining algorithms are distance-based. Thus, we investigate how to preserve the results for such algorithms upon encryption. To this end, we propose the notion of distance-preserving encryption (DPE). This notion has just the right strictness - we show that we cannot relax it, using formal arguments as well as experiments. Designing a DPE scheme is challenging, as it depends both on the data set and the specific distance measure in use. We propose a procedure to engineer DPE-schemes, dubbed DisPE. In a case study, we instantiate DisPE for SQL query logs, a type of data containing valuable information about user interests. In this study, we design DPE schemes for all SQL query distance measures from the scientific literature. We formally show that one can use a combination of existing secure property-preserving encryption schemes to this end. Finally, we discuss on the generalizability of our findings using two other data sets as examples.

Today, many scientific data sets are open to the public. For their operators, it is important to know what the users are interested in. In this paper, we study the problem of extracting and analyzing patterns from the query log of a database. We focus on design errors (antipatterns), which typically lead to unnecessary SQL statements. Such antipatterns do not only have a negative effect on performance. They also introduce bias on any subsequent analysis of the SQL log. We propose a framework designed to discover patterns and antipatterns in arbitrary SQL query logs and to clean antipatterns. To study the usefulness of our approach and to reveal insights regarding the existence of antipatterns in real-world systems, we examine the SQL log of the SkyServer project, containing more than 40 million queries. Among the top 15 patterns, we have found six antipatterns. This result as well as other ones gives way to the conclusion that antipatterns might falsify refactoring and any other downstream analyses.

We show both formally and by means of experiments that self-tuning histograms suffer from three major problems - sensitivity to learning, stagnation, and dimensionality. We also describe our solution to the problem - which is histogram initialization with subspace clustering.

Clustering methods based on modularity are wellestablished and widely used for graph data. However, today's applications store additional attribute information for each node in the graph. This attribute information may even be contradicting with the graph structure, which raises a major challenge for the simultaneous mining of both information sources. For attributed graphs it is essential to be aware of such contradicting effects caused by irrelevant attributes and highly deviating attribute values of outlier nodes. In this work, we focus on the robustness of graph clustering w.r.t. irrelevant attributes and outliers. We propose a modularity-driven approach for parameter-free clustering of attributed graphs and several efficient algorithms for its computation. The efficiency is achieved by our incremental calculation of attribute information within these modularity-driven algorithms. In our experiments, we evaluate our modularity-driven algorithms w.r.t. the new challenges in attributed graphs and show that they outperform existing approaches on large attributed graphs.

To ease the proliferation of big data, it frequently is transformed, be it by compression, be it by anonymization. Such transformations however modify characteristics of the data, such as changes in the case of time series. Changes however are important for subsequent analyses. The impact of those modifications depends on the application scenario, and quantifying it is far from trivial. This is because a transformation can shift or modify existing changes or introduce new ones. In this paper, we propose MILTON, a flexible and robust Measure for quantifying the Impact of Lossy Transformations on subsequent change detectiON. MILTON is applicable to any lossy transformation technique on time-series data and to any general-purpose change-detection approach. We have evaluated it with three real-world use cases. Our evaluation shows that MILTON allows to quantify the impact of lossy transformations and to choose the best one from a class of transformation techniques for a given application scenario.

Mutual information is a well-established and broadly used concept in information theory. It allows to quantify the mutual dependence between two variables -- an essential task in data analysis. For static data, a broad range of techniques addresses the problem of estimating mutual information. However, the assumption of static data is not applicable for today's dynamic data sources such as data streams: In contrast to static approaches, an online estimator must be able to deal with the evolving, changing, and infinite nature of the stream. Furthermore, some tasks require the estimation to be available online while processing the raw data stream. Our proposed solution Mise (Mutual Information Stream Estimation) allows a user to issue mutual information queries in arbitrary time windows. As a key feature, we introduce a novel sampling scheme, which ensures an equal treatment of queries over multiple time scales, e.g., ranging from milliseconds up to decades. We thoroughly analyze the requirements of such a multiscale sampling scheme, and evaluate the resulting quality of Mise in a broad range of experiments.

In large databases, the amount and the complexity of the data calls for data summarization techniques. Such summaries are used to assist fast approximate query answering or query optimization. Histograms are a prominent class of model-free data summaries and are widely used in database systems. So-called self-tuning histograms look at query-execution results to refine themselves. An assumption with such histograms, which has not been questioned so far, is that they can learn the dataset from scratch, that is-starting with an empty bucket configuration. We show that this is not the case. Self-tuning methods are very sensitive to the initial configuration. Three major problems stem from this. Traditional self-tuning is unable to learn projections of multi-dimensional data, is sensitive to the order of queries, and reaches only local optima with high estimation errors. We show how to improve a self-tuning method significantly by starting with a carefully chosen initial configuration. We propose initialization by dense subspace clusters in projections of the data, which improves both accuracy and robustness of self-tuning. Our experiments on different datasets show that the error rate is typically halved compared to the uninitialized version.

In a database, besides known dependencies among columns (e.g., foreign key and primary key constraints), there are many other correlations unknown to the database users. Extraction of such hidden correlations is known to be useful for various tasks in database optimization and data analytics. However, the task is challenging due to the lack of measures to quantify column correlations. Correlations may exist among columns of different data types and value domains, which makes techniques based on value matching inapplicable. Besides, a column may have multiple semantics, which does not allow disjoint partitioning of columns. Finally, from a computational perspective, one has to consider a huge search space that grows exponentially with the number of columns.

Outlier ranking aims at the distinction between exceptional outliers and regular objects by measuring deviation of individual objects. In graphs with multiple numeric attributes, not all the attributes are relevant or show dependencies with the graph structure. Considering both graph structure and all given attributes, one cannot measure a clear deviation of objects. This is because the existence of irrelevant attributes clearly hinders the detection of outliers. Thus, one has to select local outlier contexts including only those attributes showing a high contrast between regular and deviating objects. It is an open challenge to detect meaningful local contexts for each node in attributed graphs.

In many real-world applications, data is collected in multi-dimensional spaces. However, not all dimensions are relevant for data analysis. Instead, interesting knowledge is hidden in correlated subsets of dimensions (i.e., subspaces of the original space). Detecting these correlated subspaces independent of the underlying mining task is an open research problem. It is challenging due to the exponential search space. Existing methods have tried to tackle this by utilizing Apriori search schemes. However, they show poor scalability and miss high quality subspaces. This paper features a scalable subspace search scheme (4S), which overcomes the efficiency problem by departing from the traditional levelwise search. We propose a new generalized notion of correlated subspaces which gives way to transforming the search space to a correlation graph of dimensions. Then we perform a direct mining of correlated subspaces in the graph. Finally, we merge subspaces based on the MDL principle and obtain high dimensional subspaces with minimal redundancy. We theoretically show that our search scheme is more general than existing search schemes and has a significantly lower runtime complexity. Our experiments reveal that 4S scales near-linearly with both database size and dimensionality, and produces higher quality subspaces than state-of-the-art methods.

There exists a variety of traditional outlier models, which measure the deviation of outliers with respect to the full attribute space. However, these techniques fail to detect outliers that deviate only w.r.t. an attribute subset. To address this problem, recent techniques focus on a selection of subspaces that allow: (1) A clear distinction between clustered objects and outliers; (2) a description of outlier reasons by the selected subspaces. However, depending on the outlier model used, different objects in different subspaces have the highest deviation. It is an open research issue to make subspace selection adaptive to the outlier score of each object and flexible w.r.t. the use of different outlier models.

Current mining algorithms for attributed graphs exploit dependencies between attribute information and edge structure, referred to as homophily. However, techniques fail if this assumption does not hold for the full attribute space. In multivariate spaces, some attributes have high dependency with the graph structure while others do not show any dependency. Hence, it is important to select congruent subspaces (i.e., subsets of the node attributes) showing dependencies with the graph structure. In this work, we propose a method for the statistical selection of such congruent subspaces. More specifically, we define a measure which assesses the degree of congruence between a set of attributes and the entire graph. We use it as the core of a statistical test, which congruent subspaces must pass. To illustrate its applicability to common graph mining tasks and in order to evaluate our selection scheme, we apply it to community outlier detection. Our selection of congruent subspaces enhances outlier detection by measuring outlier ness scores in selected subspaces only. Experiments on attributed graphs show that our approach outperforms traditional full space approaches and gives way to better outlier detection.

In many real world applications data is collected in multi-dimensional spaces, with the knowledge hidden in subspaces (i.e., subsets of the dimensions). It is an open research issue to select meaningful subspaces without any prior knowledge about such hidden patterns. Standard approaches, such as pairwise correlation measures, or statistical approaches based on entropy, do not solve this problem; due to their restrictive pairwise analysis and loss of information in discretization they are bound to miss subspaces with potential clusters and outliers. In this paper, we focus on finding subspaces with strong mutual dependency in the selected dimension set. Chosen subspaces should provide a high discrepancy between clusters and outliers and enhance detection of these patterns. To measure this, we propose a novel contrast score that quantifies mutual correlations in subspaces by considering their cumulative distributions—without having to discretize the data. In our experiments, we show that these high contrast subspaces provide enhanced quality in cluster and outlier detection for both synthetic and real world data.

Outlier mining is a major task in data analysis. Outliers are objects that highly deviate from regular objects in their local neighborhood. Density-based outlier ranking methods score each object based on its degree of deviation. In many applications, these ranking methods degenerate to random listings due to low contrast between outliers and regular objects. Outliers do not show up in the scattered full space, they are hidden in multiple high contrast subspace projections of the data. Measuring the contrast of such subspaces for outlier rankings is an open research challenge. In this work, we propose a novel subspace search method that selects high contrast subspaces for density-based outlier ranking. It is designed as pre-processing step to outlier ranking algorithms. It searches for high contrast subspaces with a significant amount of conditional dependence among the subspace dimensions. With our approach, we propose a first measure for the contrast of subspaces. Thus, we enhance the quality of traditional outlier rankings by computing outlier scores in high contrast projections only. The evaluation on real and synthetic data shows that our approach outperforms traditional dimensionality reduction techniques, naive random projections as well as state-of-the-art subspace search techniques and provides enhanced quality for outlier ranking.

Outlier mining is an important task for finding anomalous objects. In practice, however, there is not always a clear distinction between outliers and regular objects as objects have different roles w.r.t. different attribute sets. An object may deviate in one subspace, i.e. a subset of attributes. And the same object might appear perfectly regular in other subspaces. One can think of subspaces as multiple views on one database. Traditional methods consider only one view (the full attribute space). Thus, they miss complex outliers that are hidden in multiple subspaces. In this work, we propose Outrank, a novel outlier ranking concept. Outrank exploits subspace analysis to determine the degree of outlierness. It considers different subsets of the attributes as individual outlier properties. It compares clustered regions in arbitrary subspaces and derives an outlierness score for each object. Its principled integration of multiple views into an outlierness measure uncovers outliers that are not detectable in the full attribute space. Our experimental evaluation demonstrates that Outrank successfully determines a high quality outlier ranking, and outperforms state-of-the-art outlierness measures.

Social search is a variant of information retrieval where a document or website is considered relevant if individuals from the searcher's social network have interacted with it. Our ranking metric Social Relevance Score (SRS) is based on two factors. First, the engagement intensity quantifies the effort a user has made during an interaction. Second, users can assign a trust score to each person from their social network, which is then refined using social network analysis. We have tested our hypotheses with our search engine www.social-search.com, which extends the existing social bookmarking platform folkd.com. Our search engine integrates information the folkd.com users share through the popular social networks Twitter and Facebook. With permission of 2,385 testers, we have connected to their social graphs to generate a large-scale real-world dataset. Over the course of a two-month field study, 468,889 individuals have generated 24,854,281 website recommendations. We have used those links to enhance their search results while measuring the impact on the search behavior. We have found that social results are available for most queries and usually lead to more satisfying results.

The localisation of defects in computer programmes is essential in software engineering and is important in domain-specific data mining. Existing techniques which build on call-graph mining localise defects well, but do not scale for large software projects. This paper presents a hierarchical approach with good scalability characteristics. It makes use of novel call-graph representations, frequent subgraph mining and feature selection. It first analyses call graphs of a coarse granularity, before it zooms-in into more fine-grained graphs. We evaluate our approach with defects in the Mozilla Rhino project: In our setup, it narrows down the code a developer has to examine to about 6% only.

In open environments, deciding if an individual is trustworthy, based on his past behavior, is fundamentally important. To accomplish this, centrality in a so-called feedback graph is often used as a trust measure. The nodes of this graph represent the individuals, and an edge represents feedback that evaluates a past interaction. In the open environments envisioned where individuals can specify for themselves of how to derive their trust in others, we observe that several centrality computations take place at the same time. With centrality computation being an expensive operation, performance is an important issue. While techniques for the optimization of a single centrality computation exist, little attention so far has gone into the computation of several centrality measures in combination. In this paper, we investigate how to compute several centrality measures at the same time efficiently. We propose two new optimization techniques and demonstrate their usefulness experimentally both on synthetic and on real-world data sets.

The revenue of search-engine providers strongly depends on targeted advertisement. Targeted advertisement is becoming more reliant on personal data. This puts user privacy at risk. One way to improve privacy is to anonymize search logs, but this reduces usefulness for ad placement. Further, the usefulness depends on the target function used for the anonymization. This paper is the first to study this tradeoff systematically. We quantify the usefulness of an anonymized search log for advertisement purposes, by estimating outcomes such as the number of clicks on ads or the number of ad impressions possible after anonymization. A main result is that anonymized search logs are still useful for advertisement purposes, but the extent strongly depends on the target function.

We propose a method for predicting the cardinality distribution of a multi-dimensional query. Compared to conventional 'point-based' estimates, distribution-based estimates enable the query optimizer to predict the cost of a query plan more accurately, as we show experimentally. Our method is computationally efficient and works on top of a histogram already in place. It does not store any information additional to the histogram. Our experiments show that the quality of the predictions with the new method is high.

Estimating the approximate result size of a query before its execution based on small summary statistics is important for query optimization in database systems and for other facets of query processing. This also holds for queries over text databases. Research on selectivity estimation for such queries has focused on Boolean retrieval, i.e., a document may be relevant for the query or not. But with the coalescence of database and information retrieval (IR) technology, selectivity estimation for other, more sophisticated relevance functions is gaining importance as well. These models generate a query-specific distribution of the documents over the [0, 1]-interval. With document distributions, selectivity estimation means estimating how many documents are how similar to a given query. The problem is much more complex than selectivity estimation in the Boolean context: Beside document frequency, query results also depend on other characteristics such as term frequencies and document lengths. Selectivity estimation must take them into account as well. This paper proposes and evaluates a technique for estimating the result of retrieval queries with non-Boolean relevance functions. It estimates discretized document distributions over the range of the relevance function. Despite the complexity, compared to Boolean selectivity estimation, it requires little additional data, and the additional data can be stored in existing data structures with little extensions. Our evaluation demonstrates the effectiveness of our technique.

In retail, products are organized according to layout plans, so-called planograms. Compliance to planograms is important, since good product placement can significantly increase sales. Currently, retailers are about to implement RFID installations consisting of smart shelves and RFID-tagged items to support in-store logistics and processes. In principle, they can also use these installations to implement planogram compliance verification: Each antenna is supposed to detect all tagged items in one location of the planogram. But due to physical constraints, RFID tags can be identified by more than one RFID antenna. Thus, one cannot decide if an item carrying such a tag complies with the planogram. We propose a new method called RPCV which checks planogram compliance on large databases of items. It is based on the observation that the number of times an antenna identifies each item of a certain product type roughly follows a normal distribution. RPCV represents each item as a two-dimensional vector containing the number of readings both by the right antenna and by wrong ones according to the planogram. It clusters this data, separately for each product type. A cluster then is a set of correctly placed items or of misplaced ones. RPCV produces one order of magnitude less wrong predictions than current state of the art, and it requires less data to yield good predictions. A study with RFID-equipped goods and smart shelves shows that our approach is effective in realistic scenarios.

Research on Moving Object Databases (MOD) has resulted in sophisticated query mechanisms for moving objects and regions. Wireless Sensor Networks (WSN) support a wide range of applications that track or monitor moving objects. However, applying the concepts of MOD to WSN is difficult: While MOD tend to require precise object positions, the information acquired in WSN may be incomplete or inaccurate. This may be because of limited detection ranges, node failures or detection mechanisms that only determine if an object is in the vicinity of a node, but not its exact position. In this paper, we study the processing of spatiotemporal queries in WSN. First, we adapt the models used in MOD to WSN while keeping their semantical depth. Second, we propose two approaches for processing such queries in WSN in-network instead of collecting all data at the base station. Our experimental evaluations using simulation as well as a Sun SPOT deployment show that our measures reduce communication by up to 89%, compared to collecting all information at the base station.

While join processing in wireless sensor networks has received a lot of attention recently, current solutions do not work well for continuous queries. In those networks however, continuous queries are the rule. To minimize the communication costs of join processing, it is important to not ship non-joining tuples. In order to know which tuples do not join, prior work has proposed a precomputation step. For continuous queries however, repeating the precomputation for each execution is unnecessary and leaves aside that data tends to be temporally correlated. In this paper, we present a filtering approach for the processing of continuous join queries. We propose to keep the filters and to maintain them. The problems are determining the sizes of the filters and deciding which filters to update. Simplistic approaches result in bad performance. We show how to compute solutions that are optimal. Experiments on real-world sensor data indicate that our method performs close to a theoretical optimum and consistently outperforms state-of-the-art join approaches.

Social network analysis (SNA) has attracted a lot of attention over the past years. Existing tools for SNA do not allow a user-centric analysis of the social neighborhood, i.e., the subgraph of the user's friends and friends of a friend. In this paper, we introduce SONAR, an open source Web application for user-centric SNA. Its extensible architecture and flexible data model allows developers to embed SONAR directly into social networking websites. A performance evaluation shows that our application scales well with the number of users and adds only minimal overhead to the SNA algorithms.

Materialized views (MV) can significantly improve the query performance of relational databases. In this paper, we con-sider MVs to optimize complex scenarios where many het-erogeneous nodes with different resource constraints (e.g., CPU, IO and network bandwidth) query and update nu-merous tables on different nodes. Such problems are typical for large enterprises, e.g., global retailers storing thousands of relations on hundreds of nodes at different subsidiaries. Choosing which views to materialize in a distributed, com-plex scenario is NP-hard. Furthermore, the solution space is huge, and the large number of input factors results in non-monotonic cost models. This prohibits the straightfor-ward use of brute-force algorithms, greedy approaches or proposals from organic computing. For the same reason, all solutions for choosing MVs we are aware of do not consider either distributed settings or update costs. In this paper we describe an algorithmic framework which restricts the sets of considered MVs so that a genetic algo-rithm can be applied. In order to let the genetic algorithm converge quickly, we generate initial populations based on knowledge on database tuning, and devise a selection func-tion which restricts the solution space by taking the simi-larity of MV configurations into account. We evaluate our approach both with artificial settings and a real-world RFID scenario from retail. For a small setting consisting of 24 ta-bles distributed over 9 nodes, an exhaustive search needs 10 hours processing time. Our approach derives a compa-rable set of MVs within 30 seconds. Our approach scales well: Within 15 minutes it chooses a set of MVs for a real-world scenario consisting of 1,000 relations, 400 hosts, and a workload of 3,000 queries and updates. 1.

Join processing in wireless sensor networks is difficult: As the tuples can be arbitrarily distributed within the network, matching pairs of tuples is communication intensive and costly in terms of energy. Current solutions only work well with specific placements of the nodes and/or make restrictive assumptions. In this paper, we present SENS-Join, an efficient general-purpose join method for sensor networks. To obtain efficiency, SENS-Join does not ship tuples that do not join, based on a filtering step. Our main contribution is the design of this filtering step which is highly efficient in order not to exhaust the potential savings. We demonstrate the performance of SENS-Join experimentally: The overall energy consumption can be reduced by more than 80%, as compared to the state-of-the-art approach. The per node energy consumption of the most loaded nodes can be reduced by more than an order of magnitude.

Answering queries with a low selectivity in wireless sensor networks is a challenging problem. A simple tree-based data collection is communication-intensive and costly in terms of energy. Prior work has addressed the problem by approximating query results based on models of sensor readings. This cuts communication effort if the accuracy requirements are loose, e.g., if the temperature is required within ±0.5°C. For more accuracy, the models need frequent updates, and the communication costs quickly increase. In addition, sophisticated models incur substantial training costs. We propose a query-processing scheme that efficiently consolidates sensor data based on wavelet synopses. The difficulty is that the synopsis has to be constructed incrementally during data collection to ensure efficiency. Our core contribution is to show how to distribute the construction of wavelet synopses in sensor networks. In addition, our approach provides strict error guarantees. We evaluate our distributed wavelet compaction on real-world and on synthetic sensor data. Our solution reduces communication costs by more than a factor of five compared to state-of-the-art approaches. Further, our error guarantees for which efficient data consolidation is possible are better than theirs by more than an order of magnitude.

Creating and maintaining semantic structures such as ontologies on a large scale is a labor-intensive task, which a sole individual cannot perform. Established automated solutions for this task do not yet exist. Peer production is a promising approach to create structured knowledge: Members of an online community create and maintain semantic structures collaboratively. To motivate members to participate and to ensure the quality of the data, rating-based incentive mechanisms are promising. Members mutually rate the quality of their contributions and are rewarded for good contributions and truthful ratings. Until now, there has been no systematic evaluation of such rating mechanisms in the context of structured knowledge. We have developed a platform for the collaborative creation of semantic structures. To evaluate the effect of ratings and incentive mechanisms on the quality of peer-produced data, we have conducted an extensive empirical study in an online community. We show that ratings are a reliable measure of the quality of contributions by comparing user ratings with an ex post evaluation by experts. Further experimental results are that incentive mechanisms increase the quality of contributions. We conclude that ratings and incentive mechanisms are promising to foster and improve the peer production of structured knowledge.

With more and more natural language text stored in databases, handling respective query predicates becomes very important. Optimizing queries with predicates includes (sub)string estimation, i.e., estimating the selectivity of query terms based on small summary statistics before query execution. Count Suffix Trees (CST) are commonly used to this end. While CST yield good estimates, they are expensive to build and require a large amount of memory to be stored. To fit in the data dictionary of database systems, they have to be severely pruned. Existing pruning techniques are based on suffix frequency or tree depth. In this paper, we propose new filtering and pruning techniques that reduce both the size of CST over natural-language texts and the cost of building them. The core idea is to exploit features of the natural language data, i.e., regarding only the suffixes that are useful in a linguistic sense. The most important innovations are (a) a new aggressive approximate syllabification technique to filter out suffixes, (b) a new affix and prefix stripping procedure that conflates more terms than conventional stemming techniques, (c) the deployment of state-of-the-art trigram techniques and a new syllable-based mechanism to filter out non-words (i.e., misspellings and other language anomalies like foreign words), which would cause an over-proportional growth of the CST otherwise. -- Our evaluation with large English text corpora shows that our new mechanisms in combination decrease the size of a CST by up to 80% and shorten the build phase significantly. From a different perspective, if storage space remains unchanged, the accuracy of selectivity estimates computed from the CST increases by up to 70%.

Radio Frequency Identification (RFID) promises optimization of commodity flows in all industry segments. But due to physical constraints, RFID technology cannot detect all RFID tags from an assembly of items. This poses problems when integrating RFID data with enterprise-backend systems for tasks like inventory management or shelf replenishment. In this paper we propose the TagMark method to accomplish this integration. TagMark targets at a retailer scenario, where it estimates the number of tagged items from samples like the sales history or the tags read by smart shelves. The problem is challenging because most existing estimation methods depend on assumptions that do not hold in typical RFID applications, e.g., static item sets, simple random samples, or the availability of samples with user-defined sizes. TagMark adapts mark-recapture-methods in order to provide guarantees for the accuracy of the estimation and bounds for the sample sizes. It can be implemented as a database extension, allowing seamless integration into existing enterprise backend systems. A study with RFID-equipped goods acknowledges that our approach is effective in realistic scenarios, and database experiments with up to 1,000,000 items confirm that it can be efficiently implemented. Finally, we explore a broad range of extreme conditions that might stress TagMark, including a thief who knows the location of unread items.

Collaborative search engines (CSE) are an upcoming trend in WWW search. CSE let knowledge workers concert their efforts and support user collaboration. However, search terms and links clicked that are shared among users reveal their interests, habits, social relations and intentions. Thus, CSE might put the privacy of the users at risk. In this paper, we describe our first steps towards discovering the scope of privacy needs in CSE. We identify common components of CSE, and we describe typical use cases and user groups. Based on these information, we explore the range of privacy threats that might arise from query and link sharing. Furthermore, we outline a conceptual framework to explore the privacy needs of CSE users. Finally, we describe two findings from preliminary study results: First, our participants were less concerned about what providers might learn, but wanted to restrict information disclosed to people in their social network. Second, we have identified a new class of reciprocal privacy preferences, which allow or prohibit information disclose depending on the behavior of others.

We investigate how to ensure efficiency (in the economic sense of the word) in structured networks, with a focus on heterogeneity. A network is structured if the network designer has predefined some relationships between individuals (aka. nodes). Structured networks have turned out to be surprisingly efficient – at least as long as nodes face the same costs and benefits, i.e., are homogeneous [25]. However, the homogeneity assumption is unnatural and restrictive. Economic experiments in general (not with a focus on structured networks) suggest that heterogeneity is in the way of efficiency, i.e., reduces the sum of all payoffs. This is because individuals favor outcomes where everybody earns the same. This paper describes behavioral experiments that investigate this issue, i.e., the influence of heterogeneity on efficiency in structured networks. We show that most nodes in structured networks cooperate even if they earn less than others. Our explanation is that – with our design – competition enhances cooperation. This effect is rarely observed with other networks as well as in other, less specific settings where competition is in the way of cooperation. This result is an important step towards establishing networks that yield more tangible payoffs for its nodes.

This paper analyzes structured P2P systems where peers choose both their interaction mode, i.e., how they process incoming queries, and additional contacts in the network autonomously. Since additional contacts incur additional costs, a new kind of free riding behavior, namely having only few contacts, comes into the fray. We refer to it as deliberately poor connectedness (dpc). In this paper, we show that dpc is dominant in many situations. This leads to networks with a low degree of connectivity and a higher overall forwarding load than necessary. We then propose an incentive mechanism against dpc and demonstrate its effectiveness using a formal analysis and experiments.

A part of the biosystematics literature is currently being digitized and manually marked up with XML. Fast search on such documents shall be feasible. But marking up such documents incurs high costs, and biologists would like to know the value of such an activity in advance. Deploying standard XML database technology in a straightforward way is not feasible, because of two characteristics of biosystematics documents. The first one is that descriptions of taxa are related, i.e., a more specific taxon should inherit from a more general one. The combination of inheritance with information-retrieval mechanisms gives rise to difficulties addressed in this article. The second issue is the frequent occurrence of very specific technical terms in such documents, i.e., geographical information or biological terms. To investigate the characteristics of the search in the presence of such difficulties, we have designed and implemented a respective system, based on relational database technology. We use a collection of XML documents that mimics the characteristics of biosystematics documents, as we will explain. We propose two query-evaluation alternatives and compare them by means of performance experiments. It turns out that our techniques can administer the envisioned corpus of documents efficiently and cope with those problems at the same time.

A common approach to storage and retrieval of XML documents is to store them in a database, together with materialized views on their content. The advantage over "native" XML storage managers seems to be that transactions and concurrency are for free, next to other benefits. But a closer look and preliminary experiments reveal that this results in poor performance of concurrent queries and updates. The reason is that database lock contention hinders parallelism unnecessarily. We therefore investigate concurrency control at the semantic, i.e., XML level and describe a respective transaction manager XMLTM. It features a new locking protocol DGLOCK. It generalizes the protocol for locking on directed acyclic graphs by adding simple predicate locking on the content of elements, e.g., on their text. Instead of using the original XML documents, we propose to take advantage of an abstraction of the XML document collection known as DataGuides. XMLTM allows to run XML processing at the underlying database at low ANSI isolation degrees and to release database locks early without sacrificing correctness in this setting. We have built a complete prototype system that is implemented on top of the XML Extender for IBM DB2. Our evaluation shows that our approach consistently yields performance improvements by an order of magnitude. We stress that our approach can also be implemented within a native XML storage manager, and we expect even better performance.

Our current concern is a scalable infrastructure for information retrieval (IR) with up-to-date retrieval results in the presence of frequent, continuous updates. Timely processing of updates is important with novel application domains, e.g., e-commerce. We want to use off-the-self hardware and software as much as possible. These issues are challenging, given the additional requirement that the resulting system must scale well. We have built PowerDB-IR, a system that has the characteristics sought. This paper describes its design, implementation, and evaluation. PowerDB-IR is a coordination layer for a database cluster. The rationale behind a database cluster is to 'scale-out', i.e., to add further cluster nodes, whenever necessary for better performance. We build on IR-to-database mappings and service decomposition to support high-level parallelism. We follow a three-tier architecture with the database cluster as the bottom layer for storage management. The middle tier provides IR-specific processing and update services. PowerDB-IR has the following features: It allows to insert and retrieve documents concurrently, and it ensures freshness with almost no overhead. Alternative physical data organization schemes provide adequate performance for different workloads. Query processing techniques for the different data organizations efficiently integrate the ranked retrieval results from the cluster nodes. We have run extensive experiments with our prototype using commercial database systems and middleware software products. The main result is that PowerDB-IR shows surprisingly ideal scalability and low response times.

Evaluating similarity queries over image collections effectively and efficiently is an important but difficult issue. In many settings, a system does not deal with individual queries in isolation, there rather is a stream of queries. Researchers have proposed a number of query-evaluation alternatives and generalizations, in particular parallel methods over several components, and methods that yield approximate results. Choosing a plan for a given query is subject to more criteria than in conventional settings, notably result quality next to response time and resource consumption. We have designed and implemented a query planner that incorporates these concepts. We describe our space of possible plans and how we search this space. The usefulness of such a planner depends on a number of criteria, e.g., increase of throughput, adaptivity to different workloads, query planning overhead, or influence of the scoring function in quantitative terms. This article describes respective evaluations and shows that the benefit of our particular approach is significant.

Our concern is the design of a scalable infrastructure for complex application services. We want to find out if a cluster of commodity database systems is well-suited as such an infrastructure. To this end, we have carried out a feasibility study based on document services, e.g. document insertion and retrieval. We decompose a service request into short parallel database transactions. Our system, implemented as an extension of a transaction processing monitor, routes the short transactions to the appropriate database systems in the cluster. Routing depends on the data distribution that we have chosen. To avoid bottlenecks, we distribute document functionality, such as term extraction, over the cluster. Extensive experiments show the following. (1) A relatively small number of components - for example eight components $already suffices to cope with high workloads of more than 100 concurrently active clients. (2) Speedup and throughput increase linearly for insertion operations when increasing the cluster size. These observations also hold when bundling service invocations into transactions at the semantic layer. A specialized coordinator component then implements semantic serializability and atomicity. Our experiments show that such a coordinator has minimal impact on CPU resource consumption and on response times.

We investigate query routing techniques in a cluster of databases for a query-dominant environment. The objective is to decrease query response time. Each component of the cluster runs an off-the-shelf DBMS and holds a copy of the whole database. The cluster has a coordinator that routes each query to an appropriate component. Considering queries of realistic complexity, e.g., TPC-R, this article addresses the following questions: Can routing benefit from caching effects due to previous queries? Since our components are black-boxes, how can we approximate their cache content? How to route a query, given such cache approximations? To answer these questions, we have developed a cache-aware query router that is based on signature approximations of queries. We report on experimental evaluations with the TPC-R benchmark using our PowerDB database cluster prototype. Our main result is that our approach of cache approximation routing is better than state-of-the-art strategies by a factor of two with regard to mean response time.

The problem addressed in this paper is the execution of XML queries over a large collection of XML documents. This paper concentrates on how to develop the necessary infrastructure to effectively manipulate XML data and it proposes a data structure, named the XML Schema Directory (XSD), as an access means to XML repositories. The aim of XSD is to accelerate query processing by quickly finding the relevant set of XML documents for a given query. This is obtained by considering only a small number of relative XML schemata and consequently a limiting number of XML documents, rather than the entire corpus of XML documents. XML schema similarity is introduced as a way to determine the relevance among XML documents which belong to the same knowledge category. The proposed algorithms for maintaining the XSD structure do not require reorganisation and they may be efficiently used in practice. An alternative advantage of the XSD structure is that it may also be used as a method for facilitating browsing.

When relational database systems were introduced twenty years ago (1980), they were an infrastructure and main platform for application development. With today's information systems, the database system is a storage manager, far away from the applications. Our vision is that hyperdatabases become available that move up and extend database concepts to a higher level, closer to the applications. A hyperdatabase manages distributed objects and software components as well as workflows, in analogy to a database system that manages data and transactions. In short, hyperdatabases, also called "higher order databases", will provide "higher order data independence", e.g., immunity of applications against changes in the implementation of components and workload transparency. They will be the infrastructure for distributed information systems engineering of the future, and they are an abstraction from the host of current infrastructures and middleware technology. The article elaborates on this vision and outlines concrete projects at ETHZ such as PowerDB, a database cluster project. It shows how an efficient document engine can be built on top of a database cluster. A further project studies transactional process management as a layer on top of database transactions. Image similarity and multimedia components is another project where a hyperdatabase coordinates specialized components such as feature extraction and indexing services in a distributed environment.

The CORBA standard, together with its service specifications, has gained considerable attention in recent years. The CORBA Object Query Service allows for declarative access to heterogeneous storage systems. We have come up with an implementation of this service called Harmony. The objective of the article is to provide a detailed description and quantitative assessment of Harmony. Its main technical characteristics are data-flow evaluation, bulk transfer and intra-query parallelism. To carry out the evaluation, we have classified data exchange between components of applications in several dimensions: one is to distinguish between point-, context- and bulk data access. We have compared Harmony with: (1) data access through application-specific CORBA objects, and (2) conventional client/server communication, i.e., Embedded SQL. Our results show that Harmony performs much better than Alternative 1 for bulk data access. Besides that, due to the features mentioned above, Harmony, performs approximately as well as conventional client/server communication mechanisms.

In document management systems, it is desirable to provide content-based access to documents going beyond regular expression search in addition to access based on structural characteristics or associated attributes. We present a new approach for coupling OODBMSs (object-oriented database management systems) and IRSs (information retrieval systems) that provides enhanced flexibility and functionality as compared to coupling approaches reported from the literature. Our approach allows one to decide freely to which document collections, that are used as retrieval context, document objects belong, which text contents they provide for retrieval, and how they derive their associated retrieval values, either directly from the retrieval machine or from the values of related objects. Especially, we show how, in this approach, different strategies can be applied to hierarchically structured documents, possibly avoiding redundancy and IRS or OODBMS peculiarities. Content-based and structural queries can be freely combined within the OODBMS query language.

No abstract available.

LSIR

In this paper we discuss the structured multimedia documents that will be, or already are, to some degree the communication backbone of the so-called superhighways. It will be shown that storage and retrieval of such documents will best be handled by an integration of database and information retrieval technologies. We assume documents to be structured with the help of standards like SGML/HyTime and represented by the multitude of formats currently used for multimedia data.