THIS SITE

Information for

2014 technical reports

CS-2014-01

Title Perspectives on Open Data: Issues and Opportunities
Authors Donald Cowan, Member, IEEE, Paulo Alencar, Member, IEEE, and Fred McGarry
Abstract

Open data like big data has become an important new direction in information technology. Governments are releasing
data so as to be more transparent and also claiming that open data has substantial economic value. However, there appear to be
many issues about open data that are not being discussed. This paper uses several practical examples in an attempt to illustrate
many of these issues and allied opportunities, and through them to suggest a partial research agenda around open data.

Date

January 27, 2014

Report

Perspectives on Open Data: Issues and Opportunities (PDF)

CS-2014-02

Title

Reachable Subwebs for Traversal-Based Query Execution

Authors

Olaf Hartig and M. Tamer Özsu

Abstract

Traversal-based approaches to execute queries over data on the Web have recently been studied. These approaches make use of up-to-date data from initially unknown data sources and, thus, enable applications to tap the full potential of the Web. While existing work focuses primarily on implementation techniques, a principled analysis of subwebs that are reachable by such approaches is missing. Such an analysis may help to gain new insight into the problem of optimizing the response time of traversal-based query engines. Furthermore, a better understanding of characteristics of such subwebs may also inform approaches to benchmark these engines.

This report provides such an analysis. In particular, we identify typical graph-based properties of query-specific reachable subwebs and quantify their diversity. Furthermore, we investigate whether vertex scoring methods (e.g., PageRank) are able to predict query-relevance of data sources when applied to such subwebs.

Date

February 4, 2014

Report

Reachable Subwebs for Traversal-Based Query Execution (PDF)

CS-2014-03

Title

A Multiagent Based Context-Aware and Self-Adaptive Model for Virtual Network Provisioning

Authors

Carolina Valadares, Donald Cowan, Carlos Lucena and Davy Baıa

Abstract

Recent research in network virtualization has focused on the Internet ossification problem [1] whereby multiple independent virtual networks (VN) [1] that exhibit a high degree of autonomy share physical resources and can provide services with varying degrees of quality. Thus, the Network field has taken evolutionary steps on re-thinking the design and architectural principles of VN [2] [3]. However, to the best of our knowledge, there has been little investigation into the autonomic behaviour of such architectures [4][5]. This paper describes an attempt to use Multiagent System (MAS) principles to design an autonomic and self-adaptive model for virtual network provisioning (VNP) that fills a gap in the current Internet architecture. In addition, we provide an analysis of the requirements of self-adaptive provisioning for designing a reliable autonomic model that is able to self-organize its own resources, with no external control, in order to cope with environment changes. Such behaviour will be required as the next generation Internet evolves. Through our evaluation, we demonstrate that the model achieves its main purpose of efficiently self-organizing the VN, since it is able to anticipate critical scenarios and trigger corresponding adaptive plans.

Date

February 28, 2014

Report

A Multiagent Based Context-Aware and Self-Adaptive Model for Virtual Network Provisioning (PDF)

CS-2014-04

Title

A MultiAgent-Based Simulation Model to Support Management Decision Making in Software Development

Authors

Davy Baia, Carlos J. P. Lucena, Donald Cowan, Pierre Bommel,
Carolina Valadares and Toacy Oliveira

Abstract

Context: Techniques to support the development of software projects and describe the quality of the results have received substantial attention from the research community because software projects often do not achieve their intended results in terms of factors such as time to completion and quality of the final product. Objective: In this paper, we propose a MultiAgent-Based Simulation Model to support project managers in the decision-making process that is required in the creation of software systems. This model is based on the Project Management Body of Knowledge (PMBOK) in areas such as cost, time, scope and human resources.  Method: We present an illustrative example that was drawn from our experience with real-world software development projects conducted within our research group. Such an example demonstrates the benefits and drawbacks of using MultiAgent System simulation as a support tool for the project manager’s decision-making process.  Results: We have created a simulation model and associated scenarios that allow a project manager to analyze strategic options throughout the project. Each option is based on the PMBOK practices allowing project managers to investigate the best scenario that meets the project needs such as cost, time and quality. Conclusions: Some factors are crucial to the success or failure of a project.Decisions made by the project manager are one such set of factors that determine if the project goals are achievable. Through using MABS to simulate scenarios we have become convinced that this approach can contribute to the understanding of the phenomena that occur during a software development project and provide real assistance to the project manager.

Date

March 06, 2014

Report

A MultiAgent-Based Simulation Model to Support Management Decision Making in Software Development (PDF)

CS-2014-05

Title

Reducing CTL-live Model Checking to Semantic Entailment in First-Order Logic (Version 1)

Authors

Amirhossein Vakili, Nancy A. Day

Abstract

The core of temporal logic model checking is the reachability problem, which is not expressible in first-order logic (FOL). Most model checking algorithms, both for finite and infinite Kripke structures, contain a loop that iterates to reach a fixed-point. As a result, reasoners with input languages no more expressive than FOL have been used iteratively for model checking rather than having the reasoner solve the problem completely by itself. In this article, we present a method for reducing model checking of finite and infinite Kripke structures that are expressed in FOL to entailment checking in FOL for a fragment of computational tree logic (CTL), which we call CTL-live. CTL-live includes all the CTL  connectives that are expressible in the mu-calculus using the least fixed-point operator. These connectives are traditionally used to express liveness properties. This reduction allows us to consider model checking of CTL-live as a FOL theorem proving problem, and to use directly FOL reasoning techniques for model checking without the need of fixed-point operators, transitive-closure, or induction. We prove that CTL-live is maximal in the sense that model checking of CTL connectives that are not included in CTL-live is not reducible to semantic entailment in FOL.
 

Date

March 20, 2014

Report

Reducing CTL-live Model Checking to Semantic Entailment in First-Order Logic (Version 1) (PDF)

CS-2014-06

Title

A Risk Management Approach for Distributed Event-Based Systems

Authors

Sergey Savinov and Paulo Alencar

Abstract In this paper we present a Risk Management System. The goal of the RMS is to decrease risks related to information access. The goal is met by taking the context of operations into account; providing motivation to users through incentives (e.g., punishments or rewards); providing support to track changes and ability to reason about risk-related attributes; providing support to reason about tasks, plans and goals; providing process-based system guidance; decreasing the costs per operation for growing systems by making human intervention optional.
Date

April 21, 2014

Report

A Risk Management Approach for Distributed Event-Based Systems (PDF)

CS-2014-07

Title

3-D Reconstruction from Few Projections: Structural Assumptions for Graceful DegradationPerspectives on Open Data: Issues and Opportunties

Authors

Michael Cormier, Daniel J. Lizotte, and Richard Mann

Abstract

We present a spatial-domain method for the reconstruction of a three-dimensional density distribution from one or more projections (images formed by integration of density along lines of sight) and using the three-dimensional reconstruction to explain features of the two-dimensional images. The advantages of our proposed method are that it degrades gracefully down to a single image, that it uses linear equations and constraints (allowing the use of convex optimization), that it is amenable to three-dimensional structural biases, and that ambiguity can be expressed precisely (it is possible to “know what we don’t know”). Previously described methods have some, but not all, of these properties.

Date

May 7, 2014

Report

3-D Reconstruction from Few Projections: Structural Assumptions for Graceful DegradationPerspectives on Open Data: Issues and Opportunties (PDF)

CS-2014-08

Title

Digital Marbling a GPU Approach with Precomputer Velocity Field

Authors

Si Wen

Abstract

Paper marbling is the art of creating intricate designs on an aqueous surface. I present an interactive digital marbling system by simulating fluid dynamics on the GPU using precomputed solutions to the Navier-Stokes equations. Experimental results have shown that my approach significantly improved the performance of the marbling simulation, while maintaining the quality of generated artworks.

Date

May 7, 2014

Report

Digital Marbling a GPU Approach with Precomputer Velocity Field (PDF)

CS-2014-09

Title

Constructing Call Graphs of Scala Programs

Authors

Karim Ali, Marianna Rapoport, Ondrej Lhotak, Julian Dolby, and Frank Tip

Abstract

As Scala gains popularity, there is growing interest in programming tools for it. Such tools often require call graphs. However, call graph construction algorithms in the literature do not handle Scala features, such as traits and abstract type members. Applying existing call graph construction algorithms to the JVM bytecodes generated by the Scala compiler produces very imprecise results due to type information being lost during compilation. We adapt existing call graph construction algorithms, Name-Based Resolution (RA) and Rapid Type Analysis (RTA), for Scala, and present a formalization based on Featherweight Scala. We evaluate our algorithms on a collection of Scala programs. Our results show that careful handling of complex Scala constructs greatly helps precision and that our most precise analysis generates call graphs with 1.1-3.7 times fewer nodes and .5-18.7 times fewer edges than a bytecode-based RTA analysis.
 

Date

May 14, 2014

Report

Constructing Call Graphs of Scala Programs (PDF)

CS-2014-10

Title

Verifying CTL-live Properties of Infinite State Models using an SMT solver (Version 1)

Authors

Amirhossein Vakili and Nancy A. Day

Abstract

The ability to create and analyze abstract models is an important step in conquering software complexity. In this paper, we show that it is practical to verify dynamic properties of infinite state models expressed in a subset of CTL directly using an SMT solver without iteration, abstraction, or human intervention. We call this subset CTLlive and it consists of the operators of CTL expressible using the least fixed point operator of the mu-calculus, which are commonly considered liveness properties (e.g., AF, EU). We show that using this method the verification of an infinite state model can sometimes complete more quickly than verifying a finite version of the model. We also examine modelling techniques to represent abstract models in first-order logic that facilitate this form of model checking.

Date

May 20, 2014

Report

Verifying CTL-live Properties of Infinite State Models using an SMT solver (Version 1) (PDF)

CS-2014-11

Title

Parallelized Runtime Verification of First-order LTL Specifications

Authors

Ramy Medhat, Yogi Joshi, Borzoo Bonakdarpour and Sebastian Fischmeister

Abstract

Runtime verification is an effective automated method for
specification-based offline testing and analysis as well as online
monitoring of complex systems. The specification language is often a variant of regular expressions or a popular temporal logic, such as Ltl. This paper presents a novel and efficient parallel algorithm for verifying a highly expressive fragment of first-order Ltl specifications, where nested quantifiers can be subject to second-order numerical constraints. Such constraints are useful in evaluating thresholds (e.g., expected uptime of a web server). The significance of this extension is that it enables us to reason about the correctness of a large class of systems, such as web servers, OS kernels, and network behaviour, where properties are required to be instantiated for parameterized requests, kernel objects, network nodes, etc. Our algorithm uses the popular MapReduce architecture to split a program trace into variable-based clusters at run time. Each cluster is then mapped to its respective monitor instances, verified, and reduced collectively on a multi-core CPU or the GPU. Our algorithm is fully implemented and we report very encouraging experimental results, where the monitoring overhead is negligible on real-world data sets.

Date

May 29, 2014

Report

Parallelized Runtime Verification of First-order LTL Specifications (PDF)

CS-2014-12

Title

A Framework for Network Location-Aware Node Selection

Authors

Benard Wong, Aleksandrs Slivkins and Emin Gun Sirer

Abstract

This paper introduces a lightweight, scalable and accurate framework for performing node selection based on network location. The framework, called Meridian, consists of an overlay network structured around multi-resolution rings, gossip protocols for ring maintenance, and query routing with direct measurements to satisfy user specified latency constraints. We show that this framework is general and practical by addressing three commonly encountered problems in large-scale distributed systems, namely, closest node discovery, central leader election, and multi-constraint satisfaction, without having to compute absolute co-ordinates. Users can also use the Meridian Query Language to construct custom node selection queries based on their specific network location requirements. We show analytically that the framework is scalable with logarithmic convergence when Internet latencies are modeled as a growth-constrained metric, a low-dimensional Euclidean metric, or a metric of low doubling dimension. The framework is general and admits many different implementations; we provide a sample prototype for evaluation. Large scale simulations, based on latency measurements from 6.25 million node-pairs as well as an implementation deployed on PlanetLab show that the framework is accurate and effective. A case-study that integrates Meridian with a distributed web-proxy service shows an order of magnitude improvement in end-to-end performance, demonstrating Meridian’s substantial impact on real applications.
 

Date

July 22, 2014

Report

A Framework for Network Location-Aware Node Selection (PDF)

 

CS-2014-14

Title

Answering Queries over CFDnc Knowledge Bases

Authors

David Toman and Grant Weddell

Abstract

We exhibit a procedure in the spirit of in which a relational engine can be usefully employed to address scalability issues for answering conjunctive queries in the description logic CFDnc a generalization of the logic CFDnc in which universal restrictions are permitted on left-hand-sides of inclusion dependencies. The procedure necessarily relies on a combination of the strategies that underlie both the perfect rewriting and combined approaches to OBDA.

Date

March 18, 2015

Report

Answering Queries over CFDnc Knowledge Bases (PDF)

 

CS-2014-15

Title

An exploratory study into the use of an emotionally aware cognitive assistant

Authors

Aarti Malhotra, Celia Yu, Tobias Schröder, Jesse Hoey

Abstract

This paper presents the results of a survey of human emotional responses to a set of audio-visual prompts or cues designed for assistive technology applications. Our goal in this paper is exploratory: we wish to understand how audio-visual prompts are understood by people on an emotional spectrum as a first step towards the more challenging task for designing emotionally aligned prompts for persons with cognitive disabilities such as Alzheimer’s disease and related dementias (ADRD). Persons with ADRD often need assistance from a care partner to complete activities of daily living such as washing hands, making food, or getting dressed. Artificially intelligent systems have been developed that can assist in such situations by giving automated prompts or cues. Our long term aim is to enhance such systems by delivering automated prompts that are emotionally aligned with individuals in order to help with prompt adherence and with long-term adoption. As a step in this direction, this paper presents a set of prompt videos of a virtual human ‘Rachel’, wherein she expressively communicates prompts at each step of a simple handwashing task, with various human-like emotions and behaviours. A user study was conducted for 30 such prompt videos with respect to three basic and important dimensions of emotional experience: evaluation, potency, and activity. The results show that, while people generally agree on the evaluation (valence: good/bad) of a prompt, consensus about power and activity is not as socially homogeneous. This paper gives an overview of the hand washing system, and then details the creation process of the virtual human and the results and analysis of the user study.

Date

August 18, 2014

Report

An exploratory study into the use of an emotionally aware cognitive assistant (PDF)

 

CS-2014-17

Title

An Introduction to Anemia and Bilirubinemia

Authors

Ankita Dey, Gladimir V.G. Baranoski and Tenn F. Chen

Abstract

In this report, we provide an overview of two serious medical conditions, anemia and bilirubinemia (commonly known as jaundice), which are associated with changes in the contents of specific chromophores present in the blood stream. In general terms, anemia results from a decrease in the hemoglobin content, while jaundice results from an increase in the bilirubin content. Both of them have a signficant impact on public health worldwide, with anemia being more prevalent among women of childbearing age, and jaundice more common among neonates due their underdeveloped liver. In the remainder of this report, we briefly address their causes, types, symptoms and treatment options. In Section 2, we examine these points with respect to anemia, and in Section 3 with respect to jaundice. This report closes with a summary and general observations about these two medical conditions.

Date

Nov 7, 2014

Report

An Introduction to Anemia and Bilirubinemia (PDF)

 

CS-2014-18

Title

On the Assisted Assessment of Anemia and Bilirubinemia Conditions

Authors

Ankita Dey, Gladimir V.G. Baranoski and Tenn F. Chen

Abstract

In this report, we review a number of procedures and devices that are used to diagnose and quantify the severity levels of two ubiquitous medical conditions, anemia and bilirubinemia (jaundice). Both conditions are associated with changes in the contents of specic chromophores present in the blood, more specically hemoglobin present in the red blood cells (RBCs) and biliribin found in the plasma. In general terms, anemia results from a decrease in the hemoglobin content, while jaundice results from an increase in the bilirubin content. The lower the hemoglobin content, the more severe the anemia condition becomes [1]. Conversely, bilirubinemia becomes more severe with a higher bilirubin content [2]. While both intravenous and extravenous (transcutaneous) methods are being used to measure bilirubin, direct procedures based on the collection of blood samples are normally used to measure hemoglobin content. The remainder of this report is organized as follows. In Section 2, we examine issues related to the assessment of anemia, and in Section 3 issues related to jaundice. This report closes with a summary and an indication of directions for future research in this area.

Date

Nov 7, 2014

Report

On the Assisted Assessment of Anemia and Bilirubinemia Conditions (PDF)

CS-2014-19

Title

An Agent-Based Electric Vehicle Ecosystem Model: San
Francisco Case Study

Authors

Adedamola Adepetu, Vijay Arya and Srinivasan Keshav

Abstract The widespread commercial availability of plug-in Electric Vehicles (EVs) in recent years motivates policies to encourage EV adoption and infrastructure to cope with the increasing number of EVs. We present an agent-based EV ecosystem model that incorporates EV adoption and usage with spatial and temporal considerations and that can aid different EV industry stakeholders such as policymakers, utility operators, charging station planners, and EV
manufacturers. The model follows an ecological modelling approach, and is used to determine how different policies and battery technologies affect EV adoption, EV charging, and charging station activity. We choose model parameters to fit San Francisco as a test city and simulate different scenarios. The results provide insight on potential changes to the San Francisco EV ecosystem as a result of changes in rebates, availability of workplace charging, public awareness of lower EV operational costs, and denser EV batteries. We find that our results match those obtained using other approaches and that the compact geographical size of San Francisco and its relative wealth make it an ideal city for EV
adoption.
Date

October 27, 2014

Report

An Agent-Based Electric Vehicle Ecosystem Model: San Francisco Case Study (PDF)

CS-2014-21

Title

Monte-Carlo Planning for Socially Aligned Agents using
Bayesian Affect Control Theory

Authors

Nabiha Asghar and Jesse Hoey

Abstract Affect Control Theory (ACT) is a mathematically well-defined model that makes accurate predictions about the affective content of human action. The affective predictions, which are derived from statistics about human actions and identities in real and laboratory environments, are shared normative behaviours that are believed to lead to solutions to everyday co-operative problems. A probabilistic and decision-theoretic generalisation of ACT, called BayesAct, allows the principles of ACT to be used for human-interactive agents by defining a utility function and a probabilistic version of the ACT dynamical model of affect. Planning in BayesAct, which we address in this paper, then allows one to go beyond the affective norm, and leads to the emergence of more complex interactions between “cognitive” reasoning and “affective” reasoning, such as deception leading to manipulation and altercasting. As BayesAct is a large hybrid (continuous-discrete) state/action/observation partially observable Markov decision process (POMDP), in this paper we propose a continuous variant of a successful Monte-Carlo tree search planner (POMCP), which performs dynamic discretisation of the action and observation spaces while planning. We demonstrate our variant POMCP-C in simulation on (i) a two-agent co-ordination problem that involves manipulation through affective interaction, and (ii)an affectively-aware assistive health-care device. In addition, we show that our solver can be used in non-affective domains, by demonstrating it on a continuous robot navigation problem from the literature and achieving over 50% increase in average reward compared to traditional solvers.
Date

December 16, 2014

Report Monte-Carlo Planning for Socially Aligned Agents using Bayesian Affect Control Theory (PDF)

CS-2014-22

Title

Multi-Agent Based Simulation in Software Project Management: Scope Management Representation and Visualization

Authors

Davy Baia, Carlos J. P. Lucena, Paulo Alencar, Rafael Rocha, and Donald Cowan

Abstract  Software project management (SPM) has increasingly become an essential task in many organizations, especially with the increase in size, complexity of current software systems. However, software projects often change during development time and there is a lack of models and supporting tools to support the SPM process, especially when it comes to simulations that can assess scenarios involving software project dimensions such as scope, time, cost and quality. In this paper we present our work on a multi-agent based simulation approach to decision making in software project management, with a focus on the scope management processes. In the context of these processes, we will present an instance of our approach in which we provide two essential outcomes to support the human interface aspects, namely (i) the representation of the scope processes ; and (ii) visualization techniques using a Work Breakdown Structure (WBS) to show the dynamics of activity ow sequences. To evaluate our approach, we have implemented the representations in Ja-CaMo, an agent-based framework, and, in terms of coverage, we have shown how it can be mapped to some processes of the SCRUM project management method and to the PMBOK Guide (Project Management Body of Knowledge) scope management process. Based on an exploratory study and our experience, we believe these results help to advance the research area involving the intersection of agents and project management. Especially in terms of modelling and simulation complex and dynamics under conditions pertaining agents, organizations and their environment.
Date

December 15, 2014

Report

Multi-Agent Based Simulation in Software Project Management: Scope Management Representation and Visualization (PDF)

CS-2014-23

Title

Optimal Design of Solar PV Farms with Storage

Authors

Y. Ghiassi-Farrokhfal , F. Kazhamiaka , C. Rosenberg , S. Keshav

Abstract

In the context of a large-scale solar farm participating in an energy market, we consider the problem of allocating a capital budget to solar panels and storage to maximize expected revenue over multiple time periods. This problem is complex due to many factors. To begin with, solar energy production is stochastic, with a high peak-to-average ratio, thus the access link is typically provisioned at less than peak capacity, leading to the potential for waste of energy due to curtailment. The use of storage prevents power curtailment, but the allocation of capital to storage reduces the amount of energy produced. Moreover, energy storage devices are imperfect and their costs diminish over time. We mathematically model these constraints and demonstrate that the problem is still convex, allowing efficient solution. Numerical examples demonstrate the power of our model in doing a sensitivity analysis to various design assumptions. We find that it is typically optimal to invest 90-95% of the initial capital on solar panels and the rest on storage. Interestingly, it is best to defer investment on lead-acid batteries (but not Lithium-ion batteries) closer towards the end of lifetime of the PV panels.

Date

December 11, 2014

Report

Optimal Design of Solar PV Farms with Storage (PDF)

CS-2014-25

Title

On the Remote Detection of Human Skin Signatures

Authors

Gladimir V.G. Baranoski and Tenn F. Chen

Abstract

In this technical report, we examine issues related to the detection of skin signatures in different natural environments. We also propose a new multispectral skin detection index to mitigate the occurrence of false alarms, notably during search and rescue operations.

Date

December 23, 2014

Report

On the Remote Detection of Human Skin Signatures (PDF)

CS-2014-26

Title

How Changing Communication Channels Affect Communication Patterns: Implications for the Design of Smart Objects

Authors

Anastasia Kuzminykh, James Wallace, Richard Zanibbi, Stacey Scott and Edward Lank

Abstract

In this abstract, we present our early work on analysing how communication changes as communication channels change during remote creative problem solving tasks for small, newly formed groups. In particular, our early data indicates persistence in communication style. If validated, this persistence can be leveraged to inform the design of smart objects that support inter-personal communication.

Date

December 23, 2014

Report

How Changing Communication Channels Affect Communication Patterns: Implications for the Design of Smart Objects (PDF)

CS-2014-27

Title

Constrained Nonnegative Matrix Factorization with Applications to Music Transcription

Authors

Daniel Recoskie and Richard Mann

Abstract

We apply nonnegative matrix factorization to the task of music transcription. In music transcription we are given an audio recording of a musical piece and attempt to find the underlying sheet music which generated the music. We improve upon current transcription results by imposing novel temporal and sparsity constraints which exploit the structure of music. We demonstrate the effectiveness or our technique on the MAPS dataset.

Date

December 23, 2014

Report

Constrained Nonnegative Matrix Factorization with Applications to Music Transcription (PDF)