WiFi-based indoor localization is emerging as a new positioning technology. In this work, we present our efforts to find the best recommender system based on the indoor location tracks collected from the Bow Valley shopping mall for one week. The time a user spends in a shop is considered as an implicit preference and different mapping algorithms are proposed to map the time to a more realistic rating value. A new distribution error metric is proposed to examine the mapping algorithms. Eleven different recommender systems are built and evaluated in terms of accuracy and execution time. The Slope-One recommender system with a logarithmic mapping algorithm is finally selected with a score of 1.292, distribution error of 0.178 and execution time of 0.39 seconds for ten runs.

Finding, understanding, and fixing bugs in software systems is challenging. Dynamic binary translation (DBT) systems provide a powerful facility for building program analysis and debugging tools. However, DBT abstractions are too low-level and provide limited contextual information to instrumentation tools, making it hard to implement such tools. In this theis, we introduce behavioral watchpoints, a new software-based watchpoint framework that simplifies the implementation of DBT-based program analysis and debugging tools. Behavioral watchpoints have two key features: 1) they provide contextual information at the instruction level which are directly available with watchpoints and 2) they enable specializing instruction-level instrumentation with individual data structures. We describe three applications that were easily developed using our watchpoint framework: detecting buffer overflows, detecting read-before-write and memory freeing bugs and detecting memory leaks. We implemented behavioral watchpoints using Granary, a DBT framework for instrumenting operating system kernels. We evaluated the overheads of watchpoints for analyzing and debugging operating system kernel modules and show that these overheads are reasonable.

Finding, understanding, and fixing bugs in software systems is challenging. Dynamic binary translation (DBT) systems provide a powerful facility for building program analysis and debugging tools. However, DBT abstractions are too low-level and provide limited contextual information to instrumentation tools, making it hard to implement such tools. In this theis, we introduce behavioral watchpoints, a new software-based watchpoint framework that simplifies the implementation of DBT-based program analysis and debugging tools. Behavioral watchpoints have two key features: 1) they provide contextual information at the instruction level which are directly available with watchpoints and 2) they enable specializing instruction-level instrumentation with individual data structures. We describe three applications that were easily developed using our watchpoint framework: detecting buffer overflows, detecting read-before-write and memory freeing bugs and detecting memory leaks. We implemented behavioral watchpoints using Granary, a DBT framework for instrumenting operating system kernels. We evaluated the overheads of watchpoints for analyzing and debugging operating system kernel modules and show that these overheads are reasonable.

We hypothesize and confirm that probabilistic reasoning is closely related to constraint satisfaction at a formal level, and that this relationship yields effective algorithms for guiding constraint satisfaction and constraint optimization solvers. By taking a unified view of probabilistic inference and constraint reasoning in terms of graphical models, we first associate a number of formalisms and techniques between the two areas. For instance, we characterize search and inference in constraint reasoning as summation and multiplication (or disjunction and conjunction) in the probabilistic space; necessary but insufficient consistency conditions for solutions to constraint problems (like arc-consistency) mirror approximate objective functions over probability distributions (like the Bethe free energy); and the polytope of feasible points for marginal probabilities represents the linear relaxation of a particular constraint satisfaction problem. While such insights synthesize an assortment of existing formalisms from varied research communities, they also yield an entirely novel set of “bias estimation” techniques that contribute to a growing body of research on applying probabilistic methods to constraint problems. In practical terms, these techniques estimate the percentage of solutions to a constraint satisfaction or optimization problem wherein a given variable is assigned a given value. By devising search methods that incorporate such information as heuristic guidance for variable and value ordering, we are able to outperform existing solvers on problems of interest from constraint satisfaction and constraint optimization–-as represented here by the SAT and MaxSAT problems. Further, for MaxSAT we present an equivalent transformation” process that normalizes the weights in constraint optimization problems, in order to encourage prunings of the search tree during branch-and-bound search. To control such computationally expensive processes, we determine promising situations for using them throughout the course of an individual search process. We accomplish this using a reinforcement learning-based control module that seeks a principled balance between the exploration of new strategies and the exploitation of existing experiences.

Molecular docking is a computational tool commonly applied in drug discovery projects and fundamental biological studies of protein-ligand interactions. Traditionally, molecular docking is used to address one of three following questions: (i) given a ligand molecule and a protein receptor, predict the binding mode (pose) of the ligand within the context of a receptor, (ii) screen a collection of small-molecules against a receptor and rank ligands by their likelihood of being active, and (iii) given a ligand molecule and a target receptor, predict the binding affinity of the two. Here, we focus on the first two questions, namely ranking and pose prediction. Currently, state-of-the-art docking algorithms predict poses within 2A of the native pose in a rate lower than ∼60% and in many cases, below 40%. In ranking, their ability to identify active ligands is inconsistent and generally suffers from high false-positive rate. In this thesis we present novel algorithms to enhance the ability of molecular docking to address these two questions. These algorithms do not substitute traditional docking but rather being applied on top of them to provide synergistic effect. Our algorithms improve pose predictions by 0.5-1.0A and ranking order for 23% of the targets in gold-standard benchmarks. As importantly, the algorithms improve the consistence of the posing and ranking predictions over diverse sets of targets and screening libraries. In addition to the posing and ranking, we present the pharmacophore concept. A pharmacophore is an ensemble of physiochemical descriptors associated with a biological target that elucidates common interaction patterns of ligands with that target. We introduce a novel pharmacophore inference algorithm and demonstrate its utilization in molecular docking. This thesis is outlined as follow. First we introduce the molecular docking approach for pose prediction and ranking. Second, we discuss the pharmacophore concept and present algorithms for pharmacophore inference. Third, we demonstrate the utilization of pharmacophores for pose prediction by re-scoring candidate poses generated by docking algorithms. Finally, we present algorithms to improve ranking by reducing bias in scoring functions employed by docking algorithms.

Although integrity constraints are the primary means for enforcing data integrity, there are cases in which they are not defined or are not strictly enforced. This leads to inconsistencies in the data, causing poor data quality. In this thesis, we leverage the power of constraints to improve data quality. To ensure that the data conforms to the intended application domain semantics, we develop two algorithms focusing on constraint discovery. The first algorithm discovers a class of conditional constraints, which hold over a subset of the relation, under specific conditional values. The second algorithm discovers attribute domain constraints, which bind specific values to the attributes of a relation for a given domain. These two types of constraints have been shown to be useful for data cleaning. In practice, weak enforcement of constraints often occurs for performance reasons. This leads to inconsistencies between the data and the set of defined constraints. To resolve this inconsistency, we must determine whether it is the constraints or the data that is incorrect, and then make the necessary corrections. We develop a repair model that considers repairs to the data and repairs to the constraints on an equal footing. We present repair algorithms that find the necessary repairs to bring the data and the constraints back to a consistent state. Finally, we study the efficiency and quality of our techniques. We show that our constraint discovery algorithms find meaningful constraints with good precision and recall. We also show that our repair algorithms resolve many inconsistencies with high quality repairs, and propose repairs that previous algorithms did not consider.

This thesis proposes a combination of solutions to improve scalability and playability of MMOGs.

Doctor of Philosophy / Computing and Information Sciences / William H. Hsu / While the Hierarchical Dirichlet Process (HDP) has recently been widely applied to topic modeling tasks, most current hybrid models for concurrent inference of topics and other factors are not based on HDP. In this dissertation, we present two new models that extend an HDP topic modeling framework to incorporate other learning factors. One model injects Latent Dirichlet Allocation (LDA) based sentiment learning into HDP. This model preserves the benefits of nonparametric Bayesian models for topic learning, while learning latent sentiment aspects simultaneously. It automatically learns different word distributions for each single sentiment polarity within each topic generated. The other model combines an existing HDP framework for learning topics from free text with latent authorship learning within a generative model using author list information. This model adds one more layer into the current hierarchy of HDPs to represent topic groups shared by authors, and the document topic distribution is represented as a mixture of topic distribution of its authors. This model automatically learns author contribution partitions for documents in addition to topics.

Master of Science / Department of Electrical and Computer Engineering / Dwight D. Day / Process migration is a technique in clustering and distributed computing by which parallel applications can be dynamically moved between nodes in a cluster in response to differing phases of execution, which is of growing usefulness in the field of distributed computing. A drawback to many recent implementations of process migration is that sockets for interprocess communication do not migrate with the process requiring communication to be rerouted through the process' starting, or home, node, resulting in reduced communications performance when the process is migrated away from its home node. This thesis focuses on the implemention a solution to this problem at the kernel level for the OpenMosix process migration system with efficient socket handoff and cluster-wide unique addressing by reimplemting TCP on top of the existing network code in the Linux kernel. Although falling short of the initial goal of fully transparent operation, this thesis presents a working implementation of migratable sockets for the OpenMosix process migration system that demonstrates working socket migration and improved performance over non-migrating sockets in OpenMosix.

Master of Science / Department of Computing and Information Sciences / David A. Gustafson / An interest point detection scheme is presented that is comparable in quality to existing methods, but can be performed much faster. The detection is based on a straightforward color analysis at a coarse granularity. A 3x3 grid of squares is centered on the candidate point, so that the candidate point corresponds to the middle square. If the color of the center region is inhomogeneous with all of the surrounding regions, the point is labeled as interesting. A point will also be labeled as interesting if a minority of the surrounding squares are homogeneous, and arranged in an appropriate pattern. Testing confirms that this detection scheme is much faster than the state-of-the-art. It is also repeatable, even under different viewing conditions. The detector is robust with respect to changes in viewpoint, lighting, zoom, and to a certain extent, rotation.