Computer Sciences Commons^™

Solving The Winner Determination Problem For Online B2b Transportation Matching Platforms, Hoong Chuin Lau, Baoxiang Li

Research Collection School Of Computing and Information Systems

We consider the problem of matching multiple shippers and transporters participating in an online B2B last-mile logistics platform in an emerging market. Each shipper places a bid that is made up of multiple jobs, where each job comprises key information like the weight, volume, pickup and delivery locations, and time windows. Each transporter specifies its vehicle capacity, available time periods, and a cost structure. We formulate the mathematical model and provide a Branch-and-Cut approach to solve small-scale problem instances exactly and larger scale instances heuristically using an Adaptive Large Neighbourhood Search approach. To increase the win percentage of both shippers …

Minimizing The Regret Of An Influence Provider, Yipeng Zhang, Yuchen Li, Zhifeng Bao, Baihua Zheng

Research Collection School Of Computing and Information Systems

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this …

Combinatorial Resultants In The Algebraic Rigidity Matroid, Goran Malić, Ileana Streinu

Computer Science: Faculty Publications

Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid CMn associated to the Cayley-Menger ideal for n points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from K4 graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we …

Exploring The Use Of Social Media To Infer Relationships Between Demographics, Psychographics And Vaccine Hesitancy, Abhimanyu Kapur

Computer Science Senior Theses

The growing popularity of social media as a platform to obtain information and share one's opinions on various topics makes it a rich source of information for research. In this study, we aimed to develop a framework to infer relationships between demographic and psychographic characteristics of a user and their opinion on a specific narrative - in this case, their stance on taking the COVID-19 vaccine. Twitter was the chosen platform due to the large USA user base and easily available data. Demographic traits included Race, Age, Gender, and Human-vs-Organization Status. Psychographic traits included the Big Five personality traits (Conscientiousness, …

Producing Easy-To-Verify Proofs Of Linearizability, Ugur Yavuz

Computer Science Senior Theses

Proofs of linearizability tend to be complex and lengthy, rendering their verification challenging for readers. We provide a novel technique to produce easy-to-verify proofs of linearizability, with the help of mechanical proof assistants. Specifically, we reduce the task of proving the correctness of a linearizable object implementation, to a proof of an inductive invariant of a slightly modified version of the implementation. As the latter is a task many mechanical proof systems (such as TLAPS) are well-suited to undertake, this reduction allows the verification of the proof by the reader, to only consist of a trivial syntactic check of whether …

A Survey Of Computer Graphics Facial Animation Methods: Comparing Traditional Approaches To Machine Learning Methods, Joseph A. Johnson

Master's Theses

Human communications rely on facial expression to denote mood, sentiment, and intent. Realistic facial animation of computer graphic models of human faces can be difficult to achieve as a result of the many details that must be approximated in generating believable facial expressions. Many theoretical approaches have been researched and implemented to create more and more accurate animations that can effectively portray human emotions. Even though many of these approaches are able to generate realistic looking expressions, they typically require a lot of artistic intervention to achieve a believable result. To reduce the intervention needed to create realistic facial animation, …

Witness For Two-Site Enabled Coordination, Sriram Priyatham Siram

Master's Projects

Many replicated data services utilize majority quorums to safely replicate data changes in the presence of server failures. Majority quorum-based services require a simple majority of the servers to be operational for the service to stay available. A key limitation of the majority quorum is that if a service is composed of just two servers, progress cannot be made even if a single server fails because the majority quorum size is also two. This is called the Two-Server problem. A problem similar to the Two-Server problem occurs when a service’s servers are spread across only two failure domains. Servers in …

Advancing The Ability To Predict Cognitive Decline And Alzheimer’S Disease Based On Genetic Variants Beyond Amyloid-Beta And Tau, Naveen Rawat

Master's Projects

A growing amount of neurodegenerative R&D is focused on identifying genomic- based explanations of AD that are beyond Amyloid-b and Tau. The proposed effort involves identifying some of the genomic variations, such as single nucleotide polymorphisms (SNPs), allele , chromosome, epigenetic contributors to MCI and AD that are beyond Aβ and Tau.

The project involves building a prediction model based on a support vector machine (SVM) classifier that takes into account the genomic variations and epigenetic factors to predict the early stage of mild cognitive impairment (MCI) and Alzheimer disease (AD). To achieve this, picking up important feature sets which …

Teaching Law And Artificial Intelligence, Brendan Johnson, Francis X. Shen

Minnesota Journal of Law, Science & Technology

No abstract provided.

Needles In A Haystack: How Pooling Can Control Error Rates In Noisy Tests, Arockia David Roy Kulandai, J. Stella, John Rose, Thomas Schwarz

Computer Science Faculty Research and Publications

Testing many individuals for a reasonably rare condition using imperfect, time consuming, and expensive tests can be facilitated by pooling. Pooling groups samples from different individuals that are then tested for the existence of a pathogen. An individual is diagnosed as a carrier if a threshold of the tests to which the individual contributed samples is positive. Our assumptions dictate a testing strategy that is not adaptive, with the exception of retesting positively diagnosed persons individually. Pooling is a standard proposal to stretch the supply of test kits. We show that it can also be used to control the false …

Towards Automated Software Evolution Of Data-Intensive Applications, Yiming Tang

Dissertations, Theses, and Capstone Projects

Recent years have witnessed an explosion of work on Big Data. Data-intensive applications analyze and produce large volumes of data typically terabyte and petabyte in size. Many techniques for facilitating data processing are integrated into data-intensive applications. API is a software interface that allows two applications to communicate with each other. Streaming APIs are widely used in today's Object-Oriented programming development that can support parallel processing. In this dissertation, an approach that automatically suggests stream code run in parallel or sequentially is proposed. However, using streams efficiently and properly needs many subtle considerations. The use and misuse patterns for stream …

Mechanism Design And Modeling To Analyze Complex Social Systems For Public Policy, Haripriya Chakraborty

Dissertations, Theses, and Capstone Projects

The study of complex systems is an important area of research. Many scenarios require the ability to simulate large multi-agent systems with minimal artificial assumptions. We are currently living in a world where the adoption of artificial intelligence (AI) in various areas is increasing rapidly. This, in turn, has serious consequences from a computational and policy perspective. The focus needs to be on designing systems that are not only computationally elegant and efficient but also ethical. The goal of this thesis is to examine some of the ways AI can be used to simulate complex social systems. In addition, we …

Learn Biologically Meaningful Representation With Transfer Learning, Di He

Dissertations, Theses, and Capstone Projects

Machine learning has made significant contributions to bioinformatics and computational biol­ogy. In particular, supervised learning approaches have been widely used in solving problems such as bio­marker identification, drug response prediction, and so on. However, because of the limited availability of comprehensively labeled and clean data, constructing predictive models in super­ vised settings is not always desirable or possible, especially when using data­hunger, red­hot learning paradigms such as deep learning methods. Hence, there are urgent needs to develop new approaches that could leverage more readily available unlabeled data in driving successful machine learning ap­ plications in this area.

In my dissertation, …

Metareasoning, Opportunistic Exploration, And Explanations For Autonomous Indoor Navigation, Raj Korpan

Dissertations, Theses, and Capstone Projects

Autonomous indoor navigation is an important task for mobile robots deployed without a map in real-world environments, such as museums or offices. While it travels, an autonomous robot navigator must contend with lack of prior knowledge, sensor noise, actuator error, and inquisitive people. This dissertation addresses these challenges with a cognitively-based hierarchical reasoning architecture that incorporates learning, exploration, reactivity, planning, heuristics, and explanations. Evaluation by simulation in large, complex, indoor environments shows that a robot controller can successfully navigate without a detailed map of every obstruction's location when it performs limited initial global exploration and plans in its learned spatial …

A Reinforcement Learning Approach To Vehicle Path Optimization In Urban Environments, Shamsa Abdulla Al Hassani

Theses

Road traffic management in metropolitan cities and urban areas, in general, is an important component of Intelligent Transportation Systems (ITS). With the increasing number of world population and vehicles, a dramatic increase in road traffic is expected to put pressure on the transportation infrastructure. Therefore, there is a pressing need to devise new ways to optimize the traffic flow in order to accommodate the growing needs of transportation systems. This work proposes to use an Artificial Intelligent (AI) method based on reinforcement learning techniques for computing near-optimal vehicle itineraries applied to Vehicular Ad-hoc Networks (VANETs). These itineraries are optimized based …

Assessing Real-Time Flow Experience In Human-Computer Interaction: An Electroencephalogram (Eeg) Study, Fiona Fui-Hoon Nah, Tejaswini Yelamanchili, Keng Siau, Langtao Chen

Research Collection School Of Computing and Information Systems

An optimal experience termed flow can be experienced by users who are deeply involved in human-computer interaction (HCI). The electroencephalogram (EEG) provides an innovative way to assess in real-time if users are approaching or experiencing the flow state in various applications of HCI. However, the current literature remains unclear and inconsistent with regard to the relationship between EEG activity and flow experience. The objective of this research is to assess EEG activity corresponding to the state of flow. A laboratory experiment was conducted to collect EEG data of the flow and other states (including baseline) in the context of HCI.

A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method For Efficient Optimization And Generalization, Pan Zhou, Xiao-Tong Yuan, Lin Zhouchen, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g. least squares and logistic/softmax regression. HSDMPG enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving minibatch of individual losses to estimate the original problem, and can efficiently minimize the sampled subproblems. For strongly convex loss of n components, HSDMPG attains an -optimization-error within O κ …

Gpu-Accelerated Graph Label Propagation For Real-Time Fraud Detection, Chang Ye, Yuchen Li, Bingsheng He, Zhao Li, Jianling Sun

Research Collection School Of Computing and Information Systems

Fraud detection is a pressing challenge for most financial and commercial platforms. In this paper, we study the processing pipeline of fraud detection in a large e-commerce platform of TaoBao. Graph label propagation (LP) is a core component in this pipeline to detect suspicious clusters from the user-interaction graph. Furthermore, the run-time of the LP component occupies 75% overhead of TaoBao’s automated detection pipeline. To enable real-time fraud detection, we propose a GPU-based framework, called GLP, to support large-scale LP workloads in enterprises. We have identified two key challenges when integrating GPU acceleration into TaoBao’s data processing pipeline: (1) programmability …

On M-Impact Regions And Standing Top-K Influence Problems, Bo Tang, Kyriakos Mouratidis, Mingji Han

Research Collection School Of Computing and Information Systems

In this paper, we study the ��-impact region problem (mIR). In a context where users look for available products with top-�� queries, mIR identifies the part of the product space that attracts the most user attention. Specifically, mIR determines the kind of attribute values that lead a (new or existing) product to the top-�� result for at least a fraction of the user population. mIR has several applications, ranging from effective marketing to product improvement. Importantly, it also leads to (exact and efficient) solutions for standing top-�� impact problems, which were previously solved heuristically only, or whose current solutions face …

Ultrapin: Inferring Pin Entries Via Ultrasound, Liu, Ximing, Robert H. Deng, Robert H. Deng

Research Collection School Of Computing and Information Systems

While PIN-based user authentication systems such as ATM have long been considered to be secure enough, they are facing new attacks, named UltraPIN, which can be launched from commodity smartphones. As a target user enters a PIN on a PIN-based user authentication system, an attacker may use UltraPIN to infer the PIN from a short distance (50 cm to 100 cm). In this process, UltraPIN leverages smartphone speakers to issue human-inaudible ultrasound signals and uses smartphone microphones to keep recording acoustic signals. It applies a series of signal processing techniques to extract high-quality feature vectors from low-energy and high-noise signals …

Evolutionary Generation Of Diversity In Embedded Binary Executables For Cyber Resiliency, Mitchell D. I. Hirschfeld

Theses and Dissertations

Hardening avionics systems against cyber attack is difficult and expensive. Attackers benefit from a "break one, break all" advantage due to the dominant mono-culture of automated systems. Also, undecidability of behavioral equivalence for arbitrary algorithms prevents the provable absence of undesired behaviors within the original specification. This research presents results of computational experiments using bio-inspired genetic programming to generate diverse implementations of executable software and thereby disrupt the mono-culture. Diversity is measured using the SSDeep context triggered piecewise hashing algorithm. Experiments are divided into two phases. Phase I explores the use of semantically-equivalent alterations that retain the specified behavior of …

Decreasing The Miss Rate And Eliminating The Performance Penalty Of A Data Filter Cache, Michael Stokes, David Whalley, Soner Onder

Michigan Tech Publications, Part 1

While data filter caches (DFCs) have been shown to be effective at reducing data access energy, they have not been adopted in processors due to the associated performance penalty caused by high DFC miss rates. In this article, we present a design that both decreases the DFC miss rate and completely eliminates the DFC performance penalty even for a level-one data cache (L1 DC) with a single cycle access time. First, we show that a DFC that lazily fills each word in a DFC line from an L1 DC only when the word is referenced is more energy-efficient than eagerly …

Pilltank, Lucas Chang, Hayden Tam, Aaron Teh, Krista Round

Electrical Engineering

Imagine an elderly family member, going through their daily routine of taking their pills. They find their pill box; however, they are having trouble identifying all the pills in there. Is there a name on the tablet? Can they read what it says? Do they just trust that the medication in their box is correct? How can they properly take care of themselves if they can not even confirm that what they are taking is the right medication? To combat this issue that many face, we present PillTank.

To decrease the risk of consuming the wrong medication, PillTank identifies the …

Real-Time Stylized Rendering For Large-Scale 3d Scenes, Jack Pietrok

Master's Theses

While modern digital entertainment has seen a major shift toward photorealism in animation, there is still significant demand for stylized rendering tools. Stylized, or non-photorealistic rendering (NPR), applications generally sacrifice physical accuracy for artistic or functional visual output. Oftentimes, NPR applications focus on extracting specific features from a 3D environment and highlighting them in a unique manner. One application of interest involves recreating 2D hand-drawn art styles in a 3D-modeled environment. This task poses challenges in the form of spatial coherence, feature extraction, and stroke line rendering. Previous research on this topic has also struggled to overcome specific performance bottlenecks, …

A Quantitative Argument For Autonomous Aerial Defense Overembedded Missile Systems To Thwart Cruise Threats, Andrew R. Davis

Theses and Dissertations

Given the high cost of missile defense systems, their ability to be overwhelmed, and rising tensions between the U.S. and adversaries in the Indo-Pacific region, a new modeled is proposed to investigate a new approach to missile defense. The Autonomous Aerial Defense Against Missiles (AADAM) system leverages reusable, small-scale UAVs to propose a cheaper, more effective system in defending against cruise missile threats. The aim of this system is to provide and additional layer in current missile defense strategies at lower-cost. This modeled system is found to outperform a modeled Patriot system in close-range interception of designated assets, with no …

The Effects Of Advanced Analytics And Machine Learning On The Transportation Of Natural Gas, Bj Stigall

Doctoral Dissertations and Projects

This qualitative single case study describes the effects of an advanced analytic and machine learning system (AAML) has on the transportation of natural gas pipelines and the causes for failure to fully utilize the advanced analytic and machine learning system. This study's guiding theory was the Unified Theory of Acceptance and Use of Technology (UTAUT) model and Transformation Leadership. The factors for failure to fully utilize AAML systems were studied, and the factors that made the AAML system successful were also examined. Data were collected through participant interviews. This study indicates that the primary factors for failure to fully utilize …

Detecting Receptivity For Mhealth Interventions In The Natural Environment, Varun Mishra, Florian Künzler, Jan-Niklas Kramer, Elgar Fleisch, Tobias Kowatsch, David Kotz

Dartmouth Scholarship

Just-In-Time Adaptive Intervention (JITAI) is an emerging technique with great potential to support health behavior by providing the right type and amount of support at the right time. A crucial aspect of JITAIs is properly timing the delivery of interventions, to ensure that a user is receptive and ready to process and use the support provided. Some prior works have explored the association of context and some user-specific traits on receptivity, and have built post-study machine-learning models to detect receptivity. For effective intervention delivery, however, a JITAI system needs to make in-the-moment decisions about a user's receptivity. To this end, …

Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze

Master's Theses

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2^n/2n²(log2n)²). This is an improvement over the best known algorithm, with a run time of 2ⁿn^O(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can …

An Economic Analysis Of Rebates Conditional On Positive Reviews, Jianqing Chen, Zhiling Guo, Jian Huang

Research Collection School Of Computing and Information Systems

Strategic sellers on some online selling platforms have recently been using a conditional-rebate strategy to manipulate product reviews under which only purchasing consumers who post positive reviews online are eligible to redeem the rebate. A key concern for the conditional rebate is that it can easily induce fake reviews, which might be harmful to consumers and society. We develop a microbehavioral model capturing consumers’ review-sharing benefit, review-posting cost, and moral cost of lying to examine the seller’s optimal pricing and rebate decisions. We derive three equilibria: the no-rebate, organic-review equilibrium; the low-rebate, boosted-authentic-review equilibrium; and the high-rebate, partially-fake-review equilibrium. We …

Incorrectness Logic For Graph Programs, Christopher M. Poskitt

Research Collection School Of Computing and Information Systems

Program logics typically reason about an over-approximation of program behaviour to prove the absence of bugs. Recently, program logics have been proposed that instead prove the presence of bugs by means of under-approximate reasoning, which has the promise of better scalability. In this paper, we present an under-approximate program logic for a nondeterministic graph programming language, and show how it can be used to reason deductively about program incorrectness, whether defined by the presence of forbidden graph structure or by finitely failing executions. We prove this 'incorrectness logic' to be sound and complete, and speculate on some possible future applications …