Showing 1–44 of 44 results for author: Haas, J

PRDTs: Composable Knowledge-Based Consensus Protocols with Replicated Data Types

Authors: Julian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini

Abstract: Consensus protocols are fundamental in distributed systems as they enable software with strong consistency properties. However, designing optimized protocols for specific use-cases under certain system assumptions is typically a laborious and error-prone process requiring expert knowledge. While most recent optimized protocols are variations of well-known algorithms like Paxos or Raft, they often… ▽ More Consensus protocols are fundamental in distributed systems as they enable software with strong consistency properties. However, designing optimized protocols for specific use-cases under certain system assumptions is typically a laborious and error-prone process requiring expert knowledge. While most recent optimized protocols are variations of well-known algorithms like Paxos or Raft, they often necessitate complete re-implementations, potentially introducing new bugs and complicating the application of existing verification results. This approach stands in the way of application-specific consistency protocols that can easily be amended or swapped out, depending on the given application and deployment scenario. We propose Protocol Replicated Data Types (PRDTs), a novel programming model for implementing consensus protocols using replicated data types (RDTs). Inspired by the knowledge-based view of consensus, PRDTs employ RDTs to monotonically accumulate knowledge until agreement is reached. This approach allows for implementations focusing on high-level protocol logic with minimal network environment assumptions. Moreover, by applying existing algebraic composition techniques for RDTs in the PRDT context, we enable composable protocol building-blocks for implementing complex protocols. We present a formal model of our approach, demonstrate its application in PRDT-based implementations of existing protocols, and report empirical evaluation results. Our findings indicate that the PRDT approach offers enhanced flexibility and composability in protocol design, facilitates reasoning about correctness, and does not suffer from inherent performance limitations that would prevent its use in real-world applications. △ Less

Submitted 8 April, 2025; v1 submitted 7 April, 2025; originally announced April 2025.

Comments: 23 pages, 9 figures

An Agentic AI Workflow for Detecting Cognitive Concerns in Real-world Data

Authors: Jiazi Tian, Liqin Wang, Pedram Fard, Valdery Moura Junior, Deborah Blacker, Jennifer S. Haas, Chirag Patel, Shawn N. Murphy, Lidia M. V. R. Moura, Hossein Estiri

Abstract: Early identification of cognitive concerns is critical but often hindered by subtle symptom presentation. This study developed and validated a fully automated, multi-agent AI workflow using LLaMA 3 8B to identify cognitive concerns in 3,338 clinical notes from Mass General Brigham. The agentic workflow, leveraging task-specific agents that dynamically collaborate to extract meaningful insights fro… ▽ More Early identification of cognitive concerns is critical but often hindered by subtle symptom presentation. This study developed and validated a fully automated, multi-agent AI workflow using LLaMA 3 8B to identify cognitive concerns in 3,338 clinical notes from Mass General Brigham. The agentic workflow, leveraging task-specific agents that dynamically collaborate to extract meaningful insights from clinical notes, was compared to an expert-driven benchmark. Both workflows achieved high classification performance, with F1-scores of 0.90 and 0.91, respectively. The agentic workflow demonstrated improved specificity (1.00) and achieved prompt refinement in fewer iterations. Although both workflows showed reduced performance on validation data, the agentic workflow maintained perfect specificity. These findings highlight the potential of fully automated multi-agent AI workflows to achieve expert-level accuracy with greater efficiency, offering a scalable and cost-effective solution for detecting cognitive concerns in clinical settings. △ Less

Submitted 3 February, 2025; originally announced February 2025.

A theory of appropriateness with applications to generative artificial intelligence

Authors: Joel Z. Leibo, Alexander Sasha Vezhnevets, Manfred Diaz, John P. Agapiou, William A. Cunningham, Peter Sunehag, Julia Haas, Raphael Koster, Edgar A. Duéñez-Guzmán, William S. Isaac, Georgios Piliouras, Stanley M. Bileschi, Iyad Rahwan, Simon Osindero

Abstract: What is appropriateness? Humans navigate a multi-scale mosaic of interlocking notions of what is appropriate for different situations. We act one way with our friends, another with our family, and yet another in the office. Likewise for AI, appropriate behavior for a comedy-writing assistant is not the same as appropriate behavior for a customer-service representative. What determines which action… ▽ More What is appropriateness? Humans navigate a multi-scale mosaic of interlocking notions of what is appropriate for different situations. We act one way with our friends, another with our family, and yet another in the office. Likewise for AI, appropriate behavior for a comedy-writing assistant is not the same as appropriate behavior for a customer-service representative. What determines which actions are appropriate in which contexts? And what causes these standards to change over time? Since all judgments of AI appropriateness are ultimately made by humans, we need to understand how appropriateness guides human decision making in order to properly evaluate AI decision making and improve it. This paper presents a theory of appropriateness: how it functions in human society, how it may be implemented in the brain, and what it means for responsible deployment of generative AI technology. △ Less

Submitted 25 December, 2024; originally announced December 2024.

Comments: 115 pages, 2 figures

Stochastic SketchRefine: Scaling In-Database Decision-Making under Uncertainty to Millions of Tuples

Authors: Riddho R. Haque, Anh L. Mai, Matteo Brucato, Azza Abouzied, Peter J. Haas, Alexandra Meliou

Abstract: Decision making under uncertainty often requires choosing packages, or bags of tuples, that collectively optimize expected outcomes while limiting risks. Processing Stochastic Package Queries (SPQs) involves solving very large optimization problems on uncertain data. Monte Carlo methods create numerous scenarios, or sample realizations of the stochastic attributes of all the tuples, and generate p… ▽ More Decision making under uncertainty often requires choosing packages, or bags of tuples, that collectively optimize expected outcomes while limiting risks. Processing Stochastic Package Queries (SPQs) involves solving very large optimization problems on uncertain data. Monte Carlo methods create numerous scenarios, or sample realizations of the stochastic attributes of all the tuples, and generate packages with optimal objective values across these scenarios. The number of scenarios needed for accurate approximation - and hence the size of the optimization problem when using prior methods - increases with variance in the data, and the search space of the optimization problem increases exponentially with the number of tuples in the relation. Existing solvers take hours to process SPQs on large relations containing stochastic attributes with high variance. Besides enriching the SPaQL language to capture a broader class of risk specifications, we make two fundamental contributions towards scalable SPQ processing. First, to handle high variance, we propose risk-constraint linearization (RCL), which converts SPQs into Integer Linear Programs (ILPs) whose size is independent of the number of scenarios used. Solving these ILPs gives us feasible and near-optimal packages. Second, we propose Stochastic SketchRefine, a divide and conquer framework that breaks down a large stochastic optimization problem into subproblems involving smaller subsets of tuples. Our experiments show that, together, RCL and Stochastic SketchRefine produce high-quality packages in orders of magnitude lower runtime than the state of the art. △ Less

Submitted 1 April, 2025; v1 submitted 26 November, 2024; originally announced November 2024.

Ground-to-UAV and RIS-assisted UAV-to-Ground Communication Under Channel Aging: Statistical Characterization and Outage Performance

Authors: Thanh Luan Nguyen, Georges Kaddoum, Tri Nhu Do, Zygmunt J. Haas

Abstract: This paper studies the statistical characterization of ground-to-air (G2A) and reconfigurable intelligent surface (RIS)-assisted air-to-ground (A2G) communications in RIS-assisted UAV networks under the impact of channel aging. A comprehensive channel model is presented, which incorporates the time-varying fading, three-dimensional (3D) mobility, Doppler shifts, and the effects of channel aging on… ▽ More This paper studies the statistical characterization of ground-to-air (G2A) and reconfigurable intelligent surface (RIS)-assisted air-to-ground (A2G) communications in RIS-assisted UAV networks under the impact of channel aging. A comprehensive channel model is presented, which incorporates the time-varying fading, three-dimensional (3D) mobility, Doppler shifts, and the effects of channel aging on array antenna structures. We provide analytical expressions for the G2A signal-to-noise ratio (SNR) probability density function (PDF) and cumulative distribution function (CDF), demonstrating that the G2A SNR follows a mixture of noncentral $χ^2$ distributions. The A2G communication is characterized under RIS arbitrary phase-shift configurations, showing that the A2G SNR can be represented as the product of two correlated noncentral $χ^2$ random variables (RVs). Additionally, we present the PDF and the CDF of the product of two independently distributed noncentral $χ^2$ RVs, which accurately characterize the A2G SNR's distribution. Our paper confirms the effectiveness of RISs in mitigating channel aging effects within the coherence time. Finally, we propose an adaptive spectral efficiency method that ensures consistent system performance and satisfactory outage levels when the UAV and the ground user equipments are in motion. △ Less

Submitted 1 August, 2024; originally announced August 2024.

Distributed Locking as a Data Type

Authors: Julian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini

Abstract: Mixed-consistency programming models assist programmers in designing applications that provide high availability while still ensuring application-specific safety invariants. However, existing models often make specific system assumptions, such as building on a particular database system or having baked-in coordination strategies. This makes it difficult to apply these strategies in diverse setting… ▽ More Mixed-consistency programming models assist programmers in designing applications that provide high availability while still ensuring application-specific safety invariants. However, existing models often make specific system assumptions, such as building on a particular database system or having baked-in coordination strategies. This makes it difficult to apply these strategies in diverse settings, ranging from client/server to ad-hoc peer-to-peer networks. This work proposes a new strategy for building programmable coordination mechanisms based on the algebraic replicated data types (ARDTs) approach. ARDTs allow for simple and composable implementations of various protocols, while making minimal assumptions about the network environment. As a case study, two different locking protocols are presented, both implemented as ARDTs. In addition, we elaborate on our ongoing efforts to integrate the approach into the LoRe mixed-consistency programming language. △ Less

Submitted 24 May, 2024; originally announced May 2024.

Secure Link State Routing for Mobile Ad Hoc Networks

Authors: Panagiotis Papadimitratos, Zygmunt J. Haas

Abstract: The secure operation of the routing protocol is one of the major challenges to be met for the proliferation of the Mobile Ad hoc Networking (MANET) paradigm. Nevertheless, security enhancements have been proposed mostly for reactive MANET protocols. The proposed here Secure Link State Routing Protocol (SLSP) provides secure proactive topology discovery, which can be multiply beneficial to the netw… ▽ More The secure operation of the routing protocol is one of the major challenges to be met for the proliferation of the Mobile Ad hoc Networking (MANET) paradigm. Nevertheless, security enhancements have been proposed mostly for reactive MANET protocols. The proposed here Secure Link State Routing Protocol (SLSP) provides secure proactive topology discovery, which can be multiply beneficial to the network operation. SLSP can be employed as a stand-alone protocol, or fit naturally into a hybrid routing framework, when combined with a reactive protocol. SLSP is robust against individual attackers, it is capable of adjusting its scope between local and network-wide topology discovery, and it is capable of operating in networks of frequently changing topology and membership. △ Less

Submitted 28 March, 2024; originally announced March 2024.

Journal ref: IEEE International Symposium on Applications and the Internet - Workshop on Security and Assurance in Ad Hoc Networks, Orlando, FL, USA, January 2003

Secure Routing for Mobile Ad hoc Networks

Authors: Panagiotis Papadimitratos, Zygmunt J. Haas

Abstract: The emergence of the Mobile Ad Hoc Networking (MANET) technology advocates self-organized wireless interconnection of communication devices that would either extend or operate in concert with the wired networking infrastructure or, possibly, evolve to autonomous networks. In either case, the proliferation of MANET-based applications depends on a multitude of factors, with trustworthiness being one… ▽ More The emergence of the Mobile Ad Hoc Networking (MANET) technology advocates self-organized wireless interconnection of communication devices that would either extend or operate in concert with the wired networking infrastructure or, possibly, evolve to autonomous networks. In either case, the proliferation of MANET-based applications depends on a multitude of factors, with trustworthiness being one of the primary challenges to be met. Despite the existence of well-known security mechanisms, additional vulnerabilities and features pertinent to this new networking paradigm might render such traditional solutions inapplicable. In particular, the absence of a central authorization facility in an open and distributed communication environment is a major challenge, especially due to the need for cooperative network operation. In particular, in MANET, any node may compromise the routing protocol functionality by disrupting the route discovery process. In this paper, we present a route discovery protocol that mitigates the detrimental effects of such malicious behavior, as to provide correct connectivity information. Our protocol guarantees that fabricated, compromised, or replayed route replies would either be rejected or never reach back the querying node. Furthermore, the protocol responsiveness is safeguarded under different types of attacks that exploit the routing protocol itself. The sole requirement of the proposed scheme is the existence of a security association between the node initiating the query and the sought destination. Specifically, no assumption is made regarding the intermediate nodes, which may exhibit arbitrary and malicious behavior. The scheme is robust in the presence of a number of non-colluding nodes, and provides accurate routing information in a timely manner. △ Less

Submitted 1 March, 2024; originally announced March 2024.

Comments: arXiv admin note: text overlap with arXiv:1208.3486, arXiv:1303.7300 by other authors

Journal ref: SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS), San Antonio, TX, January 27-31, 2002

Statistical Characterization of RIS-assisted UAV Communications in Terrestrial and Non-Terrestrial Networks Under Channel Aging

Authors: Thanh Luan Nguyen, Georges Kaddoum, Tri Nhu Do, Zygmunt J. Haas

Abstract: This paper studies the statistical characterization of ground-to-air (G2A) and reconfigurable intelligent surface (RIS)-assisted air-to-ground (A2G) communications with unmanned aerial vehicles (UAVs) in terrestrial and non-terrestrial networks under the impact of channel aging. We first model the G2A and A2G signal-to-noise ratios (SNRs) as non-central complex Gaussian quadratic random variable… ▽ More This paper studies the statistical characterization of ground-to-air (G2A) and reconfigurable intelligent surface (RIS)-assisted air-to-ground (A2G) communications with unmanned aerial vehicles (UAVs) in terrestrial and non-terrestrial networks under the impact of channel aging. We first model the G2A and A2G signal-to-noise ratios (SNRs) as non-central complex Gaussian quadratic random variables (RVs) and derive their exact probability density functions, offering a unique characterization for the A2G SNR as the product of two scaled non-central chi-square RVs. Moreover, we also find that, for a large number of RIS elements, the RIS-assisted A2G channel can be characterized as a single Rician fading channel. Our results reveal the presence of channel hardening in A2G communication under low UAV speeds, where we derive the maximum target spectral efficiency (SE) for a system to maintain a consistent required outage level. Meanwhile, high UAV speeds, exceeding 50 m/s, lead to a significant performance degradation, which cannot be mitigated by increasing the number of RIS elements. △ Less

Submitted 30 January, 2024; v1 submitted 25 January, 2024; originally announced January 2024.

Comments: 6 pages, 3 figures and 7 subfigures, IEEE ICC'24 (Revision)

Uncertainty-aware Risk Assessment of Robotic Systems via Importance Sampling

Authors: Woo-Jeong Baek, Tom P. Huck, Joschka Haas, Jonas Lewandrowski, Tamim Asfour, Torsten Kröger

Abstract: In this paper, we introduce a probabilistic approach to risk assessment of robot systems by focusing on the impact of uncertainties. While various approaches to identifying systematic hazards (e.g., bugs, design flaws, etc.) can be found in current literature, little attention has been devoted to evaluating risks in robot systems in a probabilistic manner. Existing methods rely on discrete notions… ▽ More In this paper, we introduce a probabilistic approach to risk assessment of robot systems by focusing on the impact of uncertainties. While various approaches to identifying systematic hazards (e.g., bugs, design flaws, etc.) can be found in current literature, little attention has been devoted to evaluating risks in robot systems in a probabilistic manner. Existing methods rely on discrete notions for dangerous events and assume that the consequences of these can be described by simple logical operations. In this work, we consider measurement uncertainties as one main contributor to the evolvement of risks. Specifically, we study the impact of temporal and spatial uncertainties on the occurrence probability of dangerous failures, thereby deriving an approach for an uncertainty-aware risk assessment. Secondly, we introduce a method to improve the statistical significance of our results: While the rare occurrence of hazardous events makes it challenging to draw conclusions with reliable accuracy, we show that importance sampling -- a technique that successively generates samples in regions with sparse probability densities -- allows for overcoming this issue. We demonstrate the validity of our novel uncertainty-aware risk assessment method in three simulation scenarios from the domain of human-robot collaboration. Finally, we show how the results can be used to evaluate arbitrary safety limits of robot systems. △ Less

Submitted 27 August, 2023; originally announced August 2023.

Comments: This work has been submitted to the IEEE for possible publication

SupEuclid: Extremely Simple, High Quality OoD Detection with Supervised Contrastive Learning and Euclidean Distance

Authors: Jarrod Haas

Abstract: Out-of-Distribution (OoD) detection has developed substantially in the past few years, with available methods approaching, and in a few cases achieving, perfect data separation on standard benchmarks. These results generally involve large or complex models, pretraining, exposure to OoD examples or extra hyperparameter tuning. Remarkably, it is possible to achieve results that can exceed many of th… ▽ More Out-of-Distribution (OoD) detection has developed substantially in the past few years, with available methods approaching, and in a few cases achieving, perfect data separation on standard benchmarks. These results generally involve large or complex models, pretraining, exposure to OoD examples or extra hyperparameter tuning. Remarkably, it is possible to achieve results that can exceed many of these state-of-the-art methods with a very simple method. We demonstrate that ResNet18 trained with Supervised Contrastive Learning (SCL) produces state-of-the-art results out-of-the-box on near and far OoD detection benchmarks using only Euclidean distance as a scoring rule. This may obviate the need in some cases for more sophisticated methods or larger models, and at the very least provides a very strong, easy to use baseline for further experimentation and analysis. △ Less

Submitted 21 August, 2023; originally announced August 2023.

Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization

Authors: Anh L. Mai, Pengyu Wang, Azza Abouzied, Matteo Brucato, Peter J. Haas, Alexandra Meliou

Abstract: A package query returns a package - a multiset of tuples - that maximizes or minimizes a linear objective function subject to linear constraints, thereby enabling in-database decision support. Prior work has established the equivalence of package queries to Integer Linear Programs (ILPs) and developed the SketchRefine algorithm for package query processing. While this algorithm was an important fi… ▽ More A package query returns a package - a multiset of tuples - that maximizes or minimizes a linear objective function subject to linear constraints, thereby enabling in-database decision support. Prior work has established the equivalence of package queries to Integer Linear Programs (ILPs) and developed the SketchRefine algorithm for package query processing. While this algorithm was an important first step toward supporting prescriptive analytics scalably inside a relational database, it struggles when the data size grows beyond a few hundred million tuples or when the constraints become very tight. In this paper, we present Progressive Shading, a novel algorithm for processing package queries that can scale efficiently to billions of tuples and gracefully handle tight constraints. Progressive Shading solves a sequence of optimization problems over a hierarchy of relations, each resulting from an ever-finer partitioning of the original tuples into homogeneous groups until the original relation is obtained. This strategy avoids the premature discarding of high-quality tuples that can occur with SketchRefine. Our novel partitioning scheme, Dynamic Low Variance, can handle very large relations with multiple attributes and can dynamically adapt to both concentrated and spread-out sets of attribute values, provably outperforming traditional partitioning schemes such as KD-tree. We further optimize our system by replacing our off-the-shelf optimization software with customized ILP and LP solvers, called Dual Reducer and Parallel Dual Simplex respectively, that are highly accurate and orders of magnitude faster. △ Less

Submitted 14 November, 2023; v1 submitted 6 July, 2023; originally announced July 2023.

Exploring Simple, High Quality Out-of-Distribution Detection with L2 Normalization

Authors: Jarrod Haas, William Yolland, Bernhard Rabus

Abstract: We demonstrate that L2 normalization over feature space can produce capable performance for Out-of-Distribution (OoD) detection for some models and datasets. Although it does not demonstrate outright state-of-the-art performance, this method is notable for its extreme simplicity: it requires only two addition lines of code, and does not need specialized loss functions, image augmentations, outlier… ▽ More We demonstrate that L2 normalization over feature space can produce capable performance for Out-of-Distribution (OoD) detection for some models and datasets. Although it does not demonstrate outright state-of-the-art performance, this method is notable for its extreme simplicity: it requires only two addition lines of code, and does not need specialized loss functions, image augmentations, outlier exposure or extra parameter tuning. We also observe that training may be more efficient for some datasets and architectures. Notably, only 60 epochs with ResNet18 on CIFAR10 (or 100 epochs with ResNet50) can produce performance within two percentage points (AUROC) of several state-of-the-art methods for some near and far OoD datasets. We provide theoretical and empirical support for this method, and demonstrate viability across five architectures and three In-Distribution (ID) datasets. △ Less

Submitted 31 January, 2024; v1 submitted 6 June, 2023; originally announced June 2023.

Doing the right thing for the right reason: Evaluating artificial moral cognition by probing cost insensitivity

Authors: Yiran Mao, Madeline G. Reinecke, Markus Kunesch, Edgar A. Duéñez-Guzmán, Ramona Comanescu, Julia Haas, Joel Z. Leibo

Abstract: Is it possible to evaluate the moral cognition of complex artificial agents? In this work, we take a look at one aspect of morality: `doing the right thing for the right reasons.' We propose a behavior-based analysis of artificial moral cognition which could also be applied to humans to facilitate like-for-like comparison. Morally-motivated behavior should persist despite mounting cost; by measuri… ▽ More Is it possible to evaluate the moral cognition of complex artificial agents? In this work, we take a look at one aspect of morality: `doing the right thing for the right reasons.' We propose a behavior-based analysis of artificial moral cognition which could also be applied to humans to facilitate like-for-like comparison. Morally-motivated behavior should persist despite mounting cost; by measuring an agent's sensitivity to this cost, we gain deeper insight into underlying motivations. We apply this evaluation to a particular set of deep reinforcement learning agents, trained by memory-based meta-reinforcement learning. Our results indicate that agents trained with a reward function that includes other-regarding preferences perform helping behavior in a way that is less sensitive to increasing cost than agents trained with more self-interested preferences. △ Less

Submitted 29 May, 2023; originally announced May 2023.

Comments: 11 pages, 3 figures

LoRe: A Programming Model for Verifiably Safe Local-First Software

Authors: Julian Haas, Ragnar Mogk, Elena Yanakieva, Annette Bieniusa, Mira Mezini

Abstract: Local-first software manages and processes private data locally while still enabling collaboration between multiple parties connected via partially unreliable networks. Such software typically involves interactions with users and the execution environment (the outside world). The unpredictability of such interactions paired with their decentralized nature make reasoning about the correctness of lo… ▽ More Local-first software manages and processes private data locally while still enabling collaboration between multiple parties connected via partially unreliable networks. Such software typically involves interactions with users and the execution environment (the outside world). The unpredictability of such interactions paired with their decentralized nature make reasoning about the correctness of local-first software a challenging endeavor. Yet, existing solutions to develop local-first software do not provide support for automated safety guarantees and instead expect developers to reason about concurrent interactions in an environment with unreliable network conditions. We propose LoRe, a programming model and compiler that automatically verifies developer-supplied safety properties for local-first applications. LoRe combines the declarative data flow of reactive programming with static analysis and verification techniques to precisely determine concurrent interactions that violate safety invariants and to selectively employ strong consistency through coordination where required. We propose a formalized proof principle and demonstrate how to automate the process in a prototype implementation that outputs verified executable code. Our evaluation shows that LoRe simplifies the development of safe local-first software when compared to state-of-the-art approaches and that verification times are acceptable. △ Less

Submitted 19 October, 2023; v1 submitted 14 April, 2023; originally announced April 2023.

Comments: This is the extended version of the work accepted at ECOOP 2023

Journal ref: ACM Trans. Program. Lang. Syst. 46, 1, Article 2 (March 2024), 26 pages

What-if Analysis for Business Professionals: Current Practices and Future Opportunities

Authors: Sneha Gathani, Zhicheng Liu, Peter J. Haas, Çağatay Demiralp

Abstract: What-if analysis (WIA) is essential for data-driven decision-making, allowing users to assess how changes in variables impact outcomes and explore alternative scenarios. Existing WIA research primarily supports the workflows of data scientists and analysts, and largely overlooks business professionals who engage in WIA through non-technical means. To bridge this gap, we conduct a two-part user stu… ▽ More What-if analysis (WIA) is essential for data-driven decision-making, allowing users to assess how changes in variables impact outcomes and explore alternative scenarios. Existing WIA research primarily supports the workflows of data scientists and analysts, and largely overlooks business professionals who engage in WIA through non-technical means. To bridge this gap, we conduct a two-part user study with 22 business professionals across marketing, sales, product, and operations roles. The first study examines their existing WIA practices, tools, and challenges. Findings reveal that business professionals perform many WIA techniques independently using rudimentary tools due to various constraints. We then implement representative WIA techniques in a visual analytics prototype and use it as a probe to conduct a follow-up study evaluating business professionals' practical use of the techniques. Results show that these techniques improve decision-making efficiency and confidence while underscoring the need for better data preparation, risk assessment, and domain knowledge integration support. Finally, we offer design recommendations to enhance future business analytics systems. △ Less

Submitted 1 March, 2025; v1 submitted 27 December, 2022; originally announced December 2022.

Comments: CHI'2025

Melting Pot 2.0

Authors: John P. Agapiou, Alexander Sasha Vezhnevets, Edgar A. Duéñez-Guzmán, Jayd Matyas, Yiran Mao, Peter Sunehag, Raphael Köster, Udari Madhushani, Kavya Kopparapu, Ramona Comanescu, DJ Strouse, Michael B. Johanson, Sukhdeep Singh, Julia Haas, Igor Mordatch, Dean Mobbs, Joel Z. Leibo

Abstract: Multi-agent artificial intelligence research promises a path to develop intelligent technologies that are more human-like and more human-compatible than those produced by "solipsistic" approaches, which do not consider interactions between agents. Melting Pot is a research tool developed to facilitate work on multi-agent artificial intelligence, and provides an evaluation protocol that measures ge… ▽ More Multi-agent artificial intelligence research promises a path to develop intelligent technologies that are more human-like and more human-compatible than those produced by "solipsistic" approaches, which do not consider interactions between agents. Melting Pot is a research tool developed to facilitate work on multi-agent artificial intelligence, and provides an evaluation protocol that measures generalization to novel social partners in a set of canonical test scenarios. Each scenario pairs a physical environment (a "substrate") with a reference set of co-players (a "background population"), to create a social situation with substantial interdependence between the individuals involved. For instance, some scenarios were inspired by institutional-economics-based accounts of natural resource management and public-good-provision dilemmas. Others were inspired by considerations from evolutionary biology, game theory, and artificial life. Melting Pot aims to cover a maximally diverse set of interdependencies and incentives. It includes the commonly-studied extreme cases of perfectly-competitive (zero-sum) motivations and perfectly-cooperative (shared-reward) motivations, but does not stop with them. As in real-life, a clear majority of scenarios in Melting Pot have mixed incentives. They are neither purely competitive nor purely cooperative and thus demand successful agents be able to navigate the resulting ambiguity. Here we describe Melting Pot 2.0, which revises and expands on Melting Pot. We also introduce support for scenarios with asymmetric roles, and explain how to integrate them into the evaluation protocol. This report also contains: (1) details of all substrates and scenarios; (2) a complete description of all baseline algorithms and results. Our intention is for it to serve as a reference for researchers using Melting Pot 2.0. △ Less

Submitted 30 October, 2023; v1 submitted 24 November, 2022; originally announced November 2022.

Comments: 69 pages, 54 figures. arXiv admin note: text overlap with arXiv:2107.06857

Linking Neural Collapse and L2 Normalization with Improved Out-of-Distribution Detection in Deep Neural Networks

Authors: Jarrod Haas, William Yolland, Bernhard Rabus

Abstract: We propose a simple modification to standard ResNet architectures--L2 normalization over feature space--that substantially improves out-of-distribution (OoD) performance on the previously proposed Deep Deterministic Uncertainty (DDU) benchmark. We show that this change also induces early Neural Collapse (NC), an effect linked to better OoD performance. Our method achieves comparable or superior Oo… ▽ More We propose a simple modification to standard ResNet architectures--L2 normalization over feature space--that substantially improves out-of-distribution (OoD) performance on the previously proposed Deep Deterministic Uncertainty (DDU) benchmark. We show that this change also induces early Neural Collapse (NC), an effect linked to better OoD performance. Our method achieves comparable or superior OoD detection scores and classification accuracy in a small fraction of the training time of the benchmark. Additionally, it substantially improves worst case OoD performance over multiple, randomly initialized models. Though we do not suggest that NC is the sole mechanism or a comprehensive explanation for OoD behaviour in deep neural networks (DNN), we believe NC's simple mathematical and geometric structure can provide a framework for analysis of this complex phenomenon in future work. △ Less

Submitted 11 January, 2023; v1 submitted 17 September, 2022; originally announced September 2022.

Comments: 19 pages, accepted by Transactions of Machine Learning Research, 2022

Adaptive Decoding Mechanisms for UAV-enabled Double-Uplink Coordinated NOMA

Authors: Thanh Luan Nguyen, Georges Kaddoum, Tri Nhu Do, Daniel Benevides da Costa, Zygmunt J. Haas

Abstract: In this paper, we propose a novel adaptive decoding mechanism (ADM) for the unmanned aerial vehicle (UAV)-enabled uplink (UL) non-orthogonal multiple access (NOMA) communications. Specifically, considering a harsh UAV environment, where ground-to-ground links are regularly unavailable, the proposed ADM overcomes the challenging problem of conventional UL-NOMA systems whose performance is sensitive… ▽ More In this paper, we propose a novel adaptive decoding mechanism (ADM) for the unmanned aerial vehicle (UAV)-enabled uplink (UL) non-orthogonal multiple access (NOMA) communications. Specifically, considering a harsh UAV environment, where ground-to-ground links are regularly unavailable, the proposed ADM overcomes the challenging problem of conventional UL-NOMA systems whose performance is sensitive to the transmitter's statistical channel state information and the receiver's decoding order. To evaluate the performance of the ADM, we derive closed-form expressions for the system outage probability (OP) and system throughput. In the performance analysis section, we provide novel expressions for practical air-to-ground and ground-to-air channels, while taking into account the practical implementation of imperfect successive interference cancellation (SIC) in UL-NOMA. Moreover, the obtained expression can be adopted to characterize the OP of various systems under a Mixture of Gamma (MG) distribution-based fading channels. Next, we propose a sub-optimal Gradient Descent-based algorithm to obtain the power allocation coefficients that result in maximum throughput with respect to each location on UAV's trajectory. To determine the significance of the proposed ADM in nonstationary environments, we consider the ground users and the UAV to move according to the Random Waypoint Mobility (RWM) and Reference Point Group Mobility (RPGM) models, respectively. Accurate formulas for the distance distributions are also provided. Numerical solutions demonstrate that the ADM-enhanced NOMA not only outperforms Orthogonal Multiple Access (OMA), but also improves the performance of UAV-enabled UL-NOMA even in mobile environments. △ Less

Submitted 8 March, 2023; v1 submitted 27 June, 2022; originally announced June 2022.

Ethical and social risks of harm from Language Models

Authors: Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, Zac Kenton, Sasha Brown, Will Hawkins, Tom Stepleton, Courtney Biles, Abeba Birhane, Julia Haas, Laura Rimell, Lisa Anne Hendricks, William Isaac, Sean Legassick, Geoffrey Irving, Iason Gabriel

Abstract: This paper aims to help structure the risk landscape associated with large-scale Language Models (LMs). In order to foster advances in responsible innovation, an in-depth understanding of the potential risks posed by these models is needed. A wide range of established and anticipated risks are analysed in detail, drawing on multidisciplinary expertise and literature from computer science, linguist… ▽ More This paper aims to help structure the risk landscape associated with large-scale Language Models (LMs). In order to foster advances in responsible innovation, an in-depth understanding of the potential risks posed by these models is needed. A wide range of established and anticipated risks are analysed in detail, drawing on multidisciplinary expertise and literature from computer science, linguistics, and social sciences. We outline six specific risk areas: I. Discrimination, Exclusion and Toxicity, II. Information Hazards, III. Misinformation Harms, V. Malicious Uses, V. Human-Computer Interaction Harms, VI. Automation, Access, and Environmental Harms. The first area concerns the perpetuation of stereotypes, unfair discrimination, exclusionary norms, toxic language, and lower performance by social group for LMs. The second focuses on risks from private data leaks or LMs correctly inferring sensitive information. The third addresses risks arising from poor, false or misleading information including in sensitive domains, and knock-on risks such as the erosion of trust in shared information. The fourth considers risks from actors who try to use LMs to cause harm. The fifth focuses on risks specific to LLMs used to underpin conversational agents that interact with human users, including unsafe use, manipulation or deception. The sixth discusses the risk of environmental harm, job automation, and other challenges that may have a disparate effect on different social groups or communities. In total, we review 21 risks in-depth. We discuss the points of origin of different risks and point to potential mitigation approaches. Lastly, we discuss organisational responsibilities in implementing mitigations, and the role of collaboration and participation. We highlight directions for further research, particularly on expanding the toolkit for assessing and evaluating the outlined risks in LMs. △ Less

Submitted 8 December, 2021; originally announced December 2021.

Augmenting Decision Making via Interactive What-If Analysis

Authors: Sneha Gathani, Madelon Hulsebos, James Gale, Peter J. Haas, Çağatay Demiralp

Abstract: The fundamental goal of business data analysis is to improve business decisions using data. Business users often make decisions to achieve key performance indicators (KPIs) such as increasing customer retention or sales, or decreasing costs. To discover the relationship between data attributes hypothesized to be drivers and those corresponding to KPIs of interest, business users currently need to… ▽ More The fundamental goal of business data analysis is to improve business decisions using data. Business users often make decisions to achieve key performance indicators (KPIs) such as increasing customer retention or sales, or decreasing costs. To discover the relationship between data attributes hypothesized to be drivers and those corresponding to KPIs of interest, business users currently need to perform lengthy exploratory analyses. This involves considering multitudes of combinations and scenarios and performing slicing, dicing, and transformations on the data accordingly, e.g., analyzing customer retention across quarters of the year or suggesting optimal media channels across strata of customers. However, the increasing complexity of datasets combined with the cognitive limitations of humans makes it challenging to carry over multiple hypotheses, even for simple datasets. Therefore mentally performing such analyses is hard. Existing commercial tools either provide partial solutions or fail to cater to business users altogether. Here we argue for four functionalities to enable business users to interactively learn and reason about the relationships between sets of data attributes thereby facilitating data-driven decision making. We implement these functionalities in SystemD, an interactive visual data analysis system enabling business users to experiment with the data by asking what-if questions. We evaluate the system through three business use cases: marketing mix modeling, customer retention analysis, and deal closing analysis, and report on feedback from multiple business users. Users find the SystemD functionalities highly useful for quick testing and validation of their hypotheses around their KPIs of interest, addressing their unmet analysis needs. The feedback also suggests that the UX design can be enhanced to further improve the understandability of these functionalities. △ Less

Submitted 8 February, 2022; v1 submitted 13 September, 2021; originally announced September 2021.

Comments: CIDR'22

Aerial Reconfigurable Intelligent Surface-Aided Wireless Communication Systems

Authors: Tri Nhu Do, Georges Kaddoum, Thanh Luan Nguyen, Daniel Benevides da Costa, Zygmunt J. Haas

Abstract: In this paper, we propose and investigate an aerial reconfigurable intelligent surface (aerial-RIS)-aided wireless communication system. Specifically, considering practical composite fading channels, we characterize the air-to-ground (A2G) links by Namkagami-m small-scale fading and inverse-Gamma large-scale shadowing. To investigate the delay-limited performance of the proposed system, we derive… ▽ More In this paper, we propose and investigate an aerial reconfigurable intelligent surface (aerial-RIS)-aided wireless communication system. Specifically, considering practical composite fading channels, we characterize the air-to-ground (A2G) links by Namkagami-m small-scale fading and inverse-Gamma large-scale shadowing. To investigate the delay-limited performance of the proposed system, we derive a tight approximate closed-form expression for the end-to-end outage probability (OP). Next, considering a mobile environment, where performance analysis is intractable, we rely on machine learning-based performance prediction to evaluate the performance of the mobile aerial-RIS-aided system. Specifically, taking into account the three-dimensional (3D) spatial movement of the aerial-RIS, we build a deep neural network (DNN) to accurately predict the OP. We show that: (i) fading and shadowing conditions have strong impact on the OP, (ii) as the number of reflecting elements increases, aerial-RIS achieves higher energy efficiency (EE), and (iii) the aerial-RIS-aided system outperforms conventional relaying systems. △ Less

Submitted 9 June, 2021; originally announced June 2021.

Young Flattenings in the Schur module basis

Authors: Lennart J. Haas, Christian Ikenmeyer

Abstract: There are several isomorphic constructions for the irreducible polynomial representations of the general linear group in characteristic zero. The two most well-known versions are called Schur modules and Weyl modules. Steven Sam used a Weyl module implementation in 2009 for his Macaulay2 package PieriMaps. This implementation can be used to compute so-called Young flattenings of polynomials. Over… ▽ More There are several isomorphic constructions for the irreducible polynomial representations of the general linear group in characteristic zero. The two most well-known versions are called Schur modules and Weyl modules. Steven Sam used a Weyl module implementation in 2009 for his Macaulay2 package PieriMaps. This implementation can be used to compute so-called Young flattenings of polynomials. Over the Schur module basis Oeding and Farnsworth describe a simple combinatorial procedure that is supposed to give the Young flattening, but their construction is not equivariant. In this paper we clarify this issue, present the full details of the theory of Young flattenings in the Schur module basis, and give a software implementation in this basis. Using Reuven Hodges' recently discovered Young tableau straightening algorithm in the Schur module basis as a subroutine, our implementation outperforms Sam's PieriMaps implementation by several orders of magnitude on many examples, in particular for powers of linear forms, which is the case of highest interest for proving border Waring rank lower bounds. △ Less

Submitted 6 April, 2021; originally announced April 2021.

MSC Class: 05E10; 68Q17 ACM Class: I.1.2

Multi-RIS-aided Wireless Systems: Statistical Characterization and Performance Analysis

Authors: Tri Nhu Do, Georges Kaddoum, Thanh Luan Nguyen, Daniel Benevides da Costa, Zygmunt J. Haas

Abstract: In this paper, we study the statistical characterization and modeling of distributed multi-reconfigurable intelligent surface (RIS)-aided wireless systems. Specifically, we consider a practical system model where the RISs with different geometric sizes are distributively deployed, and wireless channels associated to different RISs are assumed to be independent but not identically distributed (i.n.… ▽ More In this paper, we study the statistical characterization and modeling of distributed multi-reconfigurable intelligent surface (RIS)-aided wireless systems. Specifically, we consider a practical system model where the RISs with different geometric sizes are distributively deployed, and wireless channels associated to different RISs are assumed to be independent but not identically distributed (i.n.i.d.). We propose two purpose-oriented multi-RIS-aided schemes, namely, the exhaustive RIS-aided (ERA) and opportunistic RIS-aided (ORA) schemes. A mathematical framework, which relies on the method of moments, is proposed to statistically characterize the end-to-end (e2e) channels of these schemes. It is shown that either a Gamma distribution or a Log-Normal distribution can be used to approximate the distribution of the magnitude of the e2e channel coefficients in both schemes. With these findings, we evaluate the performance of the two schemes in terms of outage probability (OP) and ergodic capacity (EC), where tight approximate closed-form expressions for the OP and EC are derived. Representative results show that the ERA scheme outperforms the ORA scheme in terms of OP and EC. In addition, under i.n.i.d. fading channels, the reflecting element settings and location settings of RISs have a significant impact on the system performance of both the ERA or ORA schemes. △ Less

Submitted 29 September, 2021; v1 submitted 5 April, 2021; originally announced April 2021.

Stochastic Package Queries in Probabilistic Databases

Authors: Matteo Brucato, Nishant Yadav, Azza Abouzied, Peter J. Haas, Alexandra Meliou

Abstract: We provide methods for in-database support of decision making under uncertainty. Many important decision problems correspond to selecting a package (bag of tuples in a relational database) that jointly satisfy a set of constraints while minimizing some overall cost function; in most real-world problems, the data is uncertain. We provide methods for specifying -- via a SQL extension -- and processi… ▽ More We provide methods for in-database support of decision making under uncertainty. Many important decision problems correspond to selecting a package (bag of tuples in a relational database) that jointly satisfy a set of constraints while minimizing some overall cost function; in most real-world problems, the data is uncertain. We provide methods for specifying -- via a SQL extension -- and processing stochastic package queries (SPQs), in order to solve optimization problems over uncertain data, right where the data resides. Prior work in stochastic programming uses Monte Carlo methods where the original stochastic optimization problem is approximated by a large deterministic optimization problem that incorporates many scenarios, i.e., sample realizations of the uncertain data values. For large database tables, however, a huge number of scenarios is required, leading to poor performance and, often, failure of the solver software. We therefore provide a novel SummarySearch algorithm that, instead of trying to solve a large deterministic problem, seamlessly approximates it via a sequence of smaller problems defined over carefully crafted summaries of the scenarios that accelerate convergence to a feasible and near-optimal solution. Experimental results on our prototype system show that SummarySearch can be orders of magnitude faster than prior methods at finding feasible and high-quality packages. △ Less

Submitted 11 March, 2021; originally announced March 2021.

Journal ref: SIGMOD 2020

Temporally-Biased Sampling Schemes for Online Model Management

Authors: Brian Hentschel, Peter J. Haas, Yuanyuan Tian

Abstract: To maintain the accuracy of supervised learning models in the presence of evolving data streams, we provide temporally-biased sampling schemes that weight recent data most heavily, with inclusion probabilities for a given data item decaying over time according to a specified "decay function". We then periodically retrain the models on the current sample. This approach speeds up the training proces… ▽ More To maintain the accuracy of supervised learning models in the presence of evolving data streams, we provide temporally-biased sampling schemes that weight recent data most heavily, with inclusion probabilities for a given data item decaying over time according to a specified "decay function". We then periodically retrain the models on the current sample. This approach speeds up the training process relative to training on all of the data. Moreover, time-biasing lets the models adapt to recent changes in the data while---unlike in a sliding-window approach---still keeping some old data to ensure robustness in the face of temporary fluctuations and periodicities in the data values. In addition, the sampling-based approach allows existing analytic algorithms for static data to be applied to dynamic streaming data essentially without change. We provide and analyze both a simple sampling scheme (T-TBS) that probabilistically maintains a target sample size and a novel reservoir-based scheme (R-TBS) that is the first to provide both control over the decay rate and a guaranteed upper bound on the sample size. If the decay function is exponential, then control over the decay rate is complete, and R-TBS maximizes both expected sample size and sample-size stability. For general decay functions, the actual item inclusion probabilities can be made arbitrarily close to the nominal probabilities, and we provide a scheme that allows a trade-off between sample footprint and sample-size stability. The R-TBS and T-TBS schemes are of independent interest, extending the known set of unequal-probability sampling schemes. We discuss distributed implementation strategies; experiments in Spark illuminate the performance and scalability of the algorithms, and show that our approach can increase machine learning robustness in the face of evolving data. △ Less

Submitted 11 June, 2019; originally announced June 2019.

Comments: 49 pages, 18 figures. arXiv admin note: substantial text overlap with arXiv:1801.09709

Interference Mitigation Using Dynamic Frequency Re-use for Dense Femtocell Network Architectures

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, Zygmunt J. Haas

Abstract: The next generation network aims to efficiently deploy low cost and low power cellular base station in the subscriber's home environment. For the femtocell deployment, frequency allocation among femtocells and macrocell is big concern to mitigate the interference, and to ensure the best use of the expensive spectrum. There are many sources of interference in integrated femtocell/macrocell networks… ▽ More The next generation network aims to efficiently deploy low cost and low power cellular base station in the subscriber's home environment. For the femtocell deployment, frequency allocation among femtocells and macrocell is big concern to mitigate the interference, and to ensure the best use of the expensive spectrum. There are many sources of interference in integrated femtocell/macrocell networks. Lagging in proper management of interference reduces the system capacity, increases the outage probability, and finally users feel bad quality of experience (QoE). The cost effective interference management technique depends on the size of femtocells deployment. In this paper, firstly we present deployable various possible femtocell network scenarios. We propose the dynamic frequency re-use scheme to mitigate interference for femtocell deployment. For highly dense femtocells, we propose the functionalities of self organizing network (SON) based femtocell network architecture. The outage probability of a femtocell user is analyzed in details. The performances of the proposed schemes for various femtocell deployments are performed using numerical analysis. △ Less

Submitted 4 October, 2018; originally announced October 2018.

Comments: International Conference on Ubiquitous and Future Networks (ICUFN), June 2010, Jeju, Korea, pp. 256-261

Unknown Examples & Machine Learning Model Generalization

Authors: Yeounoh Chung, Peter J. Haas, Eli Upfal, Tim Kraska

Abstract: Over the past decades, researchers and ML practitioners have come up with better and better ways to build, understand and improve the quality of ML models, but mostly under the key assumption that the training data is distributed identically to the testing data. In many real-world applications, however, some potential training examples are unknown to the modeler, due to sample selection bias or, m… ▽ More Over the past decades, researchers and ML practitioners have come up with better and better ways to build, understand and improve the quality of ML models, but mostly under the key assumption that the training data is distributed identically to the testing data. In many real-world applications, however, some potential training examples are unknown to the modeler, due to sample selection bias or, more generally, covariate shift, i.e., a distribution shift between the training and deployment stage. The resulting discrepancy between training and testing distributions leads to poor generalization performance of the ML model and hence biased predictions. We provide novel algorithms that estimate the number and properties of these unknown training examples---unknown unknowns. This information can then be used to correct the training set, prior to seeing any test data. The key idea is to combine species-estimation techniques with data-driven methods for estimating the feature values for the unknown unknowns. Experiments on a variety of ML models and datasets indicate that taking the unknown examples into account can yield a more robust ML model that generalizes better. △ Less

Submitted 11 October, 2019; v1 submitted 24 August, 2018; originally announced August 2018.

A Privacy Scheme for Monitoring Devices in the Internet of Things

Authors: Zygmunt J. Haas, Ashkan Yousefpour

Abstract: Sufficiently strong security and privacy mechanisms are prerequisite to amass the promising benefits of the IoT technology and to incorporate this technology into our daily lives. This paper introduces a novel approach to privacy in networks, an approach which is especially well matched with the IoT characteristics. Our general approach is based on continually changing the identifying attributes o… ▽ More Sufficiently strong security and privacy mechanisms are prerequisite to amass the promising benefits of the IoT technology and to incorporate this technology into our daily lives. This paper introduces a novel approach to privacy in networks, an approach which is especially well matched with the IoT characteristics. Our general approach is based on continually changing the identifying attributes of IoT nodes. In particular, the scheme proposed in this work is based on changing the IoT nodes' IP addresses, and because the changing patterns of the IP addresses appear random to a non-intended observer, an adversary is unable to identify the source or destination of a particular transmission. Thus, packets that carry information generated by a particular node cannot be linked together. The scheme offers additional security benefits, including DoS mitigation, is relatively easy to implement, and requires no changes to the existing networking infrastructure. We discuss the details of the implementation of the scheme and evaluate its performance. △ Less

Submitted 12 March, 2018; originally announced March 2018.

Comments: Appeared in the proceedings of FABULOUS 2016 (2nd EAI International Conference on Future Access Enablers of Ubiquitous and Intelligent Infrastructures)

Journal ref: In Pervasive Computing Paradigms for Mental Health, pp. 153-165. Springer, Cham, 2016

Temporally-Biased Sampling for Online Model Management

Authors: Brian Hentschel, Peter J. Haas, Yuanyuan Tian

Abstract: To maintain the accuracy of supervised learning models in the presence of evolving data streams, we provide temporally-biased sampling schemes that weight recent data most heavily, with inclusion probabilities for a given data item decaying exponentially over time. We then periodically retrain the models on the current sample. This approach speeds up the training process relative to training on al… ▽ More To maintain the accuracy of supervised learning models in the presence of evolving data streams, we provide temporally-biased sampling schemes that weight recent data most heavily, with inclusion probabilities for a given data item decaying exponentially over time. We then periodically retrain the models on the current sample. This approach speeds up the training process relative to training on all of the data. Moreover, time-biasing lets the models adapt to recent changes in the data while -- unlike in a sliding-window approach -- still keeping some old data to ensure robustness in the face of temporary fluctuations and periodicities in the data values. In addition, the sampling-based approach allows existing analytic algorithms for static data to be applied to dynamic streaming data essentially without change. We provide and analyze both a simple sampling scheme (T-TBS) that probabilistically maintains a target sample size and a novel reservoir-based scheme (R-TBS) that is the first to provide both complete control over the decay rate and a guaranteed upper bound on the sample size, while maximizing both expected sample size and sample-size stability. The latter scheme rests on the notion of a "fractional sample" and, unlike T-TBS, allows for data arrival rates that are unknown and time varying. R-TBS and T-TBS are of independent interest, extending the known set of unequal-probability sampling schemes. We discuss distributed implementation strategies; experiments in Spark illuminate the performance and scalability of the algorithms, and show that our approach can increase machine learning robustness in the face of evolving data. △ Less

Submitted 29 January, 2018; originally announced January 2018.

Comments: 17 pages, 14 figures, extended version of an EDBT'18 paper

Foresight: Rapid Data Exploration Through Guideposts

Authors: Çağatay Demiralp, Peter J. Haas, Srinivasan Parthasarathy, Tejaswini Pedapati

Abstract: Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a visualization recommender system that helps the user rapidly explore large high-dimensional datasets through "guideposts." A guidepost is a visualization corresponding to a pr… ▽ More Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a visualization recommender system that helps the user rapidly explore large high-dimensional datasets through "guideposts." A guidepost is a visualization corresponding to a pronounced instance of a statistical descriptor of the underlying data, such as a strong linear correlation between two attributes, high skewness or concentration about the mean of a single attribute, or a strong clustering of values. For each descriptor, Foresight initially presents visualizations of the "strongest" instances, based on an appropriate ranking metric. Given these initial guideposts, the user can then look at "nearby" guideposts by issuing "guidepost queries" containing constraints on metric type, metric strength, data attributes, and data values. Thus, the user can directly explore the network of guideposts, rather than the overwhelming space of data attributes and visual encodings. Foresight also provides for each descriptor a global visualization of ranking-metric values to both help orient the user and ensure a thorough exploration process. Foresight facilitates interactive exploration of large datasets using fast, approximate sketching to compute ranking metrics. We also contribute insights on EDA practices of data scientists, summarizing results from an interview study we conducted to inform the design of Foresight. △ Less

Submitted 29 September, 2017; originally announced September 2017.

Comments: IEEE VIS'17 Data Systems and Interactive Analysis (DSIA) Workshop

Foresight: Recommending Visual Insights

Authors: Çağatay Demiralp, Peter J. Haas, Srinivasan Parthasarathy, Tejaswini Pedapati

Abstract: Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a system that helps the user rapidly discover visual insights from large high-dimensional datasets. Formally, an "insight" is a strong manifestation of a statistical property of… ▽ More Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a system that helps the user rapidly discover visual insights from large high-dimensional datasets. Formally, an "insight" is a strong manifestation of a statistical property of the data, e.g., high correlation between two attributes, high skewness or concentration about the mean of a single attribute, a strong clustering of values, and so on. For each insight type, Foresight initially presents visualizations of the top k instances in the data, based on an appropriate ranking metric. The user can then look at "nearby" insights by issuing "insight queries" containing constraints on insight strengths and data attributes. Thus the user can directly explore the space of insights, rather than the space of data dimensions and visual encodings as in other visual recommender systems. Foresight also provides "global" views of insight space to help orient the user and ensure a thorough exploration process. Furthermore, Foresight facilitates interactive exploration of large datasets through fast, approximate sketching. △ Less

Submitted 12 July, 2017; originally announced July 2017.

A Self-Taught Artificial Agent for Multi-Physics Computational Model Personalization

Authors: Dominik Neumann, Tommaso Mansi, Lucian Itu, Bogdan Georgescu, Elham Kayvanpour, Farbod Sedaghat-Hamedani, Ali Amr, Jan Haas, Hugo Katus, Benjamin Meder, Stefan Steidl, Joachim Hornegger, Dorin Comaniciu

Abstract: Personalization is the process of fitting a model to patient data, a critical step towards application of multi-physics computational models in clinical practice. Designing robust personalization algorithms is often a tedious, time-consuming, model- and data-specific process. We propose to use artificial intelligence concepts to learn this task, inspired by how human experts manually perform it. T… ▽ More Personalization is the process of fitting a model to patient data, a critical step towards application of multi-physics computational models in clinical practice. Designing robust personalization algorithms is often a tedious, time-consuming, model- and data-specific process. We propose to use artificial intelligence concepts to learn this task, inspired by how human experts manually perform it. The problem is reformulated in terms of reinforcement learning. In an off-line phase, Vito, our self-taught artificial agent, learns a representative decision process model through exploration of the computational model: it learns how the model behaves under change of parameters. The agent then automatically learns an optimal strategy for on-line personalization. The algorithm is model-independent; applying it to a new model requires only adjusting few hyper-parameters of the agent and defining the observations to match. The full knowledge of the model itself is not required. Vito was tested in a synthetic scenario, showing that it could learn how to optimize cost functions generically. Then Vito was applied to the inverse problem of cardiac electrophysiology and the personalization of a whole-body circulation model. The obtained results suggested that Vito could achieve equivalent, if not better goodness of fit than standard methods, while being more robust (up to 11% higher success rates) and with faster (up to seven times) convergence rate. Our artificial intelligence approach could thus make personalization algorithms generalizable and self-adaptable to any patient and any model. △ Less

Submitted 1 May, 2016; originally announced May 2016.

Comments: Submitted to Medical Image Analysis, Elsevier

Deadline-aware Power Management in Data Centers

Authors: Cengis Hasan, Zygmunt J. Haas

Abstract: We study the dynamic power optimization problem in data centers. We formulate and solve the following offline problem: in which slot which server has to be assigned to which job; and in which slot which server has to be switched ON or OFF so that the total power is optimal for some time horizon. We show that the offline problem is a new version of generalized assignment problem including new const… ▽ More We study the dynamic power optimization problem in data centers. We formulate and solve the following offline problem: in which slot which server has to be assigned to which job; and in which slot which server has to be switched ON or OFF so that the total power is optimal for some time horizon. We show that the offline problem is a new version of generalized assignment problem including new constraints issuing from deadline characteristics of jobs and difference of activation energy of servers. We propose an online algorithm that solves the problem heuristically and compare it to randomized routing. △ Less

Submitted 13 July, 2015; originally announced July 2015.

Call Admission Control based on Adaptive Bandwidth Allocation for Multi-Class Services in Wireless Networks

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, andZygmunt J. Haas

Abstract: Due to the fact that Quality of Service (QoS) requirements are not as stringent for non-real-time traffic types, as opposed to real-time traffic, more calls can be accommodated by releasing some bandwidth from the existing non-real-time traffic calls. If the released bandwidth to accept a handover call is larger than to accept a new call, then the probability of dropping a call is smaller than the… ▽ More Due to the fact that Quality of Service (QoS) requirements are not as stringent for non-real-time traffic types, as opposed to real-time traffic, more calls can be accommodated by releasing some bandwidth from the existing non-real-time traffic calls. If the released bandwidth to accept a handover call is larger than to accept a new call, then the probability of dropping a call is smaller than the probability of blocking a call. In this paper we propose an efficient Call Admission Control (CAC) that relies on adaptive multi-level bandwidth-allocation scheme for non-real-time calls. The features of the scheme allow reduction of the call dropping probability along with the increase of the bandwidth utilization. The numerical results show that the proposed scheme is able to attain negligible handover call dropping probability without sacrificing bandwidth utilization. △ Less

Submitted 23 February, 2015; originally announced February 2015.

Comments: International Conference on ICT Convergence (ICTC), Nov. 2010, Jeju, Korea,pp. 358-361

Priority based Bandwidth Adaptation for Multi-class Traffic in Wireless Networks

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, Zygmunt J. Haas

Abstract: The bandwidth adaptation is the technique that allows the flexibility in bandwidth allocation for a call. Using the bandwidth adaptation technique, the number of call admission in the system can be increased significantly. In this paper we propose a priority based bandwidth adaptation scheme that can release multi-level of bandwidth from the existing calls to accept call requests. The amount of re… ▽ More The bandwidth adaptation is the technique that allows the flexibility in bandwidth allocation for a call. Using the bandwidth adaptation technique, the number of call admission in the system can be increased significantly. In this paper we propose a priority based bandwidth adaptation scheme that can release multi-level of bandwidth from the existing calls to accept call requests. The amount of released bandwidth is based on the number of existing bandwidth adaptive calls and the priority of requesting traffic call. This priority scheme does not reduce the bandwidth utilization. Moreover, the proposed bandwidth adaptation strategy provides significantly reduced call blocking probability for the higher priority traffic calls. The performance analyses show the improvement of the proposed scheme. △ Less

Submitted 14 December, 2014; originally announced December 2014.

Journal ref: International Journal of Multimedia and Ubiquitous Engineering, vol. 7, no. 2, pp. 445-450, April, 2012

Cost-Effective Frequency Planning for Capacity Enhancement of Femtocellular Networks

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, Zygmunt J. Haas

Abstract: Femtocellular networks will co-exist with macrocellular networks, mitigation of the interference between these two network types is a key challenge for successful integration of these two technologies. In particular, there are several interference mechanisms between the femtocellular and the macrocellular networks, and the effects of the resulting interference depend on the density of femtocells a… ▽ More Femtocellular networks will co-exist with macrocellular networks, mitigation of the interference between these two network types is a key challenge for successful integration of these two technologies. In particular, there are several interference mechanisms between the femtocellular and the macrocellular networks, and the effects of the resulting interference depend on the density of femtocells and the overlaid macrocells in a particular coverage area. While improper interference management can cause a significant reduction in the system capacity and can increase the outage probability, effective and efficient frequency allocation among femtocells and macrocells can result in a successful co-existence of these two technologies. Furthermore, highly dense femtocellular deployments the ultimate goal of the femtocellular technology will require significant degree of self-organization in lieu of manual configuration. In this paper, we present various femtocellular network deployment scenarios, and we propose a number of frequency-allocation schemes to mitigate the interference and to increases the spectral efficiency of the integrated network. These schemes include: shared frequency band, dedicated frequency band, sub-frequency band, static frequency-reuse, and dynamic frequency-reuse. △ Less

Submitted 11 December, 2014; originally announced December 2014.

Journal ref: Wireless Personal Communications, vol. 60, no. 1, pp. 83-104, Sept. 2011

Call Admission Control based on Adaptive Bandwidth Allocation for Wireless Networks

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, Zygmunt J. Haas

Abstract: Provisioning of Quality of Service (QoS) is a key issue in any multi-media system. However, in wireless systems, supporting QoS requirements of different traffic types is more challenging due to the need to minimize two performance metrics - the probability of dropping a handover call and the probability of blocking a new call. Since QoS requirements are not as stringent for non-real-time traffic… ▽ More Provisioning of Quality of Service (QoS) is a key issue in any multi-media system. However, in wireless systems, supporting QoS requirements of different traffic types is more challenging due to the need to minimize two performance metrics - the probability of dropping a handover call and the probability of blocking a new call. Since QoS requirements are not as stringent for non-real-time traffic types, as opposed to real-time traffic, more calls can be accommodated by releasing some bandwidth from the already admitted non-real-time traffic calls. If we require that such a released bandwidth to accept a handover call ought to be larger than the bandwidth to accept a new call, then the resulting probability of dropping a handover call will be smaller than the probability of blocking a new call. In this paper we propose an efficient Call Admission Control (CAC) that relies on adaptive multi-level bandwidth-allocation scheme for non-real-time calls. The scheme allows reduction of the call dropping probability along with increase of the bandwidth utilization. The numerical results show that the proposed scheme is capable of attaining negligible handover call dropping probability without sacrificing bandwidth utilization. △ Less

Submitted 11 December, 2014; originally announced December 2014.

Journal ref: IEEE/KICS Journal of Communications and Networks (JCN). vol. 15, no. 1, pp. 15-24, Feb. 2013

A Practical, Secure, and Verifiable Cloud Computing for Mobile Systems

Authors: Sriram N. Premnath, Zygmunt J. Haas

Abstract: Cloud computing systems, in which clients rent and share computing resources of third party platforms, have gained widespread use in recent years. Furthermore, cloud computing for mobile systems (i.e., systems in which the clients are mobile devices) have too been receiving considerable attention in technical literature. We propose a new method of delegating computations of resource-constrained mo… ▽ More Cloud computing systems, in which clients rent and share computing resources of third party platforms, have gained widespread use in recent years. Furthermore, cloud computing for mobile systems (i.e., systems in which the clients are mobile devices) have too been receiving considerable attention in technical literature. We propose a new method of delegating computations of resource-constrained mobile clients, in which multiple servers interact to construct an encrypted program known as garbled circuit. Next, using garbled inputs from a mobile client, another server executes this garbled circuit and returns the resulting garbled outputs. Our system assures privacy of the mobile client's data, even if the executing server chooses to collude with all but one of the other servers. We adapt the garbled circuit design of Beaver et al. and the secure multiparty computation protocol of Goldreich et al. for the purpose of building a secure cloud computing for mobile systems. Our method incorporates the novel use of the cryptographically secure pseudo random number generator of Blum et al. that enables the mobile client to efficiently retrieve the result of the computation, as well as to verify that the evaluator actually performed the computation. We analyze the server-side and client-side complexity of our system. Using real-world data, we evaluate our system for a privacy preserving search application that locates the nearest bank/ATM from the mobile client. We also measure the time taken to construct and evaluate the garbled circuit for varying number of servers, demonstrating the feasibility of our secure and verifiable cloud computing for mobile systems. △ Less

Submitted 6 October, 2014; originally announced October 2014.

Towards Optimal Broadcast in Wireless Networks

Authors: Zygmunt J. Haas, Milen Nikolov

Abstract: Broadcast is a fundamental operation in networks, especially in wireless Mobile Ad Hoc NETworks (MANET). For example, some form of broadcasting is used by all on-demand MANET routing protocols, when there is uncertainty as to the location of the destination node, or for service discovery. Being such a basic operation of the networking protocols, the importance of efficient broadcasting has long be… ▽ More Broadcast is a fundamental operation in networks, especially in wireless Mobile Ad Hoc NETworks (MANET). For example, some form of broadcasting is used by all on-demand MANET routing protocols, when there is uncertainty as to the location of the destination node, or for service discovery. Being such a basic operation of the networking protocols, the importance of efficient broadcasting has long been recognized by the networking community. Numerous papers proposed increasingly more efficient implementation of broadcasting, while other studies presented bounds on broadcast performance. In this work, we present a new approach to efficient broadcast in networks with dynamic topologies, such as MANET, and we introduce a new broadcasting algorithm for such networking environments. We evaluate our algorithm, showing that its performance comes remarkably close to the corresponding theoretical performance bounds, even in the presence of packet loss due to, for example, MAC-layer collisions. Furthermore, we compare the performance of the proposed algorithm with other recently proposed schemes, including in various mobility settings. △ Less

Submitted 29 January, 2013; originally announced January 2013.

Comments: 15 pages, 21 figures

ACM Class: C.2.1; C.2.2

Network evolution and QOS provisioning for integrated femtocell/macrocell networks

Authors: Mostafa Zaman Chowdhury, Yeong Min Jang, Zygmunt J. Haas

Abstract: Integrated femtocell/macrocell networks, comprising a conventional cellular network overlaid with femtocells, offer an economically appealing way to improve coverage, quality of service, and access network capacity. The key element to successful femtocells/macrocell integration lies in its self-organizing capability. Provisioning of quality of service is the main technical challenge of the femtoce… ▽ More Integrated femtocell/macrocell networks, comprising a conventional cellular network overlaid with femtocells, offer an economically appealing way to improve coverage, quality of service, and access network capacity. The key element to successful femtocells/macrocell integration lies in its self-organizing capability. Provisioning of quality of service is the main technical challenge of the femtocell/macrocell integrated networks, while the main administrative challenge is the choice of the proper evolutionary path from the existing macrocellular networks to the integrated network. In this article, we introduce three integrated network architectures which, while increasing the access capacity, they also reduce the deployment and operational costs. Then, we discuss a number of technical issues, which are key to making such integration a reality, and we offer possible approaches to their solution. These issues include efficient frequency and interference management, quality of service provisioning of the xDSL-based backhaul networks, and intelligent handover control. △ Less

Submitted 13 September, 2010; originally announced September 2010.

Comments: 16 pages, 10 figures, Published in International Journal of Wireless & Mobile Networks (IJWMN)

Journal ref: International Journal of Wireless & Mobile Networks (IJWMN), Vol.2, No.3, August 2010

How to Specify and How to Prove Correctness of Secure Routing Protocols for MANET

Authors: P. Papadimitratos, Z. J. Haas, J. -P. Hubaux

Abstract: Secure routing protocols for mobile ad hoc networks have been developed recently, yet, it has been unclear what are the properties they achieve, as a formal analysis of these protocols is mostly lacking. In this paper, we are concerned with this problem, how to specify and how to prove the correctness of a secure routing protocol. We provide a definition of what a protocol is expected to achieve… ▽ More Secure routing protocols for mobile ad hoc networks have been developed recently, yet, it has been unclear what are the properties they achieve, as a formal analysis of these protocols is mostly lacking. In this paper, we are concerned with this problem, how to specify and how to prove the correctness of a secure routing protocol. We provide a definition of what a protocol is expected to achieve independently of its functionality, as well as communication and adversary models. This way, we enable formal reasoning on the correctness of secure routing protocols. We demonstrate this by analyzing two protocols from the literature. △ Less

Submitted 30 December, 2009; originally announced December 2009.

Journal ref: IEEE-CS BroadNets 2006, San Jose, CA, USA, October 2006

Coverage and Connectivity in Three-Dimensional Networks

Authors: S. M. Nazrul Alam, Zygmunt J. Haas

Abstract: Most wireless terrestrial networks are designed based on the assumption that the nodes are deployed on a two-dimensional (2D) plane. However, this 2D assumption is not valid in underwater, atmospheric, or space communications. In fact, recent interest in underwater acoustic ad hoc and sensor networks hints at the need to understand how to design networks in 3D. Unfortunately, the design of 3D ne… ▽ More Most wireless terrestrial networks are designed based on the assumption that the nodes are deployed on a two-dimensional (2D) plane. However, this 2D assumption is not valid in underwater, atmospheric, or space communications. In fact, recent interest in underwater acoustic ad hoc and sensor networks hints at the need to understand how to design networks in 3D. Unfortunately, the design of 3D networks is surprisingly more difficult than the design of 2D networks. For example, proofs of Kelvin's conjecture and Kepler's conjecture required centuries of research to achieve breakthroughs, whereas their 2D counterparts are trivial to solve. In this paper, we consider the coverage and connectivity issues of 3D networks, where the goal is to find a node placement strategy with 100% sensing coverage of a 3D space, while minimizing the number of nodes required for surveillance. Our results indicate that the use of the Voronoi tessellation of 3D space to create truncated octahedral cells results in the best strategy. In this truncated octahedron placement strategy, the transmission range must be at least 1.7889 times the sensing range in order to maintain connectivity among nodes. If the transmission range is between 1.4142 and 1.7889 times the sensing range, then a hexagonal prism placement strategy or a rhombic dodecahedron placement strategy should be used. Although the required number of nodes in the hexagonal prism and the rhombic dodecahedron placement strategies is the same, this number is 43.25% higher than the number of nodes required by the truncated octahedron placement strategy. We verify by simulation that our placement strategies indeed guarantee ubiquitous coverage. We believe that our approach and our results presented in this paper could be used for extending the processes of 2D network design to 3D networks. △ Less

Submitted 12 September, 2006; originally announced September 2006.

Comments: To appear in ACM Mobicom 2006

ACM Class: C.2.1

Topology Control and Network Lifetime in Three-Dimensional Wireless Sensor Networks

Authors: S. M. Nazrul Alam, Zygmunt J. Haas

Abstract: Coverage and connectivity issues of three-dimensional (3D) networks are addressed in [2], but that work assumes that a node can be placed at any arbitrary location. In this work, we drop that assumption and rather assume that nodes are uniformly and densely deployed in a 3D space. We want to devise a mechanism that keeps some nodes active and puts other nodes into sleep so that the number of act… ▽ More Coverage and connectivity issues of three-dimensional (3D) networks are addressed in [2], but that work assumes that a node can be placed at any arbitrary location. In this work, we drop that assumption and rather assume that nodes are uniformly and densely deployed in a 3D space. We want to devise a mechanism that keeps some nodes active and puts other nodes into sleep so that the number of active nodes at a time is minimized (and thus network life time is maximized), while maintaining full coverage and connectivity. One simple way to do that is to partition the 3D space into cells, and only one node in each cell remains active at a time. Our results show that the number of active nodes can be minimized if the shape of each cell is a truncated octahedron. It requires the sensing range to be at least 0.542326 times the transmission radius. This value is 0.5, 0.53452 and 0.5 for cube, hexagonal prism, and rhombic dodecahedron, respectively. However, at a time the number of active nodes for cube, hexagonal prism and rhombic dodecahedron model is respectively 2.372239, 1.82615 and 1.49468 times of that of truncated octahedron model. So clearly truncated octahedron model has the highest network lifetime. We also provide a distributed topology control algorithm that can be used by each sensor node to determine its cell id using a constant number of local arithmetic operations provided that the sensor node knows its location. We also validate our results by simulation. △ Less

Submitted 10 September, 2006; originally announced September 2006.

Comments: Submitted for publication

ACM Class: C.2.1