Computer Sciences Commons^™

Techniques For Improving The Scalability Of Data Center Networks, Advait Dixit

Open Access Dissertations

Data centers require highly scalable data and control planes for ensuring good performance of distributed applications. Along the data plane, network throughput and latency directly impact application performance metrics. This has led researchers to propose high bisection bandwidth network topologies based on multi-rooted trees for data center networks. However, such topologies require efficient traffic splitting algorithms to fully utilize all available bandwidth. Along the control plane, the centralized controller for software-defined networks presents new scalability challenges. The logically centralized controller needs to scale according to network demands. Also, since all services are implemented in the centralized controller, it should allow …

On The Occurrences Of Motifs In Recursive Trees, With Applications To Random Structures, Mohan Gopaladesikan

Open Access Dissertations

In this dissertation we study three problems related to motifs and recursive trees. In the first problem we consider a collection of uncorrelated motifs and their occurrences on the fringe of random recursive trees. We compute the exact mean and variance of the multivariate random vector of the counts of occurrences of the motifs. We further use the Cramér-Wold device and the contraction method to show an asymptotic convergence in distribution to a multivariate normal random variable with this mean and variance. ^ The second problem we study is that of the probability that a collection of motifs (of the …

Secure Platforms For Enforcing Contextual Access Control, Aditi Gupta

Open Access Dissertations

Advances in technology and wide scale deployment of networking enabled portable devices such as smartphones has made it possible to provide pervasive access to sensitive data to authorized individuals from any location. While this has certainly made data more accessible, it has also increased the risk of data theft as the data may be accessed from potentially unsafe locations in the presence of untrusted parties. The smartphones come with various embedded sensors that can provide rich contextual information such as sensing the presence of other users in a context. Frequent context profiling can also allow a mobile device to learn …

Trustworthy Data From Untrusted Databases, Rohit Jain

Open Access Dissertations

Increasingly, data are subjected to environments which can result in invalid (malicious or inadvertent) modifications to the data. For example, when we host the database on a third party server, or when there is a threat of insider attack or hacker attack. Ensuring the trustworthiness of data retrieved from a database is of utmost importance to users. In this dissertation, we address the question of whether a data owner can be assured that the data retrieved from an untrusted server are trustworthy. In particular, we reduce the level of trust necessary in order to establish the trustworthiness of data. Earlier …

Functional Programming Abstractions For Weakly Consistent Systems, Sivaramakrishnan Krishnamoorthy Chandrasekaran

Open Access Dissertations

In recent years, there has been a wide-spread adoption of both multicore and cloud computing. Traditionally, concurrent programmers have relied on the underlying system providing strong memory consistency, where there is a semblance of concurrent tasks operating over a shared global address space. However, providing scalable strong consistency guarantees as the scale of the system grows is an increasingly difficult endeavor. In a multicore setting, the increasing complexity and the lack of scalability of hardware mechanisms such as cache coherence deters scalable strong consistency. In geo-distributed compute clouds, the availability concerns in the presence of partial failures prohibit strong consistency. …

Relation Among Images: Modelling, Optimization And Applications, Bin Shen

Open Access Dissertations

In the last two decades, the increasing popularity of information technology has led to a dramatic increase in the amount of visual data. Many applications are developed by processing, analyzing and understanding such increasing data; and modelling the relation among images is fundamental to success of many of them. Examples include image classification, content-based image retrieval and face recognition. Given signatures of images, there are many ways to depict the relation among them, such as pairwise distance, kernel function and factor analysis. However, existing methods are still insufficient as they suffer from many real factors such as misalignment of images …

Theory Of Topological Insulators And Its Applications, Parijat Sengupta

Open Access Dissertations

An important pursuit in semiconductor physics is to discover new materials to sustain the continuous progress and improvements in the current electronic devices. Traditionally, three material types are in use: 1) Metals 2) Semiconductors 3) Insulators. All the three material types are classified according to the energy gap between conduction and valence bands derived from band theory of solids. Recent theoretical predictions and confirmed by experimental observations have provided evidence that there exists materials which behave as insulators in the bulk but possess gapless conducting states on the surface. These new class of materials are called topological insulators (TI). In …

Scaling Finite Difference Methods In Large Eddy Simulation Of Jet Engine Noise To The Petascale: Numerical Methods And Their Efficient And Automated Implementation, Yingchong Situ

Open Access Dissertations

Reduction of jet engine noise has recently become a new arena of competition between aircraft manufacturers. As a relatively new field of research in computational fluid dynamics (CFD), computational aeroacoustics (CAA) prediction of jet engine noise based on large eddy simulation (LES) is a robust and accurate tool that complements the existing theoretical and experimental approaches. In order to satisfy the stringent requirements of CAA on numerical accuracy, finite difference methods in LES-based jet engine noise prediction rely on the implicitly formulated compact spatial partial differentiation and spatial filtering schemes, a crucial component of which is an embedded solver for …

Digital Provenance - Models, Systems, And Applications, Salmin Sultana

Open Access Dissertations

Data provenance refers to the history of creation and manipulation of a data object and is being widely used in various application domains including scientific experiments, grid computing, file and storage system, streaming data etc. However, existing provenance systems operate at a single layer of abstraction (workflow/process/OS) at which they record and store provenance whereas the provenance captured from different layers provide the highest benefit when integrated through a unified provenance framework. To build such a framework, a comprehensive provenance model able to represent the provenance of data objects with various semantics and granularity is the first step. In this …

Algebraic Level Sets For Cad/Cae Integration And Moving Boundary Problems, Kritika Upreti

Open Access Dissertations

Boundary representation (B-rep) of CAD models obtained from solid modeling kernels are commonly used in design, and analysis applications outside the CAD systems. Boolean operations between interacting B-rep CAD models as well as analysis of such multi-body systems are fundamental operations on B-rep geometries in CAD/CAE applications. However, the boundary representation of B-rep solids is, in general, not a suitable representation for analysis operations which lead to CAD/CAE integration challenges due to the need for conversion from B-rep to volumetric approximations. The major challenges include intermediate mesh generation step, capturing CAD features and associated behavior exactly and recurring point containment …

Rational Multiparty Computation, John Ross Wallrabenstein

Open Access Dissertations

The field of rational cryptography considers the design of cryptographic protocols in the presence of rational agents seeking to maximize local utility functions. This departs from the standard secure multiparty computation setting, where players are assumed to be either honest or malicious. ^ We detail the construction of both a two-party and a multiparty game theoretic framework for constructing rational cryptographic protocols. Our framework specifies the utility function assumptions necessary to realize the privacy, correctness, and fairness guarantees for protocols. We demonstrate that our framework correctly models cryptographic protocols, such as rational secret sharing, where existing work considers equilibrium concepts …

Image Analysis Using Visual Saliency With Applications In Hazmat Sign Detection And Recognition, Bin Zhao

Open Access Dissertations

Visual saliency is the perceptual process that makes attractive objects "stand out" from their surroundings in the low-level human visual system. Visual saliency has been modeled as a preprocessing step of the human visual system for selecting the important visual information from a scene. We investigate bottom-up visual saliency using spectral analysis approaches. We present separate and composite model families that generalize existing frequency domain visual saliency models. We propose several frequency domain visual saliency models to generate saliency maps using new spectrum processing methods and an entropy-based saliency map selection approach. A group of saliency map candidates are then …

Energy-Efficient Information Inference In Wireless Sensor Networks Based On Graphical Modeling, Wei Zhao

Open Access Dissertations

This dissertation proposes a systematic approach, based on a probabilistic graphical model, to infer missing observations in wireless sensor networks (WSNs) for sustaining environmental monitoring. This enables us to effectively address two critical challenges in WSNs: (1) energy-efficient data gathering through planned communication disruptions resulting from energy-saving sleep cycles, and (2) sensor-node failure tolerance in harsh environments. In our approach, we develop a pairwise Markov Random Field (MRF) to model the spatial correlations in a sensor network. Our MRF model is first constructed through automatic learning from historical sensed data, by using Iterative Proportional Fitting (IPF). When the MRF model …

Canvas: A Fast And Accurate Geometric Sentence Alignment System Using Lexical Cues Within Complex Misalignment Settings, Hussein M. Ghaly

Dissertations, Theses, and Capstone Projects

In this paper, we present a new sentence alignment system (Canvas), which is a Python implementation of a geometric approach to sentence alignment, based on lexical cues. Canvas system is designed mainly to handle parallel texts exhibiting complex misalignment patterns, namely within English-Arabic pairs for United Nations documents. The system relies heavily on pre-indexing words/tokens in the source and target texts, and it creates correspondences between the token indexes. From this point onward, the alignment problem is reduced to a geometric problem of finding the path that runs through the True Correspondence Points (TCPs). The likelihood of a point being …

The Computational Complexity Of Some Games And Puzzles With Theoretical Applications, Vasiliki Despoina Mitsou

Dissertations, Theses, and Capstone Projects

The subject of this thesis is the algorithmic properties of one- and two-player

games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles

and games in this context are of the following type: can we design efficient computer

programs that play optimally given any opponent (for a two-player game), or solve

any instance of the puzzle in question?

We examine four games and puzzles and show algorithmic as well as intractability

results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport

a wolf, a goat, and a cabbage across a river by using a …

Text Extraction From Natural Scene: Methodology And Application, Chucai Yi

Dissertations, Theses, and Capstone Projects

With the popularity of the Internet and the smart mobile device, there is an increasing demand for the techniques and applications of image/video-based analytics and information retrieval. Most of these applications can benefit from text information extraction in natural scene. However, scene text extraction is a challenging problem to be solved, due to cluttered background of natural scene and multiple patterns of scene text itself. To solve these problems, this dissertation proposes a framework of scene text extraction.

Scene text extraction in our framework is divided into two components, detection and recognition. Scene text detection is to find out the …

Systematic Comparison Of Cross-Lingual Projection Techniques For Low-Density Nlp Under Strict Resource Constraints, Joshua Waxman

Dissertations, Theses, and Capstone Projects

The field of low-density NLP is often approached from an engineering perspective, and evaluations are typically haphazard - considering different architectures, given different languages, and different available resources - without a systematic comparison. The resulting architectures are then tested on the unique corpus and language for which this approach has been designed. This makes it difficult to truly evaluate which approach is truly the "best," or which approaches are best for a given language.

In this dissertation, several state-of-the-art architectures and approaches to low-density language Part-Of-Speech Tagging are reimplemented; all of these techniques exploit a relationship between a high-density (HD) …

Randomized Search Of Graphs In Log Space And Probabilistic Computation, Wen-Ju Cheng

Dissertations, Theses, and Capstone Projects

Reingold has shown that L = SL, that s-t connectivity in a poly-mixing digraph is complete for promise-RL, and that s-t connectivity for a poly-mixing out-regular digraph with known stationary distribution is in L. Several properties that bound the mixing times of random walks on digraphs have been identified, including the digraph conductance and the digraph spectral expansion. However, rapidly mixing digraphs can still have exponential cover time, thus it is important to specifically identify structural properties of digraphs that effect cover times. We examine the complexity of random walks on a basic parameterized family of unbalanced digraphs called Strong …

Quantum Crystallography Of Hydronium Cations, Sonjae Sycoria Wallace

Dissertations, Theses, and Capstone Projects

Cationic hydronium clusters of the form [HaOb]^c,(c>0), have been investigated. After investigating over 2000 crystal structures containing hydronium cations found in the Cambridge Structural Database. The hydronium cationic compounds that were most unusual, mischaracterized, or those of apparent aggregates, were investigated further by geometry optimization and in some cases with the Quantum Theory of Atoms in Molecules (QTAIM). The results of our investigations yielded the first reports of stable conformations of cyclic dihydronium cationic clusters. In a second investigation we reported the first theoretically confirmed transition state of a H7O3+conformer captured within a crystal. A third product from our …

Multi-Agent Orienteering Problem With Time-Dependent Capacity Constraints, Cen Chen, Shih-Fen Cheng, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at certain nodes simultaneously. As all nodes are capacitated, if a particular …

Scalable Detection And Extraction Of Data In Lists In Ocred Text For Ontology Population Using Semi-Supervised And Unsupervised Active Wrapper Induction, Thomas L. Packer

Theses and Dissertations

Lists of records in machine-printed documents contain much useful information. As one example, the thousands of family history books scanned, OCRed, and placed on-line by FamilySearch.org probably contain hundreds of millions of fact assertions about people, places, family relationships, and life events. Data like this cannot be fully utilized until a person or process locates the data in the document text, extracts it, and structures it with respect to an ontology or database schema. Yet, in the family history industry and other industries, data in lists goes largely unused because no known approach adequately addresses all of the costs, challenges, …

Compositional Vector Space Models For Improved Bug Localization, Shaowei Wang, David Lo, Julia Lawall

Research Collection School Of Computing and Information Systems

Software developers and maintainers often need to locate code units responsible for a particular bug. A number of Information Retrieval (IR) techniques have been proposed to map natural language bug descriptions to the associated code units. The vector space model (VSM) with the standard tf-idf weighting scheme (VSMnatural), has been shown to outperform nine other state-of-the-art IR techniques. However, there are multiple VSM variants with different weighting schemes, and their relative performance differs for different software systems. Based on this observation, we propose to compose various VSM variants, modelling their composition as an optimization problem. We propose a genetic algorithm …

Partisan Sharing: Facebook Evidence And Societal Consequences, Jisun An, Daniele Quercia, Jon Crowcroft

Research Collection School Of Computing and Information Systems

The hypothesis of selective exposure assumes that people seek out information that supports their views and eschew information that conflicts with their beliefs, and that has negative consequences on our society. Few researchers have recently found counter evidence of selective exposure in social media: users are exposed to politically diverse articles. No work has looked at what happens after exposure, particularly how individuals react to such exposure, though. Users might well be exposed to diverse articles but share only the partisan ones. To test this, we study partisan sharing on Facebook: the tendency for users to predominantly share like-minded news …

Attribute-Based Signing Right Delegation, Weiwei Liu, Yi Mu, Guomin Yang

Research Collection School Of Computing and Information Systems

Attribute-based signature and proxy signature are both very useful in many real-world applications. In this paper, we combine the special features of both signatures and propose an attribute-based proxy signature scheme, where the original signer, who possesses a set of attributes, can delegate his/her signing right to a designated proxy signer. By verifying the signature, a verifier can be convinced that the signature is generated by the proxy signer who has obtained the delegation from a legitimate signer whose attributes satisfy a predicate. However, the verifier cannot tell from the signature who is the original signer. We provide the formal …

Enabling National Software Development Competitions To Identify And Enhance Student Mentor Capability In Singapore, Chris Boesch, Sandra Boesch

Research Collection School Of Computing and Information Systems

The authors previously developed a system to facilitate the self-directed learning and practicing of software languages in Singapore. One of the goals of this self-directed learning was to enable the creation of student mentors who would be able to assist other students during classroom sessions. Building on this work, the authors extended the platform to support the promotion and coordination of multiple programming competitions including multiple schools systems within Singapore with the goals of identifying, enabling, and mentoring students who might be better prepared to mentor their peers at their school after participating in the country wide competition. This paper …

Cost-Sensitive Online Classification, Jialei Wang, Peilin Zhao, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Both cost-sensitive classification and online learning have been extensively studied in data mining and machine learning communities, respectively. However, very limited study addresses an important intersecting problem, that is, “Cost-Sensitive Online Classification". In this paper, we formally study this problem, and propose a new framework for Cost-Sensitive Online Classification by directly optimizing cost-sensitive measures using online gradient descent techniques. Specifically, we propose two novel cost-sensitive online classification algorithms, which are designed to directly optimize two well-known cost-sensitive measures: (i) maximization of weighted sum of sensitivity and specificity, and (ii) minimization of weighted misclassification cost. We analyze the theoretical bounds of …

Survey On Wakeup Scheduling For Environmentally-Powered Wireless Sensor Networks, Alvin Cerdena Valera, Wee-Seng Soh, Hwee-Pink Tan

Research Collection School Of Computing and Information Systems

Advances in energy harvesting technologies and ultra low-power computing and communication devices are enabling the realization of environmentally-powered wireless sensor networks (EPWSNs). Because of limited and dynamic energy supply, EPWSNs are duty-cycled to achieve energy-neutrality, a condition where the energy demand does not exceed the energy supply. Duty cycling entails nodes to sleep and wakeup according to a wakeup scheduling scheme. In this paper, we survey the various wakeup scheduling schemes, with focus on their suitability for EPWSNs. A classification scheme is proposed to characterize existing wakeup scheduling schemes, with three main categories, namely, asynchronous, synchronous, and …

Singapore Management University Establishes A New Research Centre On Secure Mobile Computing Technologies And Solutions, Singapore Management University

SMU Press Releases and News

The Singapore Management University (SMU) has announced today the establishment of a new centre of research excellence that focuses on mobile computing security. Funded by Singapore’s National Research Foundation (NRF), the Secure Mobile Centre is developing efficient and scalable technologies and solutions that strengthen the security of mobile computing systems, applications and services. The Secure Mobile Centre is led by a team of five faculty members from SMU’s School of Information Systems who specialise in information security and trust: Professor Robert DENG (Centre Director), Professor PANG Hwee Hwa, Associate Professor LI Yingjiu, Associate Professor DING Xuhua and Assistant Professor Debin …

Ecs Evaluation Survey Instruments, Ronald I. Greenberg, Steven Mcgee

Computer Science: Faculty Publications and Other Works

This is a compilation of several surveys used in conjunction with a large-scale implementation of the Exploring Computer Science Curriculum in high schools in the Chicago Public Schools: ECS student presurvey pp. 1--2, ECS student postsurvey pp. 3--4, teacher background survey pp. 5--11, teacher ECS workshop feedback form pp. 12--13, teacher ECS implementation survey pp. 14--24

Self-Referentiality In Constructive Semantics Of Intuitionistic And Modal Logics, Junhua Yu

Dissertations, Theses, and Capstone Projects

This thesis explores self-referentiality in the framework of justification logic. In this framework initialed by Artemov, the language has formulas of the form t:F, which means "the term t is a justification of the formula F." Moreover, terms can occur inside formulas and hence it is legal to have t:F(t), which means "the term t is a justification of the formula F about t itself." Expressions like this is not only interesting in the semantics of justification logic, but also, as we will see, necessary in applications of justification logic in formalizing constructive contents implicitly carried by modal and intuitionistic …