Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons

Open Access. Powered by Scholars. Published by Universities.®

1186 Full-Text Articles 1364 Authors 209497 Downloads 86 Institutions

All Articles in Theory and Algorithms

Faceted Search

1186 full-text articles. Page 1 of 43.

Logic Circuits From Zero Forcing, Daniel Burgarth, Vittorio Giovannetti, Leslie Hogben, Simone Severini, Michael Young 2017 Aberystwyth University

Logic Circuits From Zero Forcing, Daniel Burgarth, Vittorio Giovannetti, Leslie Hogben, Simone Severini, Michael Young

Leslie Hogben

We design logic circuits based on the notion of zero forcing on graphs; each gate of the circuits is a gadget in which zero forcing is performed. We show that such circuits can evaluate every monotone Boolean function. By using two vertices to encode each logical bit, we obtain universal computation. We also highlight a phenomenon of “back forcing” as a property of each function. Such a phenomenon occurs in a circuit when the input of gates which have been already used at a given time step is further modified by a computation actually performed at a later stage. Finally ...


Optimizing Campus Mobility With A Focus On Sustainability: A Graph Theory Approach To Intra-Campus Transportation Networks, Quinn M. Nelson 2017 Quinn Nelson

Optimizing Campus Mobility With A Focus On Sustainability: A Graph Theory Approach To Intra-Campus Transportation Networks, Quinn M. Nelson

Student Research and Creative Activity Fair

The idea of public transportation is supported by most in theory but often heavily criticized by users when put into application. There are common tensions that are related to public transportation, as described by frequent users: unreliable, too crowded, and slow. The University of Nebraska-Omaha (UNO) is a growing metropolitan institution that uses a shuttle system to transport students among their three campuses daily. As of 2015, the current total student enrollment is approximately 16,000; UNO plans to enroll 20,000 students by 2020. The expected student growth is also reflected by the current construction of new buildings and ...


Metric Similarity Joins Using Mapreduce, Yunjun GAO, Keyu YANG, Lu CHEN, Baihua ZHENG, Gang CHEN, Chun CHEN 2017 Zhejiang University

Metric Similarity Joins Using Mapreduce, Yunjun Gao, Keyu Yang, Lu Chen, Baihua Zheng, Gang Chen, Chun Chen

Research Collection School Of Information Systems

Given two object sets Q and O , a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning, data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the ...


Learning Convolutional Neural Network To Maximize Pos@Top Performance Measure, 2017 Selected Works

Learning Convolutional Neural Network To Maximize Pos@Top Performance Measure

KEPING WU

In the machine learning problems, the performance measure is used to evaluate the machine learning models. Recently, the number positive data points ranked at the top positions (Pos@Top) has been a popular performance measure in the machine learning community. In this paper, we propose to learn a convolutional neural network (CNN) model to maximize the Pos@Top performance measure. The CNN model is used to represent the multi-instance data point, and a classifier function is used to predict the label from the its CNN representation. We propose to minimize the loss function of Pos@Top over a training set ...


Alternating Direction Method Of Multipliers For Penalized Zero-Variance Discriminant Analysis, Brendan P.W. Ames, Mingyi Hong 2017 University of Alabama - Tuscaloosa

Alternating Direction Method Of Multipliers For Penalized Zero-Variance Discriminant Analysis, Brendan P.W. Ames, Mingyi Hong

Mingyi Hong

We consider the task of classification in the high dimensional setting where the number of features of the given data is significantly greater than the number of observations. To accomplish this task, we propose a heuristic, called sparse zero-variance discriminant analysis, for simultaneously performing linear discriminant analysis and feature selection on high dimensional data. This method combines classical zero-variance discriminant analysis, where discriminant vectors are identified in the null space of the sample within-class covariance matrix, with penalization applied to induce sparse structures in the resulting vectors. To approximately solve the resulting nonconvex problem, we develop a simple algorithm based ...


Exploring Representativeness And Informativeness For Active Learning, Bo DU, Zengmao WANG, Lefei ZHANG 2017 Singapore Management University

Exploring Representativeness And Informativeness For Active Learning, Bo Du, Zengmao Wang, Lefei Zhang

Research Collection School Of Information Systems

How can we find a general way to choose the most suitable samples for training a classifier? Even with very limited prior information? Active learning, which can be regarded as an iterative optimization procedure, plays a key role to construct a refined training set to improve the classification performance in a variety of applications, such as text analysis, image recognition, social network modeling, etc. Although combining representativeness and informativeness of samples has been proven promising for active sampling, state-of-the-art methods perform well under certain data structures. Then can we find a way to fuse the two active sampling criteria without ...


Discovering Historic Traffic-Tolerant Paths In Road Networks, Pui Hang LI, Man Lung YIU, Kyriakos MOURATIDIS 2017 Singapore Management University

Discovering Historic Traffic-Tolerant Paths In Road Networks, Pui Hang Li, Man Lung Yiu, Kyriakos Mouratidis

Research Collection School Of Information Systems

Historic traffic information is valuable in transportation analysis and planning, e.g., evaluating the reliability of routes for representative source-destination pairs. Also, it can be utilized to provide efficient and effective route-search services. In view of these applications, we propose the k traffic-tolerant paths (TTP) problem on road networks, which takes a source-destination pair and historic traffic information as input, and returns k paths that minimize the aggregate (historic) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to find. First, we propose an exact algorithm with effective ...


Fast Fourier Transforms Over Prime Fields Of Large Characteristic And Their Implementation On Graphics Processing Units, Davood Mohajerani 2016 The University of Western Ontario

Fast Fourier Transforms Over Prime Fields Of Large Characteristic And Their Implementation On Graphics Processing Units, Davood Mohajerani

Electronic Thesis and Dissertation Repository

Prime field arithmetic plays a central role in computer algebra and supports computation in Galois fields which are essential to coding theory and cryptography algorithms. The prime fields that are used in computer algebra systems, in particular in the implementation of modular methods, are often of small characteristic, that is, based on prime numbers that fit on a machine word. Increasing precision beyond the machine word size can be done via the Chinese Remaindering Theorem or Hensel Lemma. In this thesis, we consider prime fields of large characteristic, typically fitting on n machine words, where n is a power of ...


Analysis Of 3d Cone-Beam Ct Image Reconstruction Performance On A Fpga, Devin Held 2016 The University of Western Ontario

Analysis Of 3d Cone-Beam Ct Image Reconstruction Performance On A Fpga, Devin Held

Electronic Thesis and Dissertation Repository

Efficient and accurate tomographic image reconstruction has been an intensive topic of research due to the increasing everyday usage in areas such as radiology, biology, and materials science. Computed tomography (CT) scans are used to analyze internal structures through capture of x-ray images. Cone-beam CT scans project a cone-shaped x-ray to capture 2D image data from a single focal point, rotating around the object. CT scans are prone to multiple artifacts, including motion blur, streaks, and pixel irregularities, therefore must be run through image reconstruction software to reduce visual artifacts. The most common algorithm used is the Feldkamp, Davis, and ...


Answering Why-Not And Why Questions On Reverse Top-K Queries, Qing LIU, Yunjun GAO, Gang CHEN, Baihua ZHENG, Linlin ZHOU 2016 Zhejiang University

Answering Why-Not And Why Questions On Reverse Top-K Queries, Qing Liu, Yunjun Gao, Gang Chen, Baihua Zheng, Linlin Zhou

Research Collection School Of Information Systems

Why-not and why questions can be posed by database users to seek clarifications on unexpected query results. Specifically, why-not questions aim to explain why certain expected tuples are absent from the query results, while why questions try to clarify why certain unexpected tuples are present in the query results. This paper systematically explores the why-not and why questions on reverse top-k queries, owing to its importance in multi-criteria decision making. We first formalize why-not questions on reverse top-k queries, which try to include the missing objects in the reverse top-k query results, and then, we propose a unified framework called ...


What Is Answer Set Programming To Propositional Satisfiability, Yuliya Lierler 2016 University of Nebraska at Omaha

What Is Answer Set Programming To Propositional Satisfiability, Yuliya Lierler

Yuliya Lierler

Propositional satisfiability  (or satisfiability) and answer set programming are two closely related subareas of Artificial Intelligence that are used to model and solve difficult combinatorial search problems. Satisfiability solvers and answer set solvers  are the software systems that  find  satisfying interpretations and answer sets for given propositional formulas and logic programs, respectively. These systems are closely related in their common design patterns. In satisfiability, a propositional formula is used to encode problem specifications in a way that its satisfying interpretations correspond to the solutions of the problem. To find solutions to a problem it is then sufficient to use a ...


Network Inference Driven Drug Discovery, Gergely Zahoránszky-Kőhalmi, Tudor I. Oprea MD, PhD, Cristian G. Bologa PhD, Subramani Mani MD, PhD, Oleg Ursu PhD 2016 University of New Mexico School of Medicine

Network Inference Driven Drug Discovery, Gergely Zahoránszky-Kőhalmi, Tudor I. Oprea Md, Phd, Cristian G. Bologa Phd, Subramani Mani Md, Phd, Oleg Ursu Phd

Biomedical Sciences ETDs

The application of rational drug design principles in the era of network-pharmacology requires the investigation of drug-target and target-target interactions in order to design new drugs. The presented research was aimed at developing novel computational methods that enable the efficient analysis of complex biomedical data and to promote the hypothesis generation in the context of translational research. The three chapters of the Dissertation relate to various segments of drug discovery and development process.

The first chapter introduces the integrated predictive drug discovery platform „SmartGraph”. The novel collaborative-filtering based algorithm „Target Based Recommender (TBR)” was developed in the framework of this ...


Marim: Mobile Augmented Reality For Interactive Manuals, Tam Nguyen, Dorothy Tan, Bilal Mirza, Jose Sepulveda 2016 University of Dayton

Marim: Mobile Augmented Reality For Interactive Manuals, Tam Nguyen, Dorothy Tan, Bilal Mirza, Jose Sepulveda

Tam Nguyen

In this work, we present a practical system which uses mobile devices for interactive manuals. In particular, there are two modes provided in the system, namely, expert/trainer and trainee modes. Given the expert/trainer editor, experts design the step-by-step interactive manuals. For each step, the experts capture the images by using phones/tablets and provide visual instructions such as interest regions, text, and action animations. In the trainee mode, the system utilizes the existing object detection and tracking algorithms to identify the step scene and retrieve the respective instruction to be displayed on the mobile device. The trainee then ...


Large Scale Data Mining For It Service Management, Chunqiu Zeng 2016 Florida International University

Large Scale Data Mining For It Service Management, Chunqiu Zeng

FIU Electronic Theses and Dissertations

More than ever, businesses heavily rely on IT service delivery to meet their current and frequently changing business requirements. Optimizing the quality of service delivery improves customer satisfaction and continues to be a critical driver for business growth. The routine maintenance procedure plays a key function in IT service management, which typically involves problem detection, determination and resolution for the service infrastructure.

Many IT Service Providers adopt partial automation for incident diagnosis and resolution where the operation of the system administrators and automation operation are intertwined. Often the system administrators' roles are limited to helping triage tickets to the processing ...


Finding Causality And Responsibility For Probabilistic Reverse Skyline Query Non-Answers, Qing LIU, Yunjun GAO, Linlin ZHOU, Gang CHENG, Baihua ZHENG 2016 Singapore Management University

Finding Causality And Responsibility For Probabilistic Reverse Skyline Query Non-Answers, Qing Liu, Yunjun Gao, Linlin Zhou, Gang Cheng, Baihua Zheng

Research Collection School Of Information Systems

Causality and responsibility is an essential tool in the database community for providing intuitive explanations for answers/non-answers to queries. Causality denotes the causes for the answers/non-answers to queries, and responsibility represents the degree of a cause which reflects its influence on the answers/non-answers to queries. In this paper, we study the causality and responsibility problem (CRP) for the non-answers to probabilistic reverse skyline queries (PRSQ). We first formalize CRP on PRSQ, and then, we propose an efficient algorithm termed as CP to compute the causality and responsibility for the non-answers to PRSQ. CP first finds candidate causes ...


A Framework For Hybrid Intrusion Detection Systems, Robert N. Bronte 2016 Kennesaw State University

A Framework For Hybrid Intrusion Detection Systems, Robert N. Bronte

Master of Science in Information Technology Theses

Web application security is a definite threat to the world’s information technology infrastructure. The Open Web Application Security Project (OWASP), generally defines web application security violations as unauthorized or unintentional exposure, disclosure, or loss of personal information. These breaches occur without the company’s knowledge and it often takes a while before the web application attack is revealed to the public, specifically because the security violations are fixed. Due to the need to protect their reputation, organizations have begun researching solutions to these problems. The most widely accepted solution is the use of an Intrusion Detection System (IDS). Such ...


Marim: Mobile Augmented Reality For Interactive Manuals, Tam Nguyen, Dorothy Tan, Bilal Mirza, Jose Sepulveda 2016 University of Dayton

Marim: Mobile Augmented Reality For Interactive Manuals, Tam Nguyen, Dorothy Tan, Bilal Mirza, Jose Sepulveda

Computer Science Faculty Publications

In this work, we present a practical system which uses mobile devices for interactive manuals. In particular, there are two modes provided in the system, namely, expert/trainer and trainee modes. Given the expert/trainer editor, experts design the step-by-step interactive manuals. For each step, the experts capture the images by using phones/tablets and provide visual instructions such as interest regions, text, and action animations. In the trainee mode, the system utilizes the existing object detection and tracking algorithms to identify the step scene and retrieve the respective instruction to be displayed on the mobile device. The trainee then ...


Online Adaptive Passive-Aggressive Methods For Non-Negative Matrix Factorization And Its Applications, Chenghao LIU, HOI, Steven C. H., Peilin ZHAO, Jianling SUN, Ee-Peng LIM 2016 Zhejiang University

Online Adaptive Passive-Aggressive Methods For Non-Negative Matrix Factorization And Its Applications, Chenghao Liu, Hoi, Steven C. H., Peilin Zhao, Jianling Sun, Ee-Peng Lim

Research Collection School Of Information Systems

This paper aims to investigate efficient and scalable machine learning algorithms for resolving Non-negative Matrix Factorization (NMF), which is important for many real-world applications, particularly for collaborative filtering and recommender systems. Unlike traditional batch learning methods, a recently proposed online learning technique named "NN-PA" tackles NMF by applying the popular Passive-Aggressive (PA) online learning, and found promising results. Despite its simplicity and high efficiency, NN-PA falls short in at least two critical limitations: (i) it only exploits the first-order information and thus may converge slowly especially at the beginning of online learning tasks; (ii) it is sensitive to some key ...


Plackett-Luce Regression Mixture Model For Heterogeneous Rankings, Maksim TKACHENKO, Hady W. LAUW 2016 Singapore Management University

Plackett-Luce Regression Mixture Model For Heterogeneous Rankings, Maksim Tkachenko, Hady W. Lauw

Research Collection School Of Information Systems

Learning to rank is an important problem in many scenarios, such as information retrieval, natural language processing, recommender systems, etc. The objective is to learn a function that ranks a number of instances based on their features. In the vast majority of the learning to rank literature, there is an implicit assumption that the population of ranking instances are homogeneous, and thus can be modeled by a single central ranking function. In this work, we are concerned with learning to rank for a heterogeneous population, which may consist of a number of sub-populations, each of which may rank objects dierently ...


Hydra: Massively Compositional Model For Cross-Project Defect Prediction, Xin XIA, David LO, Sinno Jialin PAN, Nachiappan NAGAPPAN, Xinyu WANG 2016 Zhejiang University

Hydra: Massively Compositional Model For Cross-Project Defect Prediction, Xin Xia, David Lo, Sinno Jialin Pan, Nachiappan Nagappan, Xinyu Wang

Research Collection School Of Information Systems

Most software defect prediction approaches are trained and applied on data from the same project. However, often a new project does not have enough training data. Cross-project defect prediction, which uses data from other projects to predict defects in a particular project, provides a new perspective to defect prediction. In this work, we propose a HYbrid moDel Reconstruction Approach (HYDRA) for cross-project defect prediction, which includes two phases: genetic algorithm (GA) phase and ensemble learning (EL) phase. These two phases create a massive composition of classifiers. To examine the benefits of HYDRA, we perform experiments on 29 datasets from the ...


Digital Commons powered by bepress