Theory and Algorithms Commons^™

Procedural Music Generation And Adaptation Based On Game State, Timothey Andrew Adam

Master's Theses

Video game developers attempt to convey moods to emphasize their game's narrative. Events that occur within the game usually convey success or failure in some way meaningful to the story's progress. Ideally, when these events occur, the intended change in mood should be perceivable to the player. One way of doing so is to change the music. This requires musical tracks to represent many possible moods, states and game events. This can be very taxing on composers, and encoding the control flow (when to transition) of the tracks can prove to be tricky as well.

This thesis presents AUD.js, a …

Placing Videos On A Semantic Hierarchy For Search Result Navigation, Song Tan, Yu-Gang Jiang, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

Organizing video search results in a list view is widely adopted by current commercial search engines, which cannot support efficient browsing for complex search topics that have multiple semantic facets. In this article, we propose to organize video search results in a highly structured way. Specifically, videos are placed on a semantic hierarchy that accurately organizes various facets of a given search topic. To pick the most suitable videos for each node of the hierarchy, we define and utilize three important criteria: relevance, uniqueness, and diversity. Extensive evaluations on a large YouTube video dataset demonstrate the effectiveness of our approach.

Introducing Non-Determinism To The Parallel C Compiler, Rowen Concepcion

Electronic Theses, Projects, and Dissertations

The Planguages project is the birthplace of the Planguage programming
approach, which is designed to alleviate the task of writing parallel
programs and harness massively parallel computers and networks of workstations.

Planguage has two existing translators, Parallel C (PC) and Pfortran,
which is used for their base languages, C and Fortran77. The translators
work with MPI (Message Passing Interface) for communications. SOS
(ipStreams, Overlapping and Shortcutting), a function library that supports
the three named functionalities, can be used to further optimize parallel algorithms.

This project is the next step in the continuing project of updating
the PC Compiler. The goal …

Regen: Optimizing Genetic Selection Algorithms For Heterogeneous Computing, Scott Kenneth Swinkleb Winkleblack

Master's Theses

GenSel is a genetic selection analysis tool used to determine which genetic markers are informational for a given trait. Performing genetic selection related analyses is a time consuming and computationally expensive task. Due to an expected increase in the number of genotyped individuals, analysis times will increase dramatically. Therefore, optimization efforts must be made to keep analysis times reasonable.

This thesis focuses on optimizing one of GenSel’s underlying algorithms for heterogeneous computing. The resulting algorithm exposes task-level parallelism and data-level parallelism present but inaccessible in the original algorithm. The heterogeneous computing solution, ReGen, outperforms the optimized CPU implementation achieving a …

Bootstrapping Simulation-Based Algorithms With A Suboptimal Policy, Nguyen T., Silander T., Lee W., Tze-Yun Leong

Research Collection School Of Computing and Information Systems

Finding optimal policies for Markov Decision Processes with large state spaces is in general intractable. Nonetheless, simulation-based algorithms inspired by Sparse Sampling (SS) such as Upper Confidence Bound applied in Trees (UCT) and Forward Search Sparse Sampling (FSSS) have been shown to perform reasonably well in both theory and practice, despite the high computational demand. To improve the efficiency of these algorithms, we adopt a simple enhancement technique with a heuristic policy to speed up the selection of optimal actions. The general method, called Aux, augments the look-ahead tree with auxiliary arms that are evaluated by the heuristic policy. In …

Generalized Mandelbrot Sets, Aaron Schlenker

Undergraduate Honors Thesis Collection

A complex point Z₀ is defined to be a member of the famous Mandelbrot set fractal when the iterative process using the function Z² stays bounded when applied to Z₀. We investigate what happens if we change the iterative process so that Z² is now composed with, for example, a Mobius transformation, indexed on a parameter a. The Mandelbrot set corresponds to a = O. What happens when we change a = 0 to other values, repeating the iterative process and then drawing the sets? Do these Generalized Mandelbrot sets have similar properties to …

Decaf: A New Event Detection Logic For The Purpose Of Fusing Delineated-Continuous Spatial Information, Kerry Q. Hart

School of Computing: Dissertations, Theses, and Student Research

Geospatial information fusion is the process of synthesizing information from complementary data sources located at different points in space and time. Spatial phenomena are often measured at discrete locations by sensor networks, technicians, and volunteers; yet decisions often require information about locations where direct measurements do not exist. Traditional methods assume the spatial phenomena to be either discrete or continuous, an assumption that underlies and informs all subsequent analysis. Yet certain phenomena defy this dichotomy, alternating as they move across spatial and temporal scales. Precipitation, for example, appears continuous at large scales, but it can be temporally decomposed into discrete …

Using Statistical Methods To Determine Geolocation Via Twitter, Christopher M. Wright

Masters Theses & Specialist Projects

With the ever expanding usage of social media websites such as Twitter, it is possible to use statistical inquires to form a geographic location of a person using solely the content of their tweets. According to a study done in 2010, Zhiyuan Cheng, was able to detect a location of a Twitter user within 100 miles of their actual location 51% of the time. While this may seem like an already significant find, this study was done while Twitter was still finding its ground to stand on. In 2010, Twitter had 75 million unique users registered, as of March 2013, …

Generating Combinatorial Objects- A New Perspective, Alexander Chizoma Nwala

Computer Science Theses & Dissertations

Combinatorics is the science of "possibilities." This definition, while not formal is a fair statement because all too often, in order to gain insight into the solution of many counting problems, we explore the possibilities. In some cases we seek to know how many options, while in other cases we seek to enumerate or list the options. Irrespective of the scenario, combinatorics plays a vital role today. In many instances such as exploring the options for choosing a new password for a combination lock, we employ combinatorics. In considering the possible license plate permutations for a state, or to see …

Mechanisms For Arranging Ride Sharing And Fare Splitting For Last-Mile Travel Demands, Shih-Fen Cheng, Duc Thien Nguyen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

A great challenge of city planners is to provide efficient and effective connection service to travelers using public transportation system. This is commonly known as the last-mile problem and is critical in promoting the utilization of public transportation system. In this paper, we address the last-mile problem by considering a dynamic and demand-responsive mechanism for arranging ride sharing on a non-dedicated commercial fleet (such as taxis or passenger vans). Our approach has the benefits of being dynamic, flexible, and with low setup cost. A critical issue in such ride-sharing service is how riders should be grouped and serviced, and how …

Persistent Community Detection In Dynamic Social Networks, Siyuan Liu, Shuhui Wang, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

While community detection is an active area of research in social network analysis, little effort has been devoted to community detection using time-evolving social network data. We propose an algorithm, Persistent Community Detection (PCD), to identify those communities that exhibit persistent behavior over time, for usage in such settings. Our motivation is to distinguish between steady-state network activity, and impermanent behavior such as cascades caused by a noteworthy event. The results of extensive empirical experiments on real-life big social networks data show that our algorithm performs much better than a set of baseline methods, including two alternative models and the …

Didn’T You See My Message?: Predicting Attentiveness To Mobile Instant Messages, Martin Pielot, Rodrigo De Oliveira, Haewoon Kwak, Nuria. Oliver

Research Collection School Of Computing and Information Systems

Mobile instant messaging (e.g., via SMS or WhatsApp) often goes along with an expectation of high attentiveness, i.e., that the receiver will notice and read the message within a few minutes. Hence, existing instant messaging services for mobile phones share indicators of availability, such as the last time the user has been online. However, in this paper we not only provide evidence that these cues create social pressure, but that they are also weak predictors of attentiveness. As remedy, we propose to share a machine-computed prediction of whether the user will view a message within the next few minutes or …

Automatic Objects Removal For Scene Completion, Jianjun Yang, Yin Wang, Honggang Wang, Kun Hua, Wei Wang, Ju Shen

Computer Science Faculty Publications

With the explosive growth of Web-based cameras and mobile devices, billions of photographs are uploaded to the Internet. We can trivially collect a huge number of photo streams for various goals, such as 3D scene reconstruction and other big data applications. However, this is not an easy task due to the fact the retrieved photos are neither aligned nor calibrated. Furthermore, with the occlusion of unexpected foreground objects like people, vehicles, it is even more challenging to find feature correspondences and reconstruct realistic scenes. In this paper, we propose a structure-based image completion algorithm for object removal that produces visually …

Multi-Threaded Automatic Integration Using Openmp And Cuda, Rida Assaf

Masters Theses

Problems in many areas give rise to computationally expensive integrals that beg the need of efficient techniques to solve them, e.g., in computational finance for the modeling of cash flows; for the computation of Feynman loop integrals in high energy physics; and in stochastic geometry with applications to computer graphics.

We demonstrate feasible numerical approaches in the framework of the PARINT multivariate integration package. The parallel environment is provided by the cluster of the High Performance Computational Science (HPCS) laboratory, with 22 (16- or 32-core) nodes, NVIDIA GPUs, and Intel Xeon Phi coprocessors.

Monte Carlo integration is implemented in CUDA …

Machine Learning In Wireless Sensor Networks: Algorithms, Strategies, And Applications, Mohammad Abu Alsheikh, Shaowei Lin, Dusit Niyato, Hwee-Pink Tan

Research Collection School Of Computing and Information Systems

Wireless sensor networks (WSNs) monitor dynamic environments that change rapidly over time. This dynamic behavior is either caused by external factors or initiated by the system designers themselves. To adapt to such conditions, sensor networks often adopt machine learning techniques to eliminate the need for unnecessary redesign. Machine learning also inspires many practical solutions that maximize resource utilization and prolong the lifespan of the network. In this paper, we present an extensive literature review over the period 2002-2013 of machine learning methods that were used to address common issues in WSNs. The advantages and disadvantages of each proposed algorithm are …

Are Timed Automata Bad For A Specification Language? Language Inclusion Checking For Timed Automata, Ting Wang, Jun Sun, Yang Liu, Xinyu Wang, Shanping Li

Research Collection School Of Computing and Information Systems

Given a timed automaton P modeling an implementation and a timed automaton S as a specification, language inclusion checking is to decide whether the language of P is a subset of that of S. It is known that this problem is undecidable and “this result is an obstacle in using timed automata as a specification language” [2]. This undecidability result, however, does not imply that all timed automata are bad for specification. In this work, we propose a zone-based semi-algorithm for language inclusion checking, which implements simulation reduction based on Anti-Chain and LU-simulation. Though it is not guaranteed to terminate, …

A Hamming Embedding Kernel With Informative Bag-Of-Visual Words For Video Semantic Indexing, Feng Wang, Wen-Lei Zhao, Chong-Wah Ngo, Bernard Merialdo

Research Collection School Of Computing and Information Systems

In this article, we propose a novel Hamming embedding kernel with informative bag-of-visual words to address two main problems existing in traditional BoW approaches for video semantic indexing. First, Hamming embedding is employed to alleviate the information loss caused by SIFT quantization. The Hamming distances between keypoints in the same cell are calculated and integrated into the SVM kernel to better discriminate different image samples. Second, to highlight the concept-specific visual information, we propose to weight the visual words according to their informativeness for detecting specific concepts. We show that our proposed kernels can significantly improve the performance of concept …

Data Supply Chains, Tamara Kneese

Media Studies

As data moves between actors and organizations, what emerges is a data supply chain. Unlike manufacturing supply chains, transferred data is often duplicated in the process, challenging the essence of ownership. What does ethical data labor look like? How are the various stakeholders held accountable for being good data guardians? What does clean data transfer look like? What kinds of best practices can business and government put into place? What upstream rights to data providers have over downstream commercialization of their data?

Predicting Human Behavior, Tamara Kneese

Media Studies

Countless highly accurate predictions can be made from trace data, with varying degrees of personal or societal consequence (e.g., search engines predict hospital admission, gaming companies can predict compulsive gambling problems, government agencies predict criminal activity). Predicting human behavior can be both hugely beneficial and deeply problematic depending on the context. What kinds of predictive privacy harms are emerging? And what are the implications for systems of oversight and due process protections? For example, what are the implications for employment, health care and policing when predictive models are involved? How should varied organizations address what they can predict?

Advances In Piecewise Smooth Image Reconstruction, Ralf Juengling

Dissertations and Theses

Advances and new insights into algorithms for piecewise smooth image reconstruction are presented. Such algorithms fit a piecewise smooth function to image data without prior knowledge of the number of regions or the location of region boundaries in the best fitting function. This is a difficult model selection problem since the number of parameters of possible solutions varies widely.

The approach followed in this work was proposed by Yvan Leclerc. It uses the Minimum Description Length principle to make the reconstruction problem well-posed: the best fitting function yields the shortest encoding of the image data. In order to derive a …

L-Opacity: Linkage-Aware Graph Anonymization, Sadegh Nobari, Panagiotis Karras, Hwee Hwa Pang, Stephane Bressan

Research Collection School Of Computing and Information Systems

The wealth of information contained in online social networks has created a demand for the publication of such data as graphs. Yet, publication, even after identities have been removed, poses a privacy threat. Past research has suggested ways to publish graph data in a way that prevents the re-identification of nodes. However, even when identities are effectively hidden, an adversary may still be able to infer linkage between individuals with sufficiently high confidence. In this paper, we focus on the privacy threat arising from such link disclosure. We suggest L-opacity, a sufficiently strong privacy model that aims to control an …

Unstructured P2p Link Lifetimes Redux, Zhongmei Yao, Daren B. H. Cline

Computer Science Faculty Publications

We revisit link lifetimes in random P2P graphs under dynamic node failure and create a unifying stochastic model that generalizes the majority of previous efforts in this direction. We not only allow nonexponential user lifetimes and age-dependent neighbor selection, but also cover both active and passive neighbor-management strategies, model the lifetimes of incoming and outgoing links, derive churn-related message volume of the system, and obtain the distribution of transient in/out degree at each user. We then discuss the impact of design parameters on overhead and resilience of the network.

Digital Certificate Management: Optimal Pricing And Crl Releasing Strategies, Jie Zhang, Nan Hu, M. K. Raka

Research Collection School Of Computing and Information Systems

The fast growth of e-commerce and online activities places increasing needs for authentication and secure communication to enable information exchange and online transactions. The public key infrastructure (PKI) provides a promising foundation for meeting such demand, in which certificate authorities (CAs) provide digital certificates. In practice, it is critical to understand consumer purchasing and revocation behaviors so that CAs can better manage the digital certificates and its CRL releasing process. To address this problem, we analytically model a CA's pricing and revocation releasing strategies taking into consideration the users' rational decisions. The model provides solutions two main research questions: (1) …

A Fast Algorithm For The Inversion Of Quasiseparable Vandermonde-Like Matrices, Sirani M. Perera, Grigory Bonik, Vadim Olshevsky

Publications

The results on Vandermonde-like matrices were introduced as a generalization of polynomial Vandermonde matrices, and the displacement structure of these matrices was used to derive an inversion formula. In this paper we first present a fast Gaussian elimination algorithm for the polynomial Vandermonde-like matrices. Later we use the said algorithm to derive fast inversion algorithms for quasiseparable, semiseparable and well-free Vandermonde-like matrices having O(n2) complexity. To do so we identify structures of displacement operators in terms of generators and the recurrence relations(2-term and 3-term) between the columns of the basis transformation matrices for quasiseparable, semiseparable and well-free polynomials. Finally we …

Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott

HMC Senior Theses

Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe …

A Distributed Greedy Algorithm For Constructing Connected Dominating Sets In Wireless Sensor Networks, Akshaye Dhawan, Nicholas A. Scoville, Michelle Tanco

Mathematics, Computer Science & Statistics Faculty Publications

A Connected Dominating Set (CDS) of the graph representing a Wireless Sensor Network can be used as a virtual backbone for routing in the network. Since sensor nodes are constrained by limited on-board batteries, it is desirable to have a small CDS for the network. However, constructing a minimum size CDS has been shown to be a NP-hard problem. In this paper we present a distributed greedy algorithm for constructing a CDS that we call Greedy Connect. Our algorithm operates in two phases, first constructing a dominating set and then connecting the nodes in this set. We evaluate our algorithm …

Information In Biological Systems And The Fluctuation Theorem, Yaşar Demirel

Department of Chemical and Biomolecular Engineering: Faculty Publications

Some critical trends in information theory, its role in living systems and utilization in fluctuation theory are discussed. The mutual information of thermodynamic coupling is incorporated into the generalized fluctuation theorem by using information theory and nonequilibrium thermodynamics. Thermodynamically coupled dissipative structures in living systems are capable of degrading more energy, and processing complex information through developmental and environmental constraints. The generalized fluctuation theorem can quantify the hysteresis observed in the amount of the irreversible work in nonequilibrium regimes in the presence of information and thermodynamic coupling.

Data Mining Based Hybridization Of Meta-Raps, Fatemah Al-Duoli, Ghaith Rabadi

Engineering Management & Systems Engineering Faculty Publications

Though metaheuristics have been frequently employed to improve the performance of data mining algorithms, the opposite is not true. This paper discusses the process of employing a data mining algorithm to improve the performance of a metaheuristic algorithm. The targeted algorithms to be hybridized are the Meta-heuristic for Randomized Priority Search (Meta-RaPS) and an algorithm used to create an Inductive Decision Tree. This hybridization focuses on using a decision tree to perform on-line tuning of the parameters in Meta-RaPS. The process makes use of the information collected during the iterative construction and improvement phases Meta-RaPS performs. The data mining algorithm …

Generic Instance-Specific Automated Parameter Tuning Framework, Linda Lindawati

Dissertations and Theses Collection (Open Access)

Meta-heuristic algorithms play an important role in solving combinatorial optimization problems (COP) in many practical applications. The caveat is that the performance of these meta-heuristic algorithms is highly dependent on their parameter configuration which controls the algorithm behaviour. Selecting the best parameter configuration is often a difficult, tedious and unsatisfying task. This thesis studies the problem of automating the selection of good parameter configurations. Existing approaches to address the challenges of parameter configuration can be classified into one-size-fits-all and instance-specific approaches. One-size-fits-all approaches focus on finding a single best parameter configuration for a set of problem instances, while instance-specific approaches …

An Investigation Of Complex Systems In 16 Dimensions, Jordon M. Huffman

Theses and Dissertations

Sir Isaac Newton studied the world around him. He observed unexplainable phenomena that the math of his time could not prove. With the help of Gottfried Leibniz, he created infinitesimal calculus to prove his theories. The new concepts he created revolutionized science, and opened new realms of science previously unthought of. In 2002, Dr. Stephen Wolfram published A New Kind of Science, He argues that the processes of understanding cellular automata can be applied to other aspects of science. Dr. Rodrigo Obando of Columbus State University took Dr. Wolfram's work and dissected it. By breaking down the rules, he started …