Theory and Algorithms Commons^™

List, Sample, And Count, Ali Assarpour

Dissertations, Theses, and Capstone Projects

Counting plays a fundamental role in many scientific fields including chemistry, physics, mathematics, and computer science. There are two approaches for counting, the first relies on analytical tools to drive closed form expression, while the second takes advantage of the combinatorial nature of the problem to construct an algorithm whose output is the number of structures. There are many algorithmic techniques for counting, they cover the explicit approach of counting by listing to the approximate approach of counting by sampling.

This thesis looks at counting three sets of objects. First, we consider a subclass of boolean functions that are monotone. …

Rationality And Efficient Verifiable Computation, Matteo Campanelli

Dissertations, Theses, and Capstone Projects

In this thesis, we study protocols for delegating computation in a model where one of the parties is rational. In our model, a delegator outsources the computation of a function f on input x to a worker, who receives a (possibly monetary) reward. Our goal is to design very efficient delegation schemes where a worker is economically incentivized to provide the correct result f(x). In this work we strive for not relying on cryptographic assumptions, in particular our results do not require the existence of one-way functions.

We provide several results within the framework of rational proofs introduced by Azar …

Question-Guided Hybrid Convolution For Visual Question Answering, Peng Gao, Pan Lu, Hongsheng Li, Shuang Li, Yikang Li, Steven C. H. Hoi, Xiaogang Wang

Research Collection School Of Computing and Information Systems

In this paper, we propose a novel Question-Guided Hybrid Convolution (QGHC) network for Visual Question Answering (VQA). Most state-of-the-art VQA methods fuse the high-level textual and visual features from the neural network and abandon the visual spatial information when learning multi-modal features.To address these problems, question-guided kernels generated from the input question are designed to convolute with visual features for capturing the textual and visual relationship in the early stage. The question-guided convolution can tightly couple the textual and visual information but also introduce more parameters when learning kernels. We apply the group convolution, which consists of question-independent kernels and …

The Effectiveness Of Using Diversity To Select Multiple Classifier Systems With Varying Classification Thresholds, Harris K. Butler Iv, Mark A. Friend, Kenneth W. Bauer, Trevor J. Bihl

Faculty Publications

In classification applications, the goal of fusion techniques is to exploit complementary approaches and merge the information provided by these methods to provide a solution superior than any single method. Associated with choosing a methodology to fuse pattern recognition algorithms is the choice of algorithm or algorithms to fuse. Historically, classifier ensemble accuracy has been used to select which pattern recognition algorithms are included in a multiple classifier system. More recently, research has focused on creating and evaluating diversity metrics to more effectively select ensemble members. Using a wide range of classification data sets, methodologies, and fusion techniques, current diversity …

Transferring Time-Series Discrete Choice To Link-Based Route Choice In Space: Estimating Vehicle Type Preference Using Recursive Logit Model, Fabian Bastin, Yan Liu, Cinzia Cirillo, Tien Mai

Research Collection School Of Computing and Information Systems

This paper considers a sequential discrete choice problem in a time domain, formulated and solved as a route choice problem in a space domain. Starting from a dynamic specification of time-series discrete choices, we show how it is transferrable to link-based route choices that can be formulated by a finite path choice multinomial logit model. This study establishes that modeling sequential choices over time and in space are equivalent as long as the utility of the choice sequence is additive over the decision steps, the link-specific attributes are deterministic, and the decision process is Markovian. We employ the recursive logit …

Manana: A Generalized Heuristic Scoring Approach For Concept Map Analysis As Applied To Cybersecurity Education, Sharon Elizabeth Blake Gatto

LSU New Orleans Theses and Dissertations

Concept Maps (CMs) are considered a well-known pedagogy technique in creating curriculum, educating, teaching, and learning. Determining comprehension of concepts result from comparisons of candidate CMs against a master CM, and evaluate "goodness". Past techniques for comparing CMs have revolved around the creation of a subjective rubric. We propose a novel CM scoring scheme called MAnanA based on a Fuzzy Similarity Scaling (FSS) score to vastly remove the subjectivity of the rubrics in the process of grading a CM. We evaluate our framework against a predefined rubric and test it with CM data collected from the Introduction to …

Cyber Anomaly Detection: Using Tabulated Vectors And Embedded Analytics For Efficient Data Mining, Robert J. Gutierrez, Kenneth W. Bauer, Bradley C. Boehmke, Cade M. Saie, Trevor J. Bihl

Faculty Publications

Firewalls, especially at large organizations, process high velocity internet traffic and flag suspicious events and activities. Flagged events can be benign, such as misconfigured routers, or malignant, such as a hacker trying to gain access to a specific computer. Confounding this is that flagged events are not always obvious in their danger and the high velocity nature of the problem. Current work in firewall log analysis is manual intensive and involves manpower hours to find events to investigate. This is predominantly achieved by manually sorting firewall and intrusion detection/prevention system log data. This work aims to improve the ability of …

Expected Length Of The Longest Chain In Linear Hashing, Pongthip Srivarangkul, Hemanta K. Maji

The Summer Undergraduate Research Fellowship (SURF) Symposium

Hash table with chaining is a data structure that chains objects with identical hash values together with an entry or a memory address. It works by calculating a hash value from an input then placing the input in the hash table entry. When we place two inputs in the same entry, they chain together in a linear linked list. We are interested in the expected length of the longest chain in linear hashing and methods to reduce the length because the worst-case look-up time is directly proportional to it.

The linear hash function used to calculate hash value is defined …

A Divide-And-Conquer Approach To Syntax-Guided Synthesis, Peiyuan Shen, Xiaokang Qiu

The Summer Undergraduate Research Fellowship (SURF) Symposium

Program synthesis aims to generate programs automatically from user-provided specifications. One critical research thrust is called Syntax-Guideds Synthesis. In addition to semantic specifications, the user should also provide a syntactic template of the desired program, which helps the synthesizer reduce the search space. The traditional symbolic approaches, such as CounterExample-Guided Inductive Synthesis (CEGIS) framework, does not scale to large search spaces. The goal of this project is to explore a compositional, divide-n-conquer approach that heuristically divides the synthesis task into subtasks and solves them separately. The idea is to decompose the function to be synthesized by creating a set of …

Bayesian Analytical Approaches For Metabolomics : A Novel Method For Molecular Structure-Informed Metabolite Interaction Modeling, A Novel Diagnostic Model For Differentiating Myocardial Infarction Type, And Approaches For Compound Identification Given Mass Spectrometry Data., Patrick J. Trainor

Electronic Theses and Dissertations

Metabolomics, the study of small molecules in biological systems, has enjoyed great success in enabling researchers to examine disease-associated metabolic dysregulation and has been utilized for the discovery biomarkers of disease and phenotypic states. In spite of recent technological advances in the analytical platforms utilized in metabolomics and the proliferation of tools for the analysis of metabolomics data, significant challenges in metabolomics data analyses remain. In this dissertation, we present three of these challenges and Bayesian methodological solutions for each. In the first part we develop a new methodology to serve a basis for making higher order inferences in metabolomics, …

Online Spatio-Temporal Matching In Stochastic And Dynamic Domains, Meghna Lowalekar, Pradeep Varakantham, Patrick Jaillet

Research Collection School Of Computing and Information Systems

Online spatio-temporal matching of servers/services to customers is a problem that arises at a large scale in many domains associated with shared transportation (e.g., taxis, ride sharing, super shuttles, etc.) and delivery services (e.g., food, equipment, clothing, home fuel, etc.). A key characteristic of these problems is that the matching of servers/services to customers in one stage has a direct impact on the matching in the next stage. For instance, it is efficient for taxis to pick up customers closer to the drop off point of the customer from the first stage of matching. Traditionally, greedy/myopic approaches have been adopted …

Exact Processing Of Uncertain Top-K Queries In Multi-Criteria Settings, Kyriakos Mouratidis, Bo Tang

Research Collection School Of Computing and Information Systems

Traditional rank-aware processing assumes a dataset that contains available options to cover a specific need (e.g., restaurants, hotels, etc) and users who browse that dataset via top-k queries with linear scoring functions, i.e., by ranking the options according to the weighted sum of their attributes, for a set of given weights. In practice, however, user preferences (weights) may only be estimated with bounded accuracy, or may be inherently uncertain due to the inability of a human user to specify exact weight values with absolute accuracy. Motivated by this, we introduce the uncertain top-k query (UTK). Given uncertain preferences, that is, …

Embedding Wordnet Knowledge For Textual Entailment, Yunshi Lan, Jing Jiang

Research Collection School Of Computing and Information Systems

In this paper, we study how we can improve a deep learning approach to textual entailment by incorporating lexical entailment relations from WordNet. Our idea is to embed the lexical entailment knowledge contained in WordNet in specially-learned word vectors, which we call “entailment vectors.” We present a standard neural network model and a novel set-theoretic model to learn these entailment vectors from word pairs with known lexical entailment relations derived from WordNet. We further incorporate these entailment vectors into a decomposable attention model for textual entailment and evaluate the model on the SICK and the SNLI dataset. We find that …

Iterated Local Search Algorithm For The Capacitated Team Orienteering Problem, Aldy Gunawan, Kien Ming Ng, Vincent F. Yu, Gordy Adiprasetyo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper focuses on a recent variant of the Orienteering Problem (OP), namely the Capacitated Team Orienteering Problem (CTOP). In this problem, each node is associated with a demand that needs to be satisfied and a score that need to be collected. Given a set of homogeneous fleet of vehicles, the main objective is to find a path for each available vehicle in order to maximize the total score, without violating the capacity and time budget of each vehicle. We propose an Iterated Local Search algorithm that has been applied in solving various variants of the OP. We propose two …

An Algorithmic Approach To Creating Effective Study Groups Using A Smart Phone App, Kelvin J. Rosado-Ayala

Honors College Theses

For many students entering college, meeting new people and studying are a common struggle. Study groups are generally recommended, especially if the groups are comprised of members with complementary personality traits. But the challenge still remains, how do freshmen or transfer students find and form these heterogeneous study groups. In order to help alleviate this issue, an Android application was developed to automatically create study groups for students. Using basic information provided by students upon registration, the algorithm is able to automatically find matching group members. The application was designed using an agile life cycle model over the course of …

Data Center Application Security: Lateral Movement Detection Of Malware Using Behavioral Models, Harinder Pal Singh Bhasin, Elizabeth Ramsdell, Albert Alva, Rajiv Sreedhar, Medha Bhadkamkar

SMU Data Science Review

Data center security traditionally is implemented at the external network access points, i.e., the perimeter of the data center network, and focuses on preventing malicious software from entering the data center. However, these defenses do not cover all possible entry points for malicious software, and they are not 100% effective at preventing infiltration through the connection points. Therefore, security is required within the data center to detect malicious software activity including its lateral movement within the data center. In this paper, we present a machine learning-based network traffic analysis approach to detect the lateral movement of malicious software within the …

Supervised Machine Learning Bot Detection Techniques To Identify Social Twitter Bots, Phillip George Efthimion, Scott Payne, Nicholas Proferes

SMU Data Science Review

In this paper, we present novel bot detection algorithms to identify Twitter bot accounts and to determine their prevalence in current online discourse. On social media, bots are ubiquitous. Bot accounts are problematic because they can manipulate information, spread misinformation, and promote unverified information, which can adversely affect public opinion on various topics, such as product sales and political campaigns. Detecting bot activity is complex because many bots are actively trying to avoid detection. We present a novel, complex machine learning algorithm utilizing a range of features including: length of user names, reposting rate, temporal patterns, sentiment expression, followers-to-friends ratio, …

Machine Learning To Predict College Course Success, Anthony R.Y. Dalton, Justin Beer, Sriharshasai Kommanapalli, James S. Lanich Ph.D.

SMU Data Science Review

In this paper, we present an analysis of the predictive ability of machine learning on the success of students in college courses in a California Community College. The California Legislature passed assembly bill 705 in order to place students in non-remedial coursework, based on high school transcripts, to increase college completion. We utilize machine learning methods on de-identified student high school transcript data to create predictive algorithms on whether or not the student will be successful in college-level English and Mathematics coursework. To satisfy the bill’s requirements, we first use exploratory data analysis on applicable transcript variables. Then we use …

Compact Hardware Implementation Of A Sha-3 Core For Wireless Body Sensor Networks, Yi Yang, Debiao He, Neeraj Kumar, Sherali Zeadally

Information Science Faculty Publications

One of the most important Internet of Things applications is the wireless body sensor network (WBSN), which can provide universal health care, disease prevention, and control. Due to large deployments of small scale smart sensors in WBSNs, security, and privacy guarantees (e.g., security and safety-critical data, sensitive private information) are becoming a challenging issue because these sensor nodes communicate using an open channel, i.e., Internet. We implement data integrity (to resist against malicious tampering) using the secure hash algorithm 3 (SHA-3) when smart sensors in WBSNs communicate with each other using the Internet. Due to the limited resources (i.e., storage, …

Time Advancement And Bounds Intersection Checking For Faster Broad-Phase Collision Detection Of Paired Object Trajectories, Proceso L. Fernandez Jr, Mary Aveline Germar

Department of Information Systems & Computer Science Faculty Publications

For self-driving mechanisms, the motion planning requires a reasonably fast algorithm for collision detection along the trajectories. We present three algorithms for the detection of collision among objects with predefined trajectories. The first algorithm uses the intersection of the path’s bounding box. The second algorithm sequentially checks for intersection between each pair of corresponding axis-aligned bounding boxes (AABB) from the trajectories of the two paths. Lastly, the latter algorithm is modified using iterative time advancement to an estimated earliest possible collision time. Simulation experiments on a variety of pair trajectories demonstrate a significant speedup of the proposed algorithms over the …