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

Theory and Algorithms Commons

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

1145 Full-Text Articles 1307 Authors 209497 Downloads 85 Institutions

All Articles in Theory and Algorithms

Faceted Search

1145 full-text articles. Page 1 of 41.

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 ...


Reconstructability Analysis Detection Of Optimal Gene Order In Genetic Algorithms, Martin Zwick, Stephen Shervais 2016 Portland State University

Reconstructability Analysis Detection Of Optimal Gene Order In Genetic Algorithms, Martin Zwick, Stephen Shervais

Martin Zwick

The building block hypothesis implies that genetic algorithm efficiency will be improved if sets of genes that improve fitness through epistatic interaction are near to one another on the chromosome. We demonstrate this effect with a simple problem, and show that information-theoretic reconstructability analysis can be used to decide on optimal gene ordering.


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 Singapore Management 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 ...


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 ...


Plackett-Luce Regression Mixture Model For Heterogeneous Rankings, MAKSIM TKACHENKO, Hady Wirawan LAUW 2016 Singapore Management University

Plackett-Luce Regression Mixture Model For Heterogeneous Rankings, Maksim Tkachenko, Hady Wirawan 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 ...


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 Singapore Management 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 ...


Constraint Cnf: A Sat And Csp Language Under One Roof, Broes De Cat, Yuliya Lierler 2016 KU Leuven

Constraint Cnf: A Sat And Csp Language Under One Roof, Broes De Cat, Yuliya Lierler

Yuliya Lierler

A new language, called constraint CNF, is proposed. It integrates propositional logic with constraints stemming from constraint programming (CP). A family of algorithms is designed to solve problems expressed in constraint CNF. These algorithms build on techniques from both propositional satisfiability (SAT) and CP. The result is a uniform language and an algorithmic framework, which allow us to gain a deeper understanding of the relation between the solving techniques used in SAT and in CP and apply them together.


Autoquery: Automatic Construction Of Dependency Queries For Code Search, Shaowei WANG, David LO, Lingxiao JIANG 2016 Singapore Management University

Autoquery: Automatic Construction Of Dependency Queries For Code Search, Shaowei Wang, David Lo, Lingxiao Jiang

Research Collection School Of Information Systems

Many code search techniques have been proposed to return relevant code for a user query expressed as textual descriptions. However, source code is not mere text. It contains dependency relations among various program elements. To leverage these dependencies for more accurate code search results, techniques have been proposed to allow user queries to be expressed as control and data dependency relationships among program elements. Although such techniques have been shown to be effective for finding relevant code, it remains a question whether appropriate queries can be generated by average users. In this work, we address this concern by proposing a ...


Is Only One Gps Point Position Sufficient To Locate You To The Road Network Accurately?, Hao WU, Weiwei SUN, Baihua ZHENG 2016 Singapore Management University

Is Only One Gps Point Position Sufficient To Locate You To The Road Network Accurately?, Hao Wu, Weiwei Sun, Baihua Zheng

Research Collection School Of Information Systems

Locating only one GPS position to a road segment accurately is crucial to many location-based services such as mobile taxi-hailing service, geo-tagging, POI check-in, etc. This problem is challenging because of errors including the GPS errors and the digital map errors (misalignment and the same representation of bidirectional roads) and a lack of context information. To the best of our knowledge, no existing work studies this problem directly and the work to reduce GPS signal errors by considering hardware aspect is the most relevant. Consequently, this work is the first attempt to solve the problem of locating one GPS position ...


Probabilistic Models For Contextual Agreement In Preferences, DO HA LOC, Hady Wirawan LAUW 2016 Singapore Management University

Probabilistic Models For Contextual Agreement In Preferences, Do Ha Loc, Hady Wirawan Lauw

Research Collection School Of Information Systems

The long-tail theory for consumer demand implies the need for more accurate personalization technologies to target items to the users who most desire them. A key tenet of personalization is the capacity to model user preferences. Most of the previous work on recommendation and personalization has focused primarily on individual preferences. While some focus on shared preferences between pairs of users, they assume that the same similarity value applies to all items. Here we investigate the notion of "context," hypothesizing that while two users may agree on their preferences on some items, they may also disagree on other items. To ...


Modeling Sequential Preferences With Dynamic User And Context Factors, LE DUC TRONG, Yuan FANG, Hady Wirawan LAUW 2016 Singapore Management University

Modeling Sequential Preferences With Dynamic User And Context Factors, Le Duc Trong, Yuan Fang, Hady Wirawan Lauw

Research Collection School Of Information Systems

Users express their preferences for items in diverse forms, through their liking for items, as well as through the sequence in which they consume items. The latter, referred to as “sequential preference”, manifests itself in scenarios such as song or video playlists, topics one reads or writes about in social media, etc. The current approach to modeling sequential preferences relies primarily on the sequence information, i.e., which item follows another item. However, there are other important factors, due to either the user or the context, which may dynamically affect the way a sequence unfolds. In this work, we develop ...


Representation Learning For Homophilic Preferences, NGUYEN. Trong T., Hady Wirawan LAUW 2016 Singapore Management University

Representation Learning For Homophilic Preferences, Nguyen. Trong T., Hady Wirawan Lauw

Research Collection School Of Information Systems

Users express their personal preferences through ratings, adoptions, and other consumption behaviors. We seek tolearn latent representations for user preferences from such behavioral data. One representation learning model that has been shown to be effective for large preference datasets is Restricted Boltzmann Machine (RBM). While homophily, or the tendency of friends to share their preferences at some level, is an established notion in sociology, thus far it has not yet been clearly demonstrated on RBM-based preference models. The question lies in how to appropriately incorporate social network into the architecture of RBM-based models for learning representations of preferences. In this ...


Control Flow Integrity Enforcement With Dynamic Code Optimization, Yan LIN, Xiaoxiao TANG, Debin GAO, Jianming FU 2016 Singapore Management University

Control Flow Integrity Enforcement With Dynamic Code Optimization, Yan Lin, Xiaoxiao Tang, Debin Gao, Jianming Fu

Research Collection School Of Information Systems

Control Flow Integrity (CFI) is an attractive security property with which most injected and code reuse attacks can be defeated, including advanced attacking techniques like Return-Oriented Programming (ROP). However, comprehensive enforcement of CFI is expensive due to additional supports needed (e.g., compiler support and presence of relocation or debug information) and performance overhead. Recent research has been trying to strike the balance among reasonable approximation of the CFI properties, minimal additional supports needed, and acceptable performance. We investigate existing dynamic code optimization techniques and find that they provide an architecture on which CFI can be enforced effectively and efficiently ...


Using Machine Learning And Natural Language Processing Algorithms To Automate The Evaluation Of Clinical Decision Support In Electronic Medical Record Systems, Donald A. Szlosek, Jonathan M. Ferretti 2016 University of Southern Maine

Using Machine Learning And Natural Language Processing Algorithms To Automate The Evaluation Of Clinical Decision Support In Electronic Medical Record Systems, Donald A. Szlosek, Jonathan M. Ferretti

eGEMs (Generating Evidence & Methods to improve patient outcomes)

Introduction: As the number of clinical decision support systems incorporated into electronic medical records increases, so does the need to evaluate their effectiveness. The use of medical record review and similar manual methods for evaluating decision rules is laborious and inefficient. Here we use machine learning and natural language processing (NLP) algorithms to accurately evaluate a clinical decision support rule through an electronic medical record system and compare it against manual evaluation.

Methods: Modeled after the electronic medical record system EPIC at Maine Medical Center, we developed a dummy dataset containing physician notes in free text for 3621 artificial patients ...


Digital Commons powered by bepress