Theory and Algorithms Commons^™

Compress: A Comprehensive Framework Of Trajectory Compression In Road Networks, Yunheng Han, Weiwei Sun, Baihua Zheng

Research Collection School Of Computing and Information Systems

More and more advanced technologies have become available to collect and integrate an unprecedented amount of data from multiple sources, including GPS trajectories about the traces of moving objects. Given the fact that GPS trajectories are vast in size while the information carried by the trajectories could be redundant, we focus on trajectory compression in this article. As a systematic solution, we propose a comprehensive framework, namely, COMPRESS (Comprehensive Paralleled Road-Network-Based Trajectory Compression), to compress GPS trajectory data in an urban road network. In the preprocessing step, COMPRESS decomposes trajectories into spatial paths and temporal sequences, with a thorough justification …

Cataloging Github Repositories, Abhishek Sharma, Ferdian Thung, Pavneet Singh Kochhar, Agus Sulistya, David Lo

Research Collection School Of Computing and Information Systems

GitHub is one of the largest and most popular repository hosting service today, having about 14 million users and more than 54 million repositories as of March 2017. This makes it an excellent platform to find projects that developers are interested in exploring. GitHub showcases its most popular projects by cataloging them manually into categories such as DevOps tools, web application frameworks, and game engines. We propose that such cataloging should not be limited only to popular projects. We explore the possibility of developing such cataloging system by automatically extracting functionality descriptive text segments from readme files of GitHub repositories. …

Sampling Based Approaches For Minimizing Regret In Uncertain Markov Decision Problems (Mdps), Asrar Ahmed, Pradeep Varakantham, Meghna Lowalekar, Yossiri Adulyasak, Patrick Jaillet

Research Collection School Of Computing and Information Systems

Markov Decision Processes (MDPs) are an effective model to represent decision processes in the presence of transitional uncertainty and reward tradeoffs. However, due to the difficulty in exactly specifying the transition and reward functions in MDPs, researchers have proposed uncertain MDP models and robustness objectives in solving those models. Most approaches for computing robust policies have focused on the computation of maximin policies which maximize the value in the worst case amongst all realisations of uncertainty. Given the overly conservative nature of maximin policies, recent work has proposed minimax regret as an ideal alternative to the maximin objective for robust …

Scalable And Fully Distributed Localization In Large-Scale Sensor Networks, Miao Jin, Su Xia, Hongyi Wu, Xianfeng David Gu

Electrical & Computer Engineering Faculty Publications

This work proposes a novel connectivity-based localization algorithm, well suitable for large-scale sensor networks with complex shapes and a non-uniform nodal distribution. In contrast to current state-of-the-art connectivity-based localization methods, the proposed algorithm is highly scalable with linear computation and communication costs with respect to the size of the network; and fully distributed where each node only needs the information of its neighbors without cumbersome partitioning and merging process. The algorithm is theoretically guaranteed and numerically stable. Moreover, the algorithm can be readily extended to the localization of networks with a one-hop transmission range distance measurement, and the propagation of …

Community Detection In Social Networks, Ketki Kulkarni

Master's Projects

The rise of the Internet has brought people closer. The number of interactions between people across the globe has gone substantially up due to social awareness, the advancements of the technology, and digital interaction. Social networking sites have built societies, communities virtually. Often these societies are displayed as a network of nodes depicting people and edges depicting relationships, links. This is a good and e cient way to store, model and represent systems which have a complex and rich information. Towards that goal we need to nd e ective, quick methods to analyze social networks. One of the possible solution …

Influence Detection And Spread Estimation In Social Networks, Madhura Kaple

Master's Projects

A social network is an online platform, where people communicate and share information with each other. Popular social network features, which make them di erent from traditional communication platforms, are: following a user, re-tweeting a post, liking and commenting on a post etc. Many companies use various social networking platforms extensively as a medium for marketing their products. A xed amount of budget is alloted by the companies to maximize the positive in uence of their product. Every social network consists of a set of users (people) with connections between them. Each user has the potential to extend its in …

An Improved Algorithm For Learning To Perform Exception-Tolerant Abduction, Mengxue Zhang

McKelvey School of Engineering Graduate Student Theses & Dissertations

Abstract

Inference from an observed or hypothesized condition to a plausible cause or explanation for this condition is known as abduction. For many tasks, the acquisition of the necessary knowledge by machine learning has been widely found to be highly effective. However, the semantics of learned knowledge are weaker than the usual classical semantics, and this necessitates new formulations of many tasks. We focus on a recently introduced formulation of the abductive inference task that is thus adapted to the semantics of machine learning. A key problem is that we cannot expect that our causes or explanations will be perfect, …

Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz

Mathematical Sciences Technical Reports (MSTR)

The problem of exact polynomial factorization, in other words expressing a polynomial as a product of irreducible polynomials over some field, has applications in algebraic number theory. Although some algorithms for factorization over algebraic number fields are known, few are taught such general algorithms, as their use is mainly as part of the code of various computer algebra systems. This thesis provides a summary of one such algorithm, which the author has also fully implemented at https://github.com/Whirligig231/number-field-factorization, along with an analysis of the runtime of this algorithm. Let k be the product of the degrees of the adjoined elements used …

Unsupervised Machine Learning In Agent-Based Modeling, Luke D. Robinson

Celebration of Learning

Agent-based models (ABMs) are used by researchers in a variety of fields to model natural phenomena. In an ABM, a wide range of behaviors and outcomes can be observed based on the parameters of the model. In many cases, these behaviors can be categorized into discrete outcomes identifiable by human observers. Our goal was to use clustering algorithms to identify those outcomes from model output data. For this project, we used data from the NetLogo Wolf Sheep Predation model to explore and evaluate three clustering algorithms from Python's scikit-learn package. If this task can be completed reliably by a computer, …

Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler

Honors College Theses

Many factors come into play when it comes to the transmission of infectious diseases. In disease control and prevention, it is inevitable to consider the general population and the relationships between individuals as a whole, which calls for advanced mathematical modeling approaches.

We will use the concept of network flow and the modified Ford-Fulkerson algorithm to demonstrate the transmission of infectious diseases over a given period of time. Through our model one can observe what possible measures should be taken or improved upon in the case of an epidemic. We identify key nodes and edges in the resulted network, which …

Optimized Forecasting Of Dominant U.S. Stock Market Equities Using Univariate And Multivariate Time Series Analysis Methods, Michael Schwartz

Computational and Data Sciences Theses

This dissertation documents an investigation into forecasting U.S. stock market equities via two very different time series analysis techniques: 1) autoregressive integrated moving average (ARIMA), and 2) singular spectrum analysis (SSA). Approximately 40% of the S&P 500 stocks are analyzed. Forecasts are generated for one and five days ahead using daily closing prices. Univariate and multivariate structures are applied and results are compared. One objective is to explore the hypothesis that a multivariate model produces superior performance over a univariate configuration. Another objective is to compare the forecasting performance of ARIMA to SSA, as SSA is a relatively recent development …

Music Feature Matching Using Computer Vision Algorithms, Mason Hollis

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper seeks to establish the validity and potential benefits of using existing computer vision techniques on audio samples rather than traditional images in order to consistently and accurately identify a song of origin from a short audio clip of potentially noisy sound. To do this, the audio sample is first converted to a spectrogram image, which is used to generate SURF features. These features are compared against a database of features, which have been previously generated in a similar fashion, in order to find the best match. This algorithm has been implemented in a system that can run as …

A Comparative Study Of Cognitive Systems For Learning, Praneetha Mandava

Theses and Dissertations

Learning is the modification of a behavioral tendency by experience. Memory and reasoning are the most important aspects for learning in humans; information is temporarily stored in the short-term memory and processed, compared with existing memories and stored in long-term memory, and can be re-used when needed. One way to describe an organized pattern of thought or behavior and the categories of information along with their relationships is by using schemas. A cognitive script is one form of a schema that evolves over multiple exposures to the same set of stimuli and/or repeated enactment of a particular behavior. This research …

Determining Feasibility Resilience: Set Based Design Iteration Evaluation Through Permutation Stability Analysis, James E. Ross

Dissertations

The goal of robust design is to select a design that will still perform satisfactorily even with unexpected variation in design parameters. A resilient design will accommodate unanticipated future system requirements. Through studying the variations of system parameters through the use of multi objective optimization, a designer hopes to locate a robustly resilient design, which performs current mission well even with varying system parameters and is able to be easily repurposed to new missions. This ability to withstand changes is critical because it is common for the product of a design to undergo changes throughout its life cycle. This subject …

A Trivium-Inspired Pseudorandom Number Generator With A Statistical Comparison To The Randomness Of Securerandom And Trivium, Latoya Niesha Jackson

Theses and Dissertations

A pseudorandom number generator (PRNG) is an algorithm that produces a sequence of numbers which emulates the characteristics of a random sequence. In comparison to its genuine counterpart, PRNGs are considered more suitable for computing devices in that they do not consume a lot of resources (in terms of memory) and their portability; they can also be used on a wide range of devices. Cryptographically Secure PRNGs (CSPRNGs) are the only type of PRNGs suitable for cryptographic applications. They are specially designed to withstand security attacks. In this thesis, we provide descriptions of two CSPRNGs: Trivium, a hardware-based stream cipher …

Electrodynamical Modeling For Light Transport Simulation, Michael G. Saunders

Undergraduate Honors Theses

Modernity in the computer graphics community is characterized by a burgeoning interest in physically based rendering techniques. That is to say that mathematical reasoning from first principles is widely preferred to ad hoc, approximate reasoning in blind pursuit of photorealism. Thereby, the purpose of our research is to investigate the efficacy of explicit electrodynamical modeling by means of the generalized Jones vector given by Azzam [1] and the generalized Jones matrix given by Ortega-Quijano & Arce-Diego [2] in the context of stochastic light transport simulation for computer graphics. To augment the status quo path tracing framework with such a modeling …

Exploiting Anonymity And Homogeneity In Factored Dec-Mdps Through Pre-Computed Binomial Distributions, Rajiv Ranjan Kumar, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Recent work in decentralized stochastic planning for cooperative agents has focussed on exploiting omogeneity of agents and anonymity in interactions to solve problems with large numbers of agents. Due to a linear optimization formulation that computes joint policy and an objective that indirectly approximates joint expected reward with reward for expected number of agents in all state, action pairs, these approaches have ensured improved scalability. Such an objective closely approximates joint expected reward when there are many agents, due to law of large numbers. However, the performance deteriorates in problems with fewer agents. In this paper, we improve on the …

Collaborative Topic Regression For Online Recommender Systems: An Online And Bayesian Approach, Chenghao Liu, Tao Jin, Steven C. H. Hoi, Peilin Zhao, Jianling Sun

Research Collection School Of Computing and Information Systems

Collaborative Topic Regression (CTR) combines ideas of probabilistic matrix factorization (PMF) and topic modeling (such as LDA) for recommender systems, which has gained increasing success in many applications. Despite enjoying many advantages, the existing Batch Decoupled Inference algorithm for the CTR model has some critical limitations: First of all, it is designed to work in a batch learning manner, making it unsuitable to deal with streaming data or big data in real-world recommender systems. Secondly, in the existing algorithm, the item-specific topic proportions of LDA are fed to the downstream PMF but the rating information is not exploited in discovering …

Core Determining Class And Inequality Selection, Ye Luo, Hai Wang

Research Collection School Of Computing and Information Systems

The relations between unobserved events and observed outcomes can be characterized by a bipartite graph. We propose an algorithm that explores the structure of the graph to construct the "exact Core Determining Class," i.e., the set of irredudant inequalities. We prove that in general the exact Core Determining Class does not depend on the probability measure of the outcomes but only on the structure of the graph. For more general linear inequalities selection problems, we propose a statistical procedure similar to the Dantzig Selector to select the truly informative constraints. We demonstrate performances of our procedures in Monte-Carlo experiments.

Robust Object Tracking Via Locality Sensitive Histograms, Shengfeng He, Rynson W.H Lau, Qingxiong Yang, Jiang Wang, Ming-Hsuan Yang

Research Collection School Of Computing and Information Systems

This paper presents a novel locality sensitive histogram (LSH) algorithm for visual tracking. Unlike the conventional image histogram that counts the frequency of occurrence of each intensity value by adding ones to the corresponding bin, an LSH is computed at each pixel location, and a floating-point value is added to the corresponding bin for each occurrence of an intensity value. The floating-point value exponentially reduces with respect to the distance to the pixel location where the histogram is computed. An efficient algorithm is proposed that enables the LSHs to be computed in time linear in the image size and the …