Theory and Algorithms Commons^™

Analysis Of Github Pull Requests, Canon Ellis

Computer Science and Engineering Theses and Dissertations

The popularity of the software repository site GitHub has created a rise in the Pull Based Development Models' use. An essential portion of pull-based development is the creation of Pull Requests. Pull Requests often have to be reviewed by an individual to be approved and accepted into the Master branch of a software repository. The reviewing process can often be time-consuming and introduce a relatively high level of lost development time. This paper examines thousands of pull requests to understand the most valuable metadata of pull requests. We then introduce metrics in comparing the metadata of pull requests to understand …

Extending Import Detection Algorithms For Concept Import From Two To Three Biomedical Terminologies, Vipina K. Keloth, James Geller, Yan Chen, Julia Xu

Publications and Research

Background: While enrichment of terminologies can be achieved in different ways, filling gaps in the IS-A hierarchy backbone of a terminology appears especially promising. To avoid difficult manual inspection, we started a research program in 2014, investigating terminology densities, where the comparison of terminologies leads to the algorithmic discovery of potentially missing concepts in a target terminology. While candidate concepts have to be approved for import by an expert, the human effort is greatly reduced by algorithmic generation of candidates. In previous studies, a single source terminology was used with one target terminology.

Methods: In this paper, we are extending …

Sybil Defense Using Efficient Resource Burning, Diksha Gupta

Computer Science ETDs

In 1993, Dwork and Naor proposed using computational puzzles, a resource burning mechanism, to combat spam email. In the ensuing three decades, resource burning has broadened to include communication capacity, computer memory, and human effort. It has become a well-established tool in distributed security. Due to the cost attached to utilizing resource burning mechanism, these have not been popularized in domains apart from cryptocurrency.

In this dissertation, we design efficient resource burning based Sybil defense techniques for permissionless systems. As a first step, we identify existing resource burning mechanisms in literature in Chapter 2. Additionally, we enumerate numerous open problems …

Using Eye-Gaze To Evaluate Neural Attention, Shahansha Salim

Master’s Dissertations

The ability to selectively concentrate on areas of interest while ignoring the rest is termed as attention in human beings. This ability has played a key role in survival as well as information processing. Neural Attention is said to be an effort to bring similar action of selectively concentrating areas of relevance in deep neural networks. This simple yet powerful concept has attracted a lot of research in recent years, yielding breakthrough results in Natural Language Processing (NLP) problems and main stream Computer Vision problems such as Image Caption Generation, Neural Machine Translation (NMT), Visual Question Answering (VQA), Action Recognition, …

Micro Grid Control Optimization With Load And Solar Prediction, Shaju Saha

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Using renewable energy can save money and keep the environment cleaner. Installing a solar PV system is a one-time cost but it can generate energy for a lifetime. Solar PV does not generate carbon emissions while producing power. This thesis evaluates the value of being able to make accurate predictions in the use of solar energy. It uses predicted solar power and load for a system and a battery to store the energy for future use and calculates the operating cost or profit in several designed conditions. Various factors like a different place, tuning the capacity of sources, changing buy/sell …

Unsupervised Structural Graph Node Representation Learning, Mikel Joaristi

Boise State University Theses and Dissertations

Unsupervised Graph Representation Learning methods learn a numerical representation of the nodes in a graph. The generated representations encode meaningful information about the nodes' properties, making them a powerful tool for tasks in many areas of study, such as social sciences, biology or communication networks. These methods are particularly interesting because they facilitate the direct use of standard Machine Learning models on graphs. Graph representation learning methods can be divided into two main categories depending on the information they encode, methods preserving the nodes connectivity information, and methods preserving nodes' structural information. Connectivity-based methods focus on encoding relationships between nodes, …

Deep Q Learning Applied To Stock Trading, Agnibh Dasgupta

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Developing a strategy for stock trading is a vital task for investors. However, it is challenging to obtain an optimal strategy, given the complex and dynamic nature of the stock market. This thesis aims to explore the applications of Reinforcement Learning with the goal of maximizing returns from market investment, keeping in mind the human aspect of trading by utilizing stock prices represented as candlestick graphs. Furthermore, the algorithm studies public interest patterns in form of graphs extracted from Google Trends to make predictions. Deep Q learning has been used to train an agent based on fused images of stock …

Electro-Optic Satellite Constellation Design Using Multi-Objective Genetic Algorithm, Yasin Tamer

Theses and Dissertations

Satellite constellation design is a complex, highly constrained, and multidisciplinary problem. Unless optimization tools are used, tradeoffs must be conducted at the subsystem level resulting in feasible, but not necessarily optimal, system designs. As satellite technology advances, new methods to optimize the system objectives are developed. This study is based on the development of a representative regional remote sensing constellation design. This thesis analyses the design process of an electrooptic satellite constellation with regional coverage considerations using system-level optimization tools. A multi objective genetic algorithm method is used to optimize the constellation design by utilizing MATLAB and STK integration. Cost, …

Acquisition, Processing, And Analysis Of Video, Audio And Meteorological Data In Multi-Sensor Electronic Beehive Monitoring, Sarbajit Mukherjee

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

In recent years, a widespread decline has been seen in honey bee population and this is widely attributed to colony collapse disorder. Hence, it is of utmost importance that a system is designed to gather relevant information. This will allow for a deeper understanding of the possible reasons behind the above phenomenon to aid in the design of suitable countermeasures.

Electronic Beehive Monitoring is one such way of gathering critical information regarding a colony’s health and behavior without invasive beehive inspections. In this dissertation, we have presented an electronic beehive monitoring system called BeePi that can be placed on top …

Argumentation Stance Polarity And Intensity Prediction And Its Application For Argumentation Polarization Modeling And Diverse Social Connection Recommendation, Joseph Winstead Sirrianni

Graduate Theses and Dissertations

Cyber argumentation platforms implement theoretical argumentation structures that promote higher quality argumentation and allow for informative analysis of the discussions. Dr. Liu’s research group has designed and implemented a unique platform called the Intelligent Cyber Argumentation System (ICAS). ICAS structures its discussions into a weighted cyber argumentation graph, which describes the relationships between the different users, their posts in a discussion, the discussion topic, and the various subtopics in a discussion. This platform is unique as it encodes online discussions into weighted cyber argumentation graphs based on the user’s stances toward one another’s arguments and ideas. The resulting weighted cyber …

An Update On The Computational Theory Of Hamiltonian Period Functions, Bradley Joseph Klee

Graduate Theses and Dissertations

Lately, state-of-the-art calculation in both physics and mathematics has expanded to include the field of symbolic computing. The technical content of this dissertation centers on a few Creative Telescoping algorithms of our own design (Mathematica implementations are given as a supplement). These algorithms automate analysis of integral period functions at a level of difficulty and detail far beyond what is possible using only pencil and paper (unless, perhaps, you happen to have savant-level mental acuity). We can then optimize analysis in classical physics by using the algorithms to calculate Hamiltonian period functions as solutions to ordinary differential equations. The simple …

A Near-Optimal Change-Detection Based Algorithm For Piecewise-Stationary Combinatorial Semi-Bandits, Huozhi Zhou, Lingda Wang, Lav N. Varshney, Ee-Peng Lim

Research Collection School Of Computing and Information Systems

We investigate the piecewise-stationary combinatorial semi-bandit problem. Compared to the original combinatorial semi-bandit problem, our setting assumes the reward distributions of base arms may change in a piecewise-stationary manner at unknown time steps. We propose an algorithm, GLR-CUCB, which incorporates an efficient combinatorial semi-bandit algorithm, CUCB, with an almost parameter-free change-point detector, the Generalized Likelihood Ratio Test (GLRT). Our analysis shows that the regret of GLR-CUCB is upper bounded by O(√NKT logT), where N is the number of piecewise-stationary segments, K is the number of base arms, and T is the number of time steps. As a complement, we also …

Algorithms And Hardness Results For Computing Cores Of Markov Chains, Ali Ahmadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi, Dorde Zikelic

Research Collection School Of Computing and Information Systems

Given a Markov chain M = (V,v0,δ), with state space V and a starting state v0, and a probability threshold ϵ, an ϵ-core is a subset C of states that is left with probability at most ϵ. More formally, C ⊆V is an ϵ-core, iff P reach(V\C) ≤ ϵ. Cores have been applied in a wide variety of verification problems over Markov chains, Markov decision processes, and probabilistic programs, as a means of discarding uninteresting and low-probability parts of a probabilistic system and instead being able to focus on the states that are likely to be encountered in a real-world …

New Methods For Deep Learning Based Real-Valued Inter-Residue Distance Prediction, Jacob Barger

Theses

Background: Much of the recent success in protein structure prediction has been a result of accurate protein contact prediction--a binary classification problem. Dozens of methods, built from various types of machine learning and deep learning algorithms, have been published over the last two decades for predicting contacts. Recently, many groups, including Google DeepMind, have demonstrated that reformulating the problem as a multi-class classification problem is a more promising direction to pursue. As an alternative approach, we recently proposed real-valued distance predictions, formulating the problem as a regression problem. The nuances of protein 3D structures make this formulation appropriate, allowing predictions …

A Theory Of The Engagement In Open Source Projects Via Summer Of Code Programs, Jefferson Silva, Igor Wiese, Daniel M. German, Christoph Treude, Marco A. Gerosa, Igor Steinmacher

Research Collection School Of Computing and Information Systems

Summer of code programs connect students to open source software (OSS) projects, typically during the summer break from school. Analyzing consolidated summer of code programs can reveal how college students, who these programs usually target, can be motivated to participate in OSS, and what onboarding strategies OSS communities adopt to receive these students. In this paper, we study the well-established Google Summer of Code (GSoC) and devise an integrated engagement theory grounded in multiple data sources to explain motivation and onboarding in this context. Our analysis shows that OSS communities employ several strategies for planning and executing student participation, socially …

Generating Routes For Autonomous Driving In Vehicle-To-Infrastructure Communications, Jianjun Yang, Tinggui Chen, Bryson Payne, Ping Guo, Yanping Zhang, Juan Guo

Computer Science Faculty Scholarship

The study of vehicular networks has attracted considerable interest in academia and the industry. In the broad area, connected vehicles and autonomous driving are technologies based on wireless data communication between vehicles or between vehicles and infrastructures. A Vehicle-to-Infrastructure (V2I) system consists of communications and computing over vehicles and related infrastructures. In such a system, wireless sensors are installed in some selected points along roads or driving areas. In autonomous driving, it is crucial for a vehicle to figure out the ideal routes by the communications between its equipped sensors and infrastructures then the vehicle is automatically moving along …

A Survey Of Typical Attributed Graph Queries, Yanhao Wang, Yuchen Li, Ju Fan, Chang Ye, Mingke Chai

Research Collection School Of Computing and Information Systems

Graphs are commonly used for representing complex structures such as social relationships, biological interactions, and knowledge bases. In many scenarios, graphs not only represent topological relationships but also store the attributes that denote the semantics associated with their vertices and edges, known as attributed graphs. Attributed graphs can meet demands for a wide range of applications, and thus a variety of queries on attributed graphs have been proposed. However, these diverse types of attributed graph queries have not been systematically investigated yet. In this paper, we provide an extensive survey of several typical types of attributed graph queries. We propose …

Base-Package Recommendation Framework Based On Consumer Behaviours In Iptv Platform, Kuruparan Shanmugalingam, Ruwinda Ranganayanke, Chanka Gunawardhaha, Rajitha Navarathna

Research Collection School Of Computing and Information Systems

Internet Protocol TeleVision (IPTV) provides many services such as live television streaming, time-shifted media, and Video On Demand (VOD). However, many customers do not engage properly with their subscribed packages due to a lack of knowledge and poor guidance. Many customers fail to identify the proper IPTV service package based on their needs and to utilise their current package to the maximum. In this paper, we propose a base-package recommendation model with a novel customer scoring-meter based on customers behaviour. Initially, our paper describes an algorithm to measure customers engagement score, which illustrates a novel approach to track customer engagement …

Reducing Estimation Bias Via Triplet-Average Deep Deterministic Policy Gradient, Dongming Wu, Xingping Dong, Jianbing Shen, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

The overestimation caused by function approximation is a well-known property in Q-learning algorithms, especially in single-critic models, which leads to poor performance in practical tasks. However, the opposite property, underestimation, which often occurs in Q-learning methods with double critics, has been largely left untouched. In this article, we investigate the underestimation phenomenon in the recent twin delay deep deterministic actor-critic algorithm and theoretically demonstrate its existence. We also observe that this underestimation bias does indeed hurt performance in various experiments. Considering the opposite properties of single-critic and double-critic methods, we propose a novel triplet-average deep deterministic policy gradient algorithm that …

Highly Efficient And Scalable Multi-Hop Ride-Sharing, Yixin Xu, Lars Kulik, Renata Borovica‐Gajic, Abdullah Aldwyish, Jianzhong Qi

Research Collection School Of Computing and Information Systems

On-demand ride-sharing services such as Uber and Lyft have gained tremendous popularity over the past decade, largely driven by the omnipresence of mobile devices. Ride-sharing services can provide economic and environmental benefits such as reducing traffic congestion and vehicle emissions. Multi-hop ride-sharing enables passengers to transfer between vehicles within a single trip, which significantly extends the benefits of ride-sharing and provides ride opportunities that are not possible otherwise. Despite its advantages, offering real-time multi-hop ride-sharing services at large scale is a challenging computational task due to the large combination of vehicles and passenger transfer points. To address these challenges, we …

Controlling Aircraft Yaw Movement By Interval Type-2 Fuzzy Logic, Yamama Shafeek, Laith Majeed, Rasha Naji

Emirates Journal for Engineering Research

Aircraft yaw movement is essential in maneuvering; it has been controlled by some methods which achieved tracking but not fast enough. This paper performs the dynamic modeling of aircraft yaw movement and develops PI and PI-like interval type-2 fuzzy logic controller for the model. The mathematical model is derived by inserting the parameters values of single-engine Navion aircraft into standard equations. Using Matlab/ Simulink platform, the controllers' effectivity is tested and verified in two different cases; system without disturbance and when system is disturbed by some wind gust to investigate the system robustness. Simulation results show that PI controller response …

Espade: An Efficient And Semantically Secure Shortest Path Discovery For Outsourced Location-Based Services, Bharath K. Samanthula, Divyadharshini Karthikeyan, Boxiang Dong, K. Anitha Kumari

Department of Computer Science Faculty Scholarship and Creative Works

With the rapid growth of smart devices and technological advancements in tracking geospatial data, the demand for Location-Based Services (LBS) is facing a constant rise in several domains, including military, healthcare and transportation. It is a natural step to migrate LBS to a cloud environment to achieve on-demand scalability and increased resiliency. Nonetheless, outsourcing sensitive location data to a third-party cloud provider raises a host of privacy concerns as the data owners have reduced visibility and control over the outsourced data. In this paper, we consider outsourced LBS where users want to retrieve map directions without disclosing their location information. …

A Partition Based Feature Selection Approach For Mixed Data Clustering, Ashish Dutt

Student Works (2020-2029)

Presently, educational institutions compile and store huge volumes of data, such as student enrolment and attendance records, as well as their examination results. Mining such data yields stimulating information that serves its handlers well. Rapid growth in educational data points to the fact that distilling massive amounts of data requires a more sophisticated set of algorithms. This issue led to the emergence of the field of Educational Data Mining (EDM). Traditional data mining algorithms cannot be directly applied to educational problems, as they may have a specific objective and function. This implies that a pre-processing algorithm has to be enforced …

خوارزمية لاستخراج أسماء رواة الحديث النبوي آليا اعتمادا على صيغ الإخبار في السند, Omar Koussa, Moustafa Alhajj, Amani Sabra

Al Jinan الجنان

لمّا كان للحديث النبوي الشريف ولعلم الرواية الأثر الواضح في اللغة العربية؛ آثرنا أن نضع بصمتنا في هذا المجال، فقمنا بعمل تطبيق للتعرّف الآلي على أسماء الرواة عبر الاستعانة باللسانيات الحاسوبية. تكمن أهمية هذا العمل في تسهيله استخراج أسماء الرواة خدمة للدارسين في علم الحديث، كذلك سيُشكل هذا العمل نواة لأعمال لاحقة في التصنيف الآلي للرواة، طبقا للتصانيف المقررة في هذا العلم

Efficient Sampling Algorithms For Approximate Temporal Motif Counting, Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate …

Reinforcement Learning For Zone Based Multiagent Pathfinding Under Uncertainty, Jiajing Ling, Tarun Gupta, Akshat Kumar

Research Collection School Of Computing and Information Systems

We address the problem of multiple agents finding their paths from respective sources to destination nodes in a graph (also called MAPF). Most existing approaches assume that all agents move at fixed speed, and that a single node accommodates only a single agent. Motivated by the emerging applications of autonomous vehicles such as drone traffic management, we present zone-based path finding (or ZBPF) where agents move among zones, and agents' movements require uncertain travel time. Furthermore, each zone can accommodate multiple agents (as per its capacity). We also develop a simulator for ZBPF which provides a clean interface from the …

F-Measure Optimisation And Label Regularisation For Energy-Based Neural Dialogue State Tracking Models, Anh Duong Trinh, Robert J. Ross, John D. Kelleher

Conference papers

In recent years many multi-label classification methods have exploited label dependencies to improve performance of classification tasks in various domains, hence casting the tasks to structured prediction problems. We argue that multi-label predictions do not always satisfy domain constraint restrictions. For example when the dialogue state tracking task in task-oriented dialogue domains is solved with multi-label classification approaches, slot-value constraint rules should be enforced following real conversation scenarios.

To address these issues we propose an energy-based neural model to solve the dialogue state tracking task as a structured prediction problem. Furthermore we propose two improvements over previous methods with respect …

Unclonable Secret Keys, Marios Georgiou

Dissertations, Theses, and Capstone Projects

We propose a novel concept of securing cryptographic keys which we call “Unclonable Secret Keys,” where any cryptographic object is modified so that its secret key is an unclonable quantum bit-string whereas all other parameters such as messages, public keys, ciphertexts, signatures, etc., remain classical. We study this model in the authentication and encryption setting giving a plethora of definitions and positive results as well as several applications that are impossible in a purely classical setting.

In the authentication setting, we define the notion of one-shot signatures, a fundamental element in building unclonable keys, where the signing key not only …

Set Operators, Xiaojin Ye

Dissertations, Theses, and Capstone Projects

My research is centered on set operators. These are universally applicable regardless of the internal structure (numeric or non-numeric) of each individual observed datum. In our research, we have developed the theory of set operators to fill holes and gaps in observed data and eliminate paper shred garbage, thereby changing the observed symbolic data set into one whose pattern is closer to the pattern in the underlying population from which the observed data set was sampled with perturbations.

We describe different set operators including increasing operators, decreasing operators, ex- pansive operators, contractive operators, union preserving operators, intersection preserving op- erators, …

Querying Recurrent Convoys Over Trajectory Data, Munkh-Erdene Yadamjav, Zhifeng Bao, Baihua Zheng, Farhana M. Choudhury, Hanan Samet

Research Collection School Of Computing and Information Systems

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. Existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the movement pattern. In this study, we define a problem of finding recurrent pattern of co-moving objects from streaming trajectories and propose an efficient solution that enables us to discover recent co-moving object patterns repeated within a given time period. Experimental results on …