Abstract This study examines how humans interact with large language models (LLMs) in real-world, unconstrained settings, focusing on potential shifts in users’ mental models. Initially, many users approach LLMs as traditional software tools, employing structured, machine-like prompts. However, after their first interaction, a notable shift occurs, such as increased politeness, more natural language phrasing, and shorter, more contextually nuanced prompts. That is, users increasingly adopt conversational behaviors typical of human-to-human communication and, in turn, this suggests a cognitive transition in the way users perceive and engage with AI systems. Analyzing over 200,000 conversations with computational linguistics methods, we find initial indications supporting this change. These insights have implications for AI design, trust, and ethical concerns, highlighting the need for further research beyond a mostly computational perspective to strengthen our findings on how users cognitively frame their interactions with AI.

Abstract We examine whether data generated by explanation techniques, which promote a process of self-reflection, can improve classifier performance. Our work is based on the idea that humans have the ability to make quick, intuitive decisions as well as to reflect on their own thinking and learn from explanations. To the best of our knowledge, this is the first time that the potential of mimicking this process by using explanations generated by explainability methods has been explored. We found that combining explanations with traditional labeled data leads to significant improvements in classification accuracy and training efficiency across multiple image classification datasets and convolutional neural network architectures. It is worth noting that during training, we not only used explanations for the correct or predicted class, but also for other classes. This serves multiple purposes, including allowing for reflection on potential outcomes and enriching the data through augmentation.

The amount of battery-powered Internet of Things (IoT) devices is strongly increasing. Predicting their battery health is important to maintain and proactively replace them to avoid outages. This article gives an overview of the existing literature using the IoT functionality to track and predict battery health. We elaborate on battery health concepts commonly found in the literature, i.e., State of Charge (SoC), State of Health (SoH), and remaining useful life (RuL). We provide definitions, use cases, and examples synthesized from a final selection of 23 reviewed papers. Important components are identified and assessed on how best to combine such components to build a state-of-the-art battery health tracking platform. The acquisition sensors send information about the battery to the IoT-connected controller for preprocessing. The aggregated data is then sent via wireless networking to a cloud-based monitoring platform, where it is stored in a database system. It can be visualized to the customer via a visualization interface.

Small devices, such as drills, are increasingly being equipped with Internet of Things (IoT) functions that make it possible to collect usage data, adapt the way they work, and also gain insights into the further development of the devices; even in application areas with limited battery capacity and noncontinuous Internet connection. Since the health of the battery is a crucial factor in the successful long-term deployment of these IoT devices, tracking their capacity-based State of Health (SoH-C) is important to avoid outages. To preserve energy, utilization data is aggregated and sent when an event occurs (e.g., charging). To avoid the need to introduce expensive intrinsic battery tracking sensors as done in large-scale IoT devices, this article uses the existing capacity tracking sensor of the battery management system (BMS) to track the SoH by applying the peak State-of-Charge (SoC) extraction technique. However, an SoH update can only be achieved and verified when the battery is peak cycled; which does not happen every charge/discharge cycle and also depends on the charging behavior of the customer. As long as the battery is shallow cycled, existing approaches would not update the SoH. To ensure continuous SoH tracking, the novel solution, presented in this article, called “battery health index” (BHI) combines physical capacity-based measurements with data-driven machine learning predictions based on utilization data to provide an always up-to-date SoH. The proposed state-of-the-art method is evaluated on a hand-held battery platform with millions of batteries and it outperforms existing solutions. The presented model enables proactive battery exchange by predicting the remaining useful lifetime (RUL) therefore increasing customer experience.

The application of recommendation technologies has been crucial in the promotion of physical and digital content across numerous global platforms such as Amazon, Apple, and Netflix. Our study aims to investigate the advantages of employing recommendation technologies on educational platforms, with a particular focus on an educational platform for learning and practicing music. Our research is based on data from Tomplay, a music platform that offers sheet music with professional audio recordings, enabling users to discover and practice music content at varying levels of difficulty. Through our analysis, we emphasize the distinct interaction patterns on educational platforms like Tomplay, which we compare with other commonly used recommendation datasets. We find that interactions are comparatively sparse on educational platforms, with users often focusing on specific content as they learn, rather than interacting with a broader range of material. Therefore, our primary goal is to address the issue of data sparsity. We achieve this through entity resolution principles and propose a neural network (NN)-based recommendation model. Further, we improve this model by utilizing graph neural networks (GNNs), which provide superior predictive accuracy compared to NNs. Notably, our study demonstrates that GNNs are highly effective even for users with little or no historical preferences (cold-start problem). Our cold-start experiments also provide valuable insights into an independent issue, namely, the number of historical interactions needed by a recommendation model to gain a comprehensive understanding of a user. Our findings demonstrate that a platform acquires a solid knowledge of a user’s general preferences and characteristics with 50 past interactions. Overall, our study makes significant contributions to information systems research on business analytics and prescriptive analytics. Moreover, our framework and evaluation results offer implications for various stakeholders, including online educational institutions, education policymakers, and learning platform users.

Machine Learning (ML) has become a valuable asset to solve many real-world tasks. For Network Intrusion Detection (NID), however, scientific advances in ML are still seen with skepticism by practitioners. This disconnection is due to the intrinsically limited scope of research papers, many of which primarily aim to demonstrate new methods "outperforming" prior work—oftentimes overlooking the practical implications for deploying the proposed solutions in real systems. Unfortunately, the value of ML for NID depends on a plethora of factors, such as hardware, that are often neglected in scientific literature.This paper aims to reduce the practitioners’ skepticism towards ML for NID by changing the evaluation methodology adopted in research. After elucidating which factors influence the operational deployment of ML in NID, we propose the notion of pragmatic assessment, which enable practitioners to gauge the real value of ML methods for NID. Then, we show that the state-of-research hardly allows one to estimate the value of ML for NID. As a constructive step forward, we carry out a pragmatic assessment. We re-assess existing ML methods for NID, focusing on the classification of malicious network traffic, and consider: hundreds of configuration settings; diverse adversarial scenarios; and four hardware platforms. Our large and reproducible evaluations enable estimating the quality of ML for NID. We also validate our claims through a user-study with security practitioners.

Adversarial samples mostly aim at fooling machine learning (ML) models. They often involve minor pixel-based perturbations that are imperceptible to human observers. In this work, adversarial samples should fool both humans and ML models, which is important in two-stage decision processes. We perform changes on a higher abstraction level so that a target sample exhibits properties of a desired sample. Technically, we contribute by deriving a regularization scheme for autoencoders incorporating a classifier loss for smoothly interpolating between wildly different samples. The realism and effectiveness of generated samples are confirmed with a user study and other evaluations. Our experiments consider neural networks of four architectures, assessed on MNIST, FashionMNIST, QuickDraw and CIFAR-10. Results show that our scheme leads to superior performance compared to existing interpolation techniques: on average, other methods have an 11% higher failure rate when producing a sample that is of any of two interpolated classes. Furthermore, our attacks work in both white- and black-box settings.

Artificial intelligence (AI) makes decisions impacting our daily lives in an increasingly autonomous manner. Their actions might cause accidents, harm, or, more generally, violate regulations. Determining whether an AI caused a specific event and, if so, what triggered the AI’s action, are key forensic questions. We provide a conceptualization of the problems and strategies for forensic investigation. We focus on AI that is potentially “malicious by design” and gray box analysis. Our evaluation using convolutional neural networks illustrates challenges and ideas for identifying malicious AI.

Abstract Interpreting a large number of neurons in deep learning is difficult. Our proposed ‘CLAssifier-DECoder’ architecture (ClaDec) facilitates the understanding of the output of an arbitrary layer of neurons or subsets thereof. It uses a decoder that transforms the incomprehensible representation of the given neurons to a representation that is more similar to the domain a human is familiar with. In an image recognition problem, one can recognize what information (or concepts) a layer maintains by contrasting reconstructed images of ClaDec with those of a conventional auto-encoder(AE) serving as reference. An extension of ClaDec allows trading comprehensibility and fidelity. We evaluate our approach for image classification using convolutional neural networks. We show that reconstructed visualizations using encodings from a classifier capture more relevant classification information than conventional AEs. This holds although AEs contain more information on the original input. Our user study highlights that even non-experts can identify a diverse set of concepts contained in images that are relevant (or irrelevant) for the classifier. We also compare against saliency based methods that focus on pixel relevance rather than concepts. We show that ClaDec tends to highlight more relevant input areas to classification though outcomes depend on classifier architecture. Code is at https://github.com/JohnTailor/ClaDec

Recommendation technologies have been playing an instrumental role for promoting both physical and digital content across several global platforms (Amazon, Apple, Netflix). Here we provide a study on the benefits of recommendation technologies in an educational platform with a focus on music learning. There are several characteristics present in this educational platform that make this recommendation problem particularly interesting, namely: a) the few but highly repetitive interactions, b) the existence of multiple versions of the same content across many difficulty levels, orchestrations, and musical instruments, and c) the user's expertise in a musical instrument which is essential for making appropriate recommendations. We highlight the unique dataset characteristics and compare them to those of other widely-used recommendation datasets. To alleviate the very high data sparsity due to the multi-instantiation of songs, we use entity resolution principles to embed songs in a new space. Using this lightweight entity resolution step on song data, in combination with neural recommendation architectures, we can double the predictive accuracy compared to techniques based on matrix factorization.

While the potential of deep learning(DL) for automating simple tasks is already well explored, recent research started investigating the use of deep learning for creative design, both for complete artifact creation and supporting humans in the creation process. In this paper, we use insights from computational creativity to conceptualize and assess current applications of generative deep learning in creative domains identified in a literature review. We highlight parallels between current systems and different models of human creativity as well as their shortcomings. While deep learning yields results of high value, such as high quality images, their novelity is typically limited due to multiple reasons such a being tied to a conceptual space defined by training data and humans. Current DL methods also do not allow for changes in the internal problem representation and they lack the capability to identify connections across highly different domains, both of which are seen as major drivers of human creativity.

Artificial intelligence (AI) comes with great opportunities but can also pose significant risks. Automatically generated explanations for decisions can increase transparency and foster trust, especially for systems based on automated predictions by AI models. However, given, e.g., economic incentives to create dishonest AI, to what extent can we trust explanations? To address this issue, our work investigates how AI models (i.e., deep learning, and existing instruments to increase transparency regarding AI decisions) can be used to create and detect deceptive explanations. As an empirical evaluation, we focus on text classification and alter the explanations generated by GradCAM, a well-established explanation technique in neural networks. Then, we evaluate the effect of deceptive explanations on users in an experiment with 200 participants. Our findings confirm that deceptive explanations can indeed fool humans. However, one can deploy machine learning (ML) methods to detect seemingly minor deception attempts with accuracy exceeding 80% given sufficient domain knowledge. Without domain knowledge, one can still infer inconsistencies in the explanations in an unsupervised manner, given basic knowledge of the predictive model under scrutiny.

The data distribution commonly evolves over time leading to problems such as concept drift that often decrease classifier performance. Current techniques are not adequate for this problem because they either require detailed knowledge of the transformation or are not suited for anticipating unseen domains but can only adapt to domains, where data samples are available. We seek to predict unseen data (and their labels) allowing us to tackle challenges s a non-constant data distribution in a proactive manner rather than detecting and reacting to already existing changes that might already have led to errors. To this end, we learn a domain transformer in an unsupervised manner that allows generating data of unseen domains. Our approach first matches independently learned latent representations of two given domains obtained from an auto-encoder using a Cycle-GAN. In turn, a transformation of the original samples can be learned that can be applied iteratively to extrapolate to unseen domains. Our evaluation of CNNs on image data confirms the usefulness of the approach. It also achieves very good results on the well-known problem of unsupervised domain adaption, where only labels but no samples have to be predicted. Code is available at https://github.com/JohnTailor/DoTra.

Visual realism in Virtual Reality (VR) increases both immersion and development costs. Consequently, it is important to understand the cost-benefit trade-off of specific aspects of visual realism. Determining the extent of visual realism often leads to decisions on the level of visual complexity of a Virtual Environment (VE). In this paper, we investigate the impact of visual complexity on a user's spatial orientation through a user study. To do so, we created a VE containing parts of a real-world place. Participants were asked to map their location within the VE to the corresponding real-world location. They were provided by a pop-up map of the entire VE, on which they were required to choose one named location out of a predefined set of locations. We manipulated the VE's visual complexity by varying the visual elements used to provide cartographic information, namely a map overlay and 3D blocks as buildings. This results in four scene types: i) landscape contour, ii) landscape contour with 3D buildings, iii) landscape contour overlaid with a map, and iv) landscape contour with both 3D buildings and the map overlay. Each participant performed our location recall task for each scene type. Our findings provide empirical evidence that addition of each of these two visual elements individually improved spatial orientation, while their combination only adds a slight improvement.

This work investigates questions related to learning features in convolutional neural networks (CNN). Empirical findings across multiple architectures such as VGG, ResNet, Inception and MobileNet indicate that weights near the center of a filter are larger than weights on the outside. Current regularization schemes violate this principle. Thus, we introduce Locality-promoting Regularization, which yields accuracy gains across multiple architectures and datasets. We also show theoretically that the empirical finding could be explained by maximizing feature cohesion under the assumption of spatial locality.

Humans increasingly interact with Artificial intelligence (AI) systems. AI systems are optimized for objectives such as minimum computation or minimum error rate in recognizing and interpreting inputs from humans. In contrast, inputs created by humans are often treated as a given. We investigate how inputs of humans can be altered to reduce misinterpretation by the AI system and to improve efficiency of input generation for the human while altered inputs should remain as similar as possible to the original inputs. These objectives result in trade-offs that are analyzed for a deep learning system classifying handwritten digits. To create examples that serve as demonstrations for humans to improve, we develop a model based on a conditional convolutional autoencoder (CCAE). Our quantitative and qualitative evaluation shows that in many occasions the generated proposals lead to lower error rates, require less effort to create and differ only modestly from the original samples.

Regulations to contain the spread of COVID-19 have affected corporations, institutions, and individuals to a degree that most people have never seen before. Information systems researchers have initiated a discourse on information technology’s role in helping people manage this situation. This study informs and substantiates this discourse based on an analysis of a rich dataset: Starting in March 2020, we collected about 3 million tweets that document people’s use of web-conferencing systems (WCS) like Zoom during the COVID-19 crisis. Applying text-mining techniques to Twitter data and drawing on affordance theory, we derive five affordances of and five constraints to the use of WCS during the crisis. Based on our analysis, our argument is that WCS emerged as a social technology that led to a new virtual togetherness by facilitating access to everyday activities and contacts that were “locked away” because of COVID-19-mitigation efforts. We find that WCS facilitated encounters that could not have taken place otherwise and that WCS use led to a unique blending of various aspects of people’s lives. Using our analysis, we derive implications and directions for future research to address existing constraints and realise the potentials of this period of forced digitalisation.

Neural systems offer high predictive accuracy but are plagued by long training times and low interpretability. We present a simple neural architecture for recommender systems that lifts several of these shortcomings. Firstly, the approach has a high predictive power that is comparable to state-of-the-art recommender approaches. Secondly, owing to its simplicity, the trained model can be interpreted easily because it provides the individual contribution of each input feature to the decision. Our method is three orders of magnitude faster than general-purpose explanatory approaches, such as LIME. Finally, thanks to its design, our architecture addresses cold-start issues, and therefore the model does not require retraining in the presence of new users.

Current topic models often suffer from discovering topics not matching human intuition, unnatural switching of topics within documents and high computational demands. We address these shortcomings by proposing a topic model and an inference algorithm based on automatically identifying characteristic keywords for topics. Keywords influence the topic assignments of nearby words. Our algorithm learns (key)word-topic scores and self-regulates the number of topics. The inference is simple and easily parallelizable. A qualitative analysis yields comparable results to those of state-of-the-art models, but with different strengths and weaknesses. Quantitative analysis using eight datasets shows gains regarding classification accuracy, PMI score, computational performance, and consistency of topic assignments within documents, while most often using fewer topics.

We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O (√ log Δ)+ 2 O (√log log n ) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(√/log n log log n , /log Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.

Numerous applications, e.g., in the industrial sector, produce large amounts of time-series data, which must be stored and made available for distributed processing. While outsourcing data storage and processing to third-party service providers offers many benefits, it raises data privacy issues. In light of this problem, techniques have been proposed to share only encrypted data with the remote service provider, yet the capability to run meaningful queries over the data is preserved. However, timeseries data is typically compressed at the server to save space, which is not easily possible when dealing with encrypted data. Moreover, data must be compressed in such a way that queries can still be executed efficiently. As a first step in this direction, we present an approach that preserves data privacy, enables compression at the server, and supports querying of the stored data. Our evaluation using realworld time-series data shows that our compression mechanism can reduce the required space drastically. Moreover, the median running time of all considered queries increases marginally, implying that compression can be introduced without sacrificing performance of query execution.

In this paper, we present a semi-automatic approach for mining a large-scale dataset of IDE interactions to extract usage smells, i.e., inefficient IDE usage patterns exhibited by developers in the field. The approach outlined in this paper first mines frequent IDE usage patterns, filtered via a set of thresholds and by the authors, that are subsequently supported (or disputed) using a developer survey, in order to form usage smells. In contrast with conventional mining of IDE usage data, our approach identifies time-ordered sequences of developer actions that are exhibited by many developers in the field. This pattern mining workflow is resilient to the ample noise present in IDE datasets due to the mix of actions and events that these datasets typically contain. We identify usage patterns and smells that contribute to the understanding of the usability of Visual Studio for debugging, code search, and active file navigation, and, more broadly, to the understanding of developer behavior during these software development activities. Among our findings is the discovery that developers are reluctant to use conditional breakpoints when debugging, due to perceived IDE performance problems as well as due to the lack of error checking in specifying the conditional.

Homomorphic encryption and secure multi-party computation enable computations on encrypted data. However, both techniques suffer from a large performance overhead. While advances in algorithms might reduce the overhead, we show that achieving perfect (or even computational) confidentiality is not possible without increasing the running time compared to computations on plaintext more than exponentially in some cases. In practice, however, perfect confidentiality is not always required. The paper discusses mechanisms to trade off confidentiality and performance for computing on ciphertexts. It introduces a fine-grained approach to define security levels for variables called (statistical) subdomain privacy. This concept differs substantially from prior work because it treats a variable as confidential or non-confidential depending on the actual value. We further propose privacy-preserving methods for memory access patterns. We apply our techniques to improve performance of control flow logic (loops, if-then-else logic) and arithmetic operations such as multiplications. The evaluation shows that the resulting speedup can be in the order of several magnitudes depending on the privacy needs.

The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O(√log log n) rounds with probability 1-1/n^Ω(1) in a graph with n nodes and maximum degree ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains ∆+1 colors.

Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O (log 2 Δ + 2 o (√log log n ) ) time, where Δ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log n ≪ Δ ≪ 2√log n , and comes close to the Ω(log Δ / log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O (log Δ + log 4 log n ) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal . —A (Δ + 1)-coloring algorithm requiring O (log Δ + 2 o (√log log n ) time, improving on an O (log Δ + √log n )-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O (√log n )-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O (log 2/3 n )-time MIS algorithm for graphs with arboricity up to 2 (log n )1/3 . Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n )-size graph.

Industrial control systems are an important part of critical infrastructures and their uninterrupted operation is important for many aspects of society. In recent years these systems have come under more scrutiny, as reports about attacks on them have become more frequent. There is therefore a need to better secure them, and the first step to achieve this is to identify the threat landscape for such systems. This is typically done by creating a threat model of a system, enumerating the potential threats, and then devising mitigation options based on the discovered threats. However, many of the available threat modeling methods and tools target very specific systems (e.g., software components), and do not lend themselves well to evaluating diverse systems or abstract reference architectures of systems. In this paper we present a methodology for system threat modeling that addresses this gap, by enabling the modeling of a diverse range of systems and reference architectures of systems. Furthermore, the methodology provides additional functionality, such as guiding the user in the completion of a threat model and automatically detecting unmitigated threats in a system. In addition, our methodology also takes mitigation into account by modeling the security components in a system. We have implemented the methodology in a web-based tool, and also evaluated the tool on a reference architecture of a complex automation system, validating both the approach and the tool.

The emergence of cloud-based storage services is opening up new avenues in data exchange and data dissemination. This has amplified the interest in right-protection mechanisms to establish ownership in the event of data leakage. Current right-protection technologies, however, rarely provide strong guarantees on dataset utility after the protection process. This work presents techniques that explicitly address this topic and provably preserve the outcome of certain mining operations. In particular, we take special care to guarantee that the outcome of hierarchical clustering operations remains the same before and after right protection. Our approach considers all prevalent hierarchical clustering variants: single-, complete-, and average-linkage. We imprint the ownership in a dataset using watermarking principles, and we derive tight bounds on the expansion/contraction of distances incurred by the process. We leverage our analysis to design fast algorithms for right protection without exhaustively searching the vast design space. Finally, because the right-protection process introduces a user-tunable distortion on the dataset, we explore the possibility of using this mechanism for data obfuscation. We quantify the tradeoff between obfuscation and utility for spatiotemporal datasets and discover very favorable characteristics of the process. An additional advantage is that when one is interested in both right-protecting and obfuscating the original data values, the proposed mechanism can accomplish both tasks simultaneously.

We present a new methodology for solving linear Support Vector Machines (SVMs) that capitalizes on multiple 1D projections. We show that the approach approximates the optimal solution with high accuracy and comes with analytical guarantees. Our solution adapts on methodologies from random projections, exponential search, and coordinate descent. In our experimental evaluation, we compare our approach with the popular liblinear SVM library. We demonstrate a significant speedup on various benchmarks. At the same time, the new methodology provides a comparable or better approximation factor of the optimal solution and exhibits smooth convergence properties. Our results are accompanied by bounds on the time complexity and accuracy.

Hierarchical clustering (HC) algorithms are generally limited to small data instances due to their runtime costs. Here we mitigate this shortcoming and explore fast HC algorithms based on random projections for single (SLC) and average (ALC) linkage clustering as well as for the minimum spanning tree problem (MST). We present a thorough adaptive analysis of our algorithms that improve prior work from O(N2) by up to a factor of N/(log N)2 for a dataset of N points in Euclidean space. The algorithms maintain, with arbitrary high probability, the outcome of hierarchical clustering as well as the worst-case running-time guarantees. We also present parameter-free instances of our algorithms.

Clustering offers significant insights in data analysis. Density based algorithms have emerged as flexible and efficient techniques, able to discover high-quality and potentially irregularly shaped- clusters. We present two fast density-based clustering algorithms based on random projections. Both algorithms demonstrate one to two orders of magnitude speedup compared to equivalent state-of-art density based techniques, even for modest-size datasets. We give a comprehensive analysis of both our algorithms and show runtime of O(dNlog2 N), for a d-dimensional dataset. Our first algorithm can be viewed as a fast variant of the OPTICS density-based algorithm, but using a softer definition of density combined with sampling. The second algorithm is parameter-less, and identifies areas separating clusters.

This paper attends to a generalized version of the classic page migration problem where migration costs are not necessarily given by the migration distance only, but may depend on prior migrations, or on the available bandwidth along the migration path. Interestingly, this problem cannot be viewed from a Metrical Task System (MTS) perspective, despite the generality of MTS: The corresponding MTS has an unbounded state space and, thus, an unbounded competitive ratio. Nevertheless, we are able to present an optimal online algorithm for a wide range of problem variants, improving the best upper bounds known so far for more specific problems. For example, we present a tight bound of Θ(log n/log log n) for the competitive ratio of the virtual server migration problem introduced recently.

The emergence of cloud-based storage services is opening up new avenues in data exchange and data dissemination. This has amplified the interest in right-protection mechanisms for establishing ownership in case of data leakage. Current right-protection technologies, however, rarely provide strong guarantees on the dataset utility after the protection process. This work presents techniques that explicitly address this shortcoming and provably preserve the outcome of certain mining operations. In particular, we take special care to guarantee that the outcome of hierarchical clustering operations remains the same before and after right protection. We encode data ownership using watermarking principles. In the process, we derive fundamental bounds on the distortion incurred by the watermarking. We leverage our theoretical analysis to design fast algorithms for right protection without exhaustively searching the vast design space.

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include 1) A randomized algorithm for computing a maximal matching (MM) in O(log Δ + (log log n)4) rounds, where Δ is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Δ in the range [(log log n)4, √log n]. 2) A randomized maximal independent set (MIS) algorithm requiring O(log Δ√log n) rounds, for all Δ, and only 2O(√log log n) rounds when Δ = poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon, Babai, and Itai when log Δ ≫ √log n. 3) A randomized (Δ + 1)-coloring algorithm requiring O(log Δ + 2O((√log log n)) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Δ + √log n) rounds. This result implies that an O(Δ)-coloring can be computed in 2O(√log log n)rounds for all Δ, improving on Kothapalli et al.'s O(√log n)-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any fixed minor) requiring O(√log n) and O(log2/3n) rounds w.h.p., respectively.

This paper presents a case study on the impact of development processes on the success of globally distributed software projects. The study compares agile (Scrum, XP, etc.) vs. structured (RUP, waterfall) processes to determine if the choice of process impacts: the overall success and economic savings of distributed projects; the importance customers attribute to projects; the motivation of the development teams; and the amount of real-time or asynchronous communication required during project development. The case study includes data from 66 projects developed in Europe, Asia, and the Americas. The results show no significant difference between the outcome of projects following agile processes and structured processes, suggesting that agile and structured processes can be equally effective for globally distributed development. The paper also discusses several qualitative aspects of distributed software development such as the advantages of near shore vs. offshore, the preferred communication patterns, and some common critical aspects.

We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time/color trade-off. To get a Δ+1 coloring takes time O(log Δ+ √ log n). To obtain an O(Δ+log1+1/log*nn) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Δlog(c) n+ log1+1/c n) colors, where c denotes an arbitrary constant and log(c ) n denotes the c times (recursively) applied logarithm ton.

We show how to partition data structures representable by directed acyclic graphs, i.e. rooted trees, to allow for efficient complex operations, which lie beyond inserts, deletes and finds. The approach potentially improves the performance of any operation modifying more than one element of the data structure. It covers common data structures implementable via linked lists or trees such as sets and maps. We demonstrate its simplicity and its effectiveness using a concurrent sorted linked list. We achieve a speedup of up to 250% even for small divisions.

We give a graph decomposition technique that creates entirely independent subproblems for graph problems such as coloring and dominating sets that can be solved without synchronization on a distributed memory system. For coloring, evaluation shows a performance gain of a factor 3 to 5 at the price of using more colors.

We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring algorithm needs with high probability O(Δ ∙ log n) time and uses O(Δ) colors, where n and Δ are the number of nodes in the network and the maximum degree, respectively; this algorithm requires knowledge of a linear bound on n and Δ. We improve this result in three ways: Firstly, we improve the time complexity, instead of the logarithmic factor we just need a polylogarithmic additive term; more specifically, our time complexity is O(Δ + log Δ ∙ log n) given an estimate of n and Δ, and O(Δ + log2 n) without knowledge of Δ. Secondly, our vertex coloring algorithm needs Δ + 1 colors only. Thirdly, our algorithm manages to do a distance-d coloring with asymptotically optimal O(Δ) colors for a constant d.

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our algorithm is asymptotically optimal. Our algorithm answers prominent open problems in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta+1 coloring in O(log* n) time, where delta is the maximum degree of the graph.