2014 technical reports

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.

January 27, 2014

Perspectives on Open Data: Issues and Opportunities (PDF)

Reachable Subwebs for Traversal-Based Query Execution

Olaf Hartig and M. Tamer Özsu

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.

February 4, 2014

Reachable Subwebs for Traversal-Based Query Execution (PDF)

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

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

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.

February 28, 2014

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

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

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

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.

March 06, 2014

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

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

Amirhossein Vakili, Nancy A. Day

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.
 

March 20, 2014

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

A Risk Management Approach for Distributed Event-Based Systems

Sergey Savinov and Paulo Alencar

April 21, 2014

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

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

Michael Cormier, Daniel J. Lizotte, and Richard Mann

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.

May 7, 2014

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

Digital Marbling a GPU Approach with Precomputer Velocity Field

Si Wen

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.

May 7, 2014

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

Constructing Call Graphs of Scala Programs

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

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.
 

May 14, 2014

Constructing Call Graphs of Scala Programs (PDF)

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

Amirhossein Vakili and Nancy A. Day

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.

May 20, 2014

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

Parallelized Runtime Verification of First-order LTL Specifications

Ramy Medhat, Yogi Joshi, Borzoo Bonakdarpour and Sebastian Fischmeister

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.

May 29, 2014

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

A Framework for Network Location-Aware Node Selection

Benard Wong, Aleksandrs Slivkins and Emin Gun Sirer

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.
 

July 22, 2014

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

Answering Queries over CFD^∀_ncKnowledge Bases

David Toman and Grant Weddell

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 CFD^∀_nc a generalization of the logic CFD_nc 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.

March 18, 2015

Answering Queries over CFD∀nc Knowledge Bases (PDF)

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

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

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.

August 18, 2014

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

An Introduction to Anemia and Bilirubinemia

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

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.

Nov 7, 2014

An Introduction to Anemia and Bilirubinemia (PDF)

On the Assisted Assessment of Anemia and Bilirubinemia Conditions

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

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.

Nov 7, 2014

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

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

Adedamola Adepetu, Vijay Arya and Srinivasan Keshav

October 27, 2014

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

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

Nabiha Asghar and Jesse Hoey

December 16, 2014

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

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

December 15, 2014

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

Optimal Design of Solar PV Farms with Storage

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

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.

December 11, 2014

Optimal Design of Solar PV Farms with Storage (PDF)

On the Remote Detection of Human Skin Signatures

Gladimir V.G. Baranoski and Tenn F. Chen

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.

December 23, 2014

On the Remote Detection of Human Skin Signatures (PDF)

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

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

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.

December 23, 2014

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

Constrained Nonnegative Matrix Factorization with Applications to Music Transcription

Daniel Recoskie and Richard Mann

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.

December 23, 2014

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