Theory and Algorithms Commons^™

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 Computing and 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 …

Processing Incomplete K Nearest Neighbor Search, Xiaoye Miao, Yunjun Gao, Gang Chen, Baihua Zheng, Huiyong Cui

Research Collection School Of Computing and Information Systems

Given a setS of multidimensional objects and a query object q, a k nearest neighbor (kNN) query finds from S the k closest objects to q. This query is a fundamental problem in database, data mining, and information retrieval research. It plays an important role in a wide spectrum of real applications such as image recognition and location-based services. However, due to the failure of data transmission devices, improper storage, and accidental loss, incomplete data exist widely in those applications, where some dimensional values of data items are missing. In this paper, we systematically study incomplete k nearest neighbor (IkNN) …

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

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 …

Towards Learning And Verifying Invariants Of Cyber-Physical Systems By Code Mutation, Yuqi Chen, Christopher M. Poskitt, Jun Sun

Research Collection School Of Computing and Information Systems

Cyber-physical systems (CPS), which integrate algorithmic control with physical processes, often consist of physically distributed components communicating over a network. A malfunctioning or compromised component in such a CPS can lead to costly consequences, especially in the context of public infrastructure. In this short paper, we argue for the importance of constructing invariants (or models) of the physical behaviour exhibited by CPS, motivated by their applications to the control, monitoring, and attestation of components. To achieve this despite the inherent complexity of CPS, we propose a new technique for learning invariants that combines machine learning with ideas from mutation testing. …

Partitioning Uncertain Workloads, Freddy Chua, Bernardo A. Huberman

Research Collection School Of Computing and Information Systems

We present a method for determining the ratio of the tasks when breaking any complex workload in such a way that once the outputs from all tasks are joined, their full completion takes less time and exhibit smaller variance than when running on the undivided workload. To do that, we have to infer the capabilities of the processing unit executing the divided workloads or tasks. We propose a Bayesian Inference algorithm to infer the amount of time each task takes in a way that does not require prior knowledge on the processing unit capability. We demonstrate the effectiveness of this …

A Survey On Wireless Indoor Localization From The Device Perspective, Jiang Xiao, Zimu Zhou, Youwen Yi, Lionel M. Ni

Research Collection School Of Computing and Information Systems

With the marvelous development of wireless techniques and ubiquitous deployment of wireless systems indoors, myriad indoor location-based services (ILBSs) have permeated into numerous aspects of modern life. The most fundamental functionality is to pinpoint the location of the target via wireless devices. According to how wireless devices interact with the target, wireless indoor localization schemes roughly fall into two categories: device based and device free. In device-based localization, a wireless device (e.g., a smartphone) is attached to the target and computes its location through cooperation with other deployed wireless devices. In device-free localization, the target carries no wireless devices, while …

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

Research Collection School Of Computing and 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, and then, it …

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 systems currently …

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 follows the displayed …

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

Research Collection School Of Computing and 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 …

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 Computing and 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 …

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

Research Collection School Of Computing and 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

Research Collection School Of Computing and 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, Loc Do, Hady W. Lauw

Research Collection School Of Computing and 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, Duc Trong Le, Yuan Fang, Hady W. Lauw

Research Collection School Of Computing and 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 generative …

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

Research Collection School Of Computing and 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

Research Collection School Of Computing and 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. In …

Soft Confidence-Weighted Learning, Jialei Wang, Peilin Zhao, Hoi, Steven C. H.

Research Collection School Of Computing and Information Systems

Online learning plays an important role in many big datamining problems because of its high efficiency and scalability. In theliterature, many online learning algorithms using gradient information havebeen applied to solve online classification problems. Recently, more effectivesecond-order algorithms have been proposed, where the correlation between thefeatures is utilized to improve the learning efficiency. Among them,Confidence-Weighted (CW) learning algorithms are very effective, which assumethat the classification model is drawn from a Gaussian distribution, whichenables the model to be effectively updated with the second-order informationof the data stream. Despite being studied actively, these CW algorithms cannothandle nonseparable datasets and noisy datasets very …

On The Geodesic Centers Of Polygonal Domains, Haitao Wang

Computer Science Faculty and Staff Publications

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, …

Stochastic Multiple Gradient Decent For Inferring Action-Based Network Generators, Qian Wu, Viplove Arora, Mario Ventresca

The Summer Undergraduate Research Fellowship (SURF) Symposium

Networked systems, like the internet, social networks etc., have in recent years attracted the attention of researchers, specifically to develop models that can help us understand or predict the behavior of these systems. A way of achieving this is through network generators, which are algorithms that can synthesize networks with statistically similar properties to a given target network. Action-based Network Generators (ABNG)is one of these algorithms that defines actions as strategies for nodes to form connections with other nodes, hence generating networks. ABNG is parametrized using an action matrix that assigns an empirical probability distribution to vertices for choosing specific …