Theory and Algorithms Commons^™

Geoprune: Efficiently Matching Trips In Ride-Sharing Through Geometric Properties, Yixin Xu, Jianzhong Qi, Renata Borovica-Gajic

Research Collection School Of Computing and Information Systems

On-demand ride-sharing is rapidly growing. Matching trip requests to vehicles efficiently is critical for the service quality of ride-sharing. To match trip requests with vehicles, a prune-And-select scheme is commonly used. The pruning stage identifies feasible vehicles that can satisfy the trip constraints (e.g., trip time). The selection stage selects the optimal one(s) from the feasible vehicles. The pruning stage is crucial to lowering the complexity of the selection stage and to achieve efficient matching. We propose an effective and efficient pruning algorithm called GeoPrune. GeoPrune represents the time constraints of trip requests using circles and ellipses, which can be …

Enhancing The Performance Of Ir-Based Traceability Recovery Of Requirement Artifacts Using Noun Phrases, Dafaalla Abdelrahman Mashahi Khalafalla

Student Works (2020-2029)

Requirement traceability can be considered as a measure of software quality to help achieve validation, verification, and reusability. Neglecting traceability leads to less maintainable software. Creating traceability links after-the-fact, known as traceability recovery, is a tedious and time-consuming process when it is done manually. Therefore, information retrieval (IR) methods have been used to automatically identify traceability links between the artifacts. However, as a result of limitations of the software engineer and the IR techniques, the performance of the IR methods is negatively affected. There is no IR method that is able to recover traceability links between artifacts with high precision …

Unsupervised Monocular Depth Estimation With Multi-Scale Structural Similarity Powered Loss Function, Kohan Ali

Student Works (2020-2029)

Depth Estimation refers to a set of techniques and algorithms that aim to obtain a representation of spatial information of a scene. Nowadays specific hardware such as sensors, radars and multiple-view-recording cameras are being used in order to acquire depth data of a scene. Modern approaches use deep learning to address this task by trying to learn depth information in a supervised manner. However, this approach requires a large amount ground-truth data for a particular scene so that a model can be trained successfully. Also preparing ground-truth data for a range of environments is a challenging and expensive task to …

Efficient Vehicle Routing Optimization For Autistic Users, Mohammed Shabalah Abdulrahman Hasan

Student Works (2020-2029)

In recent years, daily life without a vehicle would be impossible. As an inevitable result, the number of vehicles on the road increases day by day in various large cities around the world. The increased number of vehicles is a big concern because it causes a lot of traffic congestions, especially during peak hours. Besides, there has been a rapid rise of on-demand Ride-Hailing Services (RHSs), such as Grab, Uber, EzCab, and MyCar, etc. This allows passengers with smartphones to place trip requests and assign them to drivers according to requester’s location and drivers' availability. In consequence, efficient routing algorithms …

Translating Counting Problems Into Computable Language Expressions, Zach Prescott

Theses

The realm of automated problem solving is a relatively new field, even in the context of natural language processing. One area where this is often demonstrated is that of creating a program that can solve word problems. The program must understand the problem, perform some processing, and then convey this information to a user in a way that is accessible and understandable. There has been quite a lot of progress in this area with simpler problems. However, when it comes to understanding problems that involve a level of NLP, the results are not conclusive. In this paper, we would like …

Design And Implementation Of A Deterministic And Nondeterministic Finite Automaton Simulator, Camron C. Dennler

Computer Science and Software Engineering

The purpose of this project is to assist students in visualizing and understanding the structure and operation of deterministic and nondeterministic finite automata. This software achieves this purpose by providing students with the ability to build, modify, and test automata in an intuitive environment. This enables a simple and efficient avenue for experimentation, which upholds the Cal Poly ideal of Learning by Doing.

Readers of this report should be familiar with basic concepts in the theory of finite state machines; a general understanding of object-oriented programming is also necessary.

Novel Fast Algorithms For Low Rank Matrix Approximation, John T. Svadlenka

Dissertations, Theses, and Capstone Projects

Recent advances in matrix approximation have seen an emphasis on randomization techniques in which the goal was to create a sketch of an input matrix. This sketch, a random submatrix of an input matrix, having much fewer rows or columns, still preserves its relevant features. In one of such techniques random projections approximate the range of an input matrix. Dimension reduction transforms are obtained by means of multiplication of an input matrix by one or more matrices which can be orthogonal, random, and allowing fast multiplication by a vector. The Subsampled Randomized Hadamard Transform (SRHT) is the most popular among …

Towards Distributed Node Similarity Search On Graphs, Tianming Zhang, Yunjun Gao, Baihua Zheng, Lu Chen, Shiting Wen, Wei Guo

Research Collection School Of Computing and Information Systems

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly …

Optimal Control Of A Rumor Propagation Model With Different Propagation Degrees In Social Network, Yingfeng Tang

Student Works (2020-2029)

Rumor is a social interaction of information, and its development is of great significance to human beings. In this paper, by studying the D K model and a rumor model spreading with rumor latent period, deduces the rumor model with differe nt propagation degrees of the spreaders. The two equilibrium points in the system are found through derivation. In real life, enterprises often ignore the reasonable planning of the cost of rumor control. By means of public education and media technology u sing by the authorities to debunk rumors, an optimal control problem i s established. The Pontryagin’s maximum principle …

Quantum Random Walk Search And Grover's Algorithm - An Introduction And Neutral-Atom Approach, Anna Maria Houk

Physics

In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using neutral-atom (also …

Evaluating Driving Performance Of A Novel Behavior Planning Model On Connected Autonomous Vehicles, Keyur Shah

Honors Scholar Theses

Many current algorithms and approaches in autonomous driving attempt to solve the "trajectory generation" or "trajectory following” problems: given a target behavior (e.g. stay in the current lane at the speed limit or change lane), what trajectory should the vehicle follow, and what inputs should the driving agent apply to the throttle and brake to achieve this trajectory? In this work, we instead focus on the “behavior planning” problem—specifically, should an autonomous vehicle change lane or keep lane given the current state of the system?

In addition, current theory mainly focuses on single-vehicle systems, where vehicles do not communicate with …

Accelerating The Information-Theoretic Approach Of Community Detection Using Distributed And Hybrid Memory Parallel Schemes, Md Abdul Motaleb Faysal

LSU New Orleans Theses and Dissertations

There are several approaches for discovering communities in a network (graph). Despite being approximating in nature, discovering communities based on the laws of Information Theory has a proven standard of accuracy. The information-theoretic algorithm known as Infomap developed a decade ago for detecting communities, did not foresee the tremendous growth of social networking, multimedia, and massive information boom. To discover communities in massive networks, we have designed a distributed-memory-parallel Infomap in the MPI framework. Our design reaches scalability of over 500 processes capable of processing networks with millions of edges while maintaining quality comparable to the sequential Infomap. We have …

Higher-Order Link Prediction Using Graph Embeddings, Neeraj Chavan

Master's Projects

Link prediction is an emerging field that predicts if two nodes in a network are likely to be connected or not in the near future. Networks model real-world systems using pairwise interactions of nodes. However, many of these interactions may involve more than two nodes or entities simultaneously. For example, social interactions often occur in groups of people, research collaborations are among more than two authors, and biological networks describe interactions of a group of proteins. An interaction that consists of more than two entities is called a higher-order structure. Predicting the occurrence of such higher-order structures helps us solve …

Rehearsal Scheduling Problem, Thuan Bao

Master's Projects

Scheduling is a common task that plays a crucial role in many industries such as manufacturing or servicing. In a competitive environment, effective scheduling is one of the key factors to reduce cost and increase productivity. Therefore, scheduling problems have been studied by many researchers over the past thirty years. Rehearsal scheduling problem (RSP) is similar to the popular resource-constrained project scheduling problem (RCPSP); however, it does not have activity precedence constraints and the resources’ availabilities are not fixed during processing time. RSP can be used to schedule rehearsal in theatre industry or to schedule group scheduling when each member …

Graphical Representation Of Text Semantics, Karl Kevin Tiba Fossoh

Master of Science in Computer Science Theses

A text is a set of words conveying a particular semantic based on their order, representation and structure. Those elements can be associated through a different set of interpretations, based on frequency and proportionality. The problem with context is that numbers do not help understand the semantics and fall short to convey the message of the text. The graphical representation of text semantics focuses on the conversion of text to images. Contrarily to word clouds that simply produce frequency mapping of words within the text and topic models that essentially give context to word frequencies and proportionalities, images keep intact …

Csp-Completeness And Its Applications, Alexander Durgin

McKelvey School of Engineering Graduate Student Theses & Dissertations

We build off of previous ideas used to study both reductions between CSPrefutation problems and improper learning and between CSP-refutation problems themselves to expand some hardness results that depend on the assumption that refuting random CSP instances are hard for certain choices of predicates (like k-SAT). First, we are able argue the hardness of the fundamental problem of learning conjunctions in a one-sided PAC-esque learning model that has appeared in several forms over the years. In this model we focus on producing a hypothesis that foremost guarantees a small false-positive rate while minimizing the false-negative rate for such hypotheses. Further, …

Voxel Optimization, Scott Bengs

Student Academic Conference

Voxel Optimization This poster presentation covers optimization for voxels. They can be thought of as three dimensional pixels. Vo coming from volume and xel from pixel. Voxels are just values placed in a 3D grid. Voxels have many interesting uses in the medical and scientific field, especially in geology. One use in computer science is storing world information for video games or graphical applications. One very popular example is Minecraft, a game that allows all of the world to be changed, that uses cube shaped voxels. The first topic will be on the naive approach of building a model from …

The Theory Of Cryptography In Bitcoin, Can Hong

Mathematics Senior Capstone Papers

Bitcoin is a well known virtual currency, or cryptocurrency. It was created by a group of people using the name Satoshi Nakamoto in 2008. Currently, many people are utilizing Bitcoin for personal gains and transactions. To keep transactions secure requires techniques from modern cryptography. In this paper, we explain certain aspects of the cryptography of Bitcoin. We are going to discuss two components of the cryptography of Bitcoin—hash functions and signatures. We will describe what the hash function and signature are, give some examples of hash functions, and discuss certain criteria that good hash functions should satisfy.

Predictive Modeling Of Asynchronous Event Sequence Data, Jin Shang

LSU Doctoral Dissertations

Large volumes of temporal event data, such as online check-ins and electronic records of hospital admissions, are becoming increasingly available in a wide variety of applications including healthcare analytics, smart cities, and social network analysis. Those temporal events are often asynchronous, interdependent, and exhibiting self-exciting properties. For example, in the patient's diagnosis events, the elevated risk exists for a patient that has been recently at risk. Machine learning that leverages event sequence data can improve the prediction accuracy of future events and provide valuable services. For example, in e-commerce and network traffic diagnosis, the analysis of user activities can be …

Generating Acoustic Projections Using 3d Models, Jake A. Brazelton

Senior Honors Projects, 2020-current

Raytracing is used in commercial graphics engines most commonly for lighting effects, but it also has many uses when it comes to acoustic simulation. Adopted directly from these computer graphics programs, the formulas presented herein enable the visualization of acoustic intensity levels throughout a 3D space using Python 3 and the OpenGL library. In addition to visualization, they also provide the ability to calculate the reverberation time and critical distance of an enclosed space in relation to its size and material makeup. The described application bundles all of these components together in a Qt5 application that allows users to view …