Alumni Dissertations

 

Alumni Dissertations

Filter Dissertations By:

 
 
  • SEARCHING FOR MOBILE DATA WITH A PRIORI STATISTICAL KNOWLEDGE OF THEIR WHEREABOUTS UNDER DELAY CONSTRAINTS

    Author:
    Yi Feng
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    AMOTZ BAR-NOY
    Abstract:

    One or more tokens are hidden into several boxes, and then the boxes are locked. The probabilities of each token being found in each box are known. All the probabilities are independent. A searcher is looking for one, some, or all of the tokens by unlocking boxes in a predetermined number of rounds. In each round, any subset of the boxes can be unlocked and the searcher collects all tokens in them. Each box is associated with a positive unlocking cost. The goal is to minimize the expected cost of unlocking boxes until the desired tokens are found. The original motivation is to page mobile users in cellular network systems. Mobile users are tokens and cells are boxes. The probabilities of the users in cells can be extracted from historical data. The unlocking costs of boxes reflect the resources that are consumed to page a cell. The predetermined number of rounds ensures that the users will be found within a certain period of time (delay constraint). The goal is to minimize the resources that are consumed to find the users under the pre-determined delay constraint. In addition to the application of paging mobile users, this scheduling problem has broad utilization in finding information in sensor networks, searching for information in distributed data centers, medical decision making, etc. The special case in which a single token is sought and all the boxes have the same unlocking costs has been studied. Polynomial time optimal algorithms exist. Optimal search strategies can be found in a time which is quadratic with respect to the number of boxes and linear with respect to the number of rounds. We improve this time complexity to linear with respect to both the number of boxes and the number of rounds, and provide a hierarchy of algorithms that trades off optimality for complexity. In the general case of searching a single token while the boxes can have different unlocking costs, we prove it being strongly NP-hard, and provide various approximation algorithms. We also demonstrate a tradeoff between the time complexity and implementation complexity of our approximation algorithms. In the case in which we search multiple tokens and all boxes are of the same unlocking costs, we explore the conference call problem and the yellow page problem. In the former we want to find all tokens and in the later we want to find (any) one of the tokens. The conference call problem has been studied. It is NP-hard and approximation algorithms exist. We show a duality between both problems and provide efficient polynomial-time and exponential-time optimal algorithms for specific cases of the problems. We show a tradeoff between the time and space complexity of optimal algorithms. We implement all of our algorithms and some of the algorithms by other researchers. We conduct a comprehensive experimental study in the context of the paging mobile users application. The experimental study provides further insight of the behavior of algorithms and presents the performance of algorithms in real system.

  • Phylogenetic Trees and Their Analysis

    Author:
    Eric Ford
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Katherine St. John
    Abstract:

    Determining the best possible evolutionary history, the lowest-cost phylogenetic tree, to fit a given set of taxa and character sequences using maximum parsimony is an active area of research due to its underlying importance in understanding biological processes. As several steps in this process are NP-Hard when using popular, biologically-motivated optimality criteria, significant amounts of resources are dedicated to both both heuristics and to making exact methods more computationally tractable. We examine both phylogenetic data and the structure of the search space in order to suggest methods to reduce the number of possible trees that must be examined to find an exact solution for any given set of taxa and associated character data. Our work on four related problems combines theoretical insight with empirical study to improve searching of the tree space. First, we show that there is a Hamiltonian path through tree space for the most common tree metrics, answering Bryant's Challenge for the minimal such path. We next examine the topology of the search space under various metrics, showing that some metrics have local maxima and minima even with "perfect" data, while some others do not. We further characterize conditions for which sequences simulated under the Jukes-Cantor model of evolution yield well-behaved search spaces. Next, we reduce the search space needed for an exact solution by splitting the set of characters into mutually-incompatible subsets of compatible characters, building trees based on the perfect phylogenies implied by these sets, and then searching in the neighborhoods of these trees. We validate this work empirically. Finally, we compare two approaches to the generalized tree alignment problem, or GTAP: Sequence alignment followed by tree search vs. Direct Optimization, on both biological and simulated data.

  • Discovering Regularity in Point Clouds of Urban Scenes

    Author:
    Sam Friedman
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Ioannis Stamos
    Abstract:

    Despite the apparent chaos of the urban environment, cities are actually replete with regularity. From the grid of streets laid out over the earth, to the lattice of windows thrown up into the sky, periodic regularity abounds in the urban scene. Just as salient, though less uniform, are the self-similar branching patterns of trees and vegetation that line streets and fill parks. We propose novel methods for discovering these regularities in 3D range scans acquired by a time-of-flight laser sensor. The applications of this regularity information are broad, and we present two original algorithms. The first exploits the efficiency of the Fourier transform for the real-time detection of periodicity in building facades. Periodic regularity is discovered online by doing a plane sweep across the scene and analyzing the frequency space of each column in the sweep. The simplicity and online nature of this algorithm allow it to be embedded in scanner hardware, making periodicity detection a built-in feature of future 3D cameras. We demonstrate the usefulness of periodicity in view registration, compression, segmentation, and facade reconstruction. The second algorithm leverages the hierarchical decomposition and locality in space of the wavelet transform to find stochastic parameters for procedural models that succinctly describe vegetation. These procedural models facilitate the generation of virtual worlds for architecture, gaming, and augmented reality. The self-similarity of vegetation can be inferred using multi-resolution analysis to discover the underlying branching patterns. We present a unified framework of these tools, enabling the modeling, transmission, and compression of high-resolution, accurate, and immersive 3D images.

  • Finsler Optimal Control Theory

    Author:
    Srikanth Gottipati
    Year of Dissertation:
    2009
    Program:
    Computer Science
    Advisor:
    Sergei Artemov
    Abstract:

    This thesis is a contribution to solving problems of extracting optimal controls for complex systems. Its novelty consists of a detailed examination of Finsler geometry based control by connections as proposed by Kohn and Nerode and its relation to Pontryagin's maximum principle. The long term hope is that these methods will form the underpinning of the applications of control of hybrid systems. Any advances in mathematical and algorithmic techniques for solving such problems would have wide application in business, industry, and science. The widespread use of Bellman's dynamic programming, Dantzig's linear programming, Kalman's optimization with linear quadratic cost functions, demonstrate this. But symbolic and numerical techniques historically have fallen well short of yielding efficient computation procedures to obtain near optimal controls for complex systems. Most investigations have been based on Pontryagin's geometric representation of optimal control and his maximum principle. Kohn and Nerode have proposed a different problem formulation aimed at extracting robust controls as a function of state (synthesis problem with a robustness requirement) in the context of a Finsler geometry corresponding to the optimal control problem. This leads to the study of geometric, symbolic, and numerical methods for solving geodesic equations for connections in Finsler Geometry. A principal result of this thesis is the determination of the relations between the Finsler and Pontryagin formulations of optimal control, and the transformation from one to the other. A second principal result is establishing the relations between robustness and curvature. Curvature is used to quantify the spread of geodesics due to disturbances. Finally, the thesis concludes with numerical integration schemes for computing controls and local connections.

  • Developing Probabilistic Graphical Models for Identifying Text Patterns and Semantics

    Author:
    Minhua Huang
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Robert M. Haralick
    Abstract:

    In this dissertation, we discuss a new probabilistic graphical model called the data sequence dependence model (DSDM). This model is derived from the joint probability function for a sequence of class assignments given a sequence of input symbols (words) under fewer and different conditional independence assumptions than the commonly used probabilistic graphical models, such as hidden Markov models (HMMs), maximum entropy Markov models (MEMMs), and conditional random fields (CRFs). Our model accounts for the data sequence dependency rather than the class sequence dependency. In order to find a sequence of optimal class assignments for a sequence of input symbols, the HMM and CRF models have to employ dynamic programming. In contrast to these models, our method does not need to employ dynamic programming. Although dynamic programming is an efficient optimization technique, our model leads to an algorithm whose computational complexity is less than dynamic programming and whose performance is just as good or better. Based on DSDM, we develop algorithms for identifying semantics in texts. In this research, semantics consists of three types of text patterns. They are the semantic arguments of a verb, the sense of a polysemous word, and the noun phrases of a sentence. In addition, two other probabilistic graphical models are described. They are called the context independence model (CIM) and the class sequence dependence model (CSDM). These models have the same economic gain function as DSDM. However, they are derived under the different conditional independence assumptions. Finally, statistical testing methodologies are employed to validate these models. For our task of identifying semantic patterns, we compare each pair of the models by testing the null hypothesis that the two models are equally good at identifying semantic patterns against the alternative hypothesis that one model is better able to identify semantic patterns. The resulting p-value shows that DSDM is better able to identify semantic patterns than the other models.

  • MULTI-OBJECTIVE GENETIC PROGRAMMING FOR DATA VISUALIZATION AND CLASSIFICATION

    Author:
    Ilknur Icke
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Andrew Rosenberg
    Abstract:

    The process of knowledge discovery lies on a continuum ranging between the human driven (manual exploration) approaches to fully automatic data mining methods. As a hybrid approach, the emerging field of visual analytics aims to facilitate human-machine collaborative decision making by providing automated analysis of data via interactive visualizations. One area of interest in visual analytics is to develop data transformation methods that support visualization and analysis. In this thesis, we develop an evolutionary computing based multi-objective dimensionality reduction method for visual data classification. The algorithm is called Genetic Programming Projection Pursuit (G3P) where genetic programming is utilized in order to automatically create visualizations of higher dimensional labeled datasets which are assessed in terms of discriminative power and interpretability. We consider two forms of interpretability of the visualizations: clearly separated and compact class structures along with easily interpretable data transformation expressions relating the original data attributes to the visualization axes. The G3P algorithm incorporates a number of automated measures of interpretability that were found to be in alignment with human judgement through a user study we conducted. On a number of data mining problems, we show that G3P generates a large number of data transformations that are better than those generated by a number of dimensionality reduction methods such as the principal components analysis (PCA), multiple discriminants analysis (MDA) and targeted projection pursuit (TPP) in terms of discriminative power and interpretability.

  • Optimizing Resource Allocation Under Constraints

    Author:
    Matthew Johnson
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Amotz Bar-Noy
    Abstract:

    The fundamental concept of resource allocation--assigning resources to tasks, and so on--gives rise to very broad families of problems, with instances in many domains, applications, disciplines. In the proposed thesis, we will study a series of assignment-oriented resource allocation problems modeling real-world situations, from the point of view of online and approximation algorithms. The complexities and character of these problems vary greatly. Separate from the problem definitions, we will also examine how the difficulty changes as we vary modalities such as online v. offline, distributed v. centralized, linear v. poly-time, thus mapping out a lattice of problem settings. For each problem and setting, we seek efficient algorithms of the appropriate kind (e.g., exact, approximation, competitive, distributed, ...). Three classes of problems examined in particular will be sensor-mission matching, battery charge scheduling, and geometric sensor coverage.

  • 3D Map Building of Structured Indoor Environments with Heterogeneous Robots

    Author:
    Ravi Kaushik
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Jizhong Xiao
    Abstract:

    We explore a methodology to construct 3D maps of indoor environments using multiple heterogeneous robots. The robots acquire overlapping 3D range images at contiguous locations and fuse them together to form a complete range map. Our methodology involves three major steps in map construction: the first step is to estimate an initial pose between the multiple robots using a real-time camera pose estimation algorithm, the second step involves extracting polygon features from overlapping range images and the third step involves registration of the overlapping range images using extracted polygonal features. We evaluate the performance of several approaches to camera pose estimation, which is used to determine the initial estimate of pose between the multiple robots. We introduce a fast and robust segmentation algorithm, which extracts the polygonal features from the 3D range images. A polygon-based registration algorithm accurately fuses the overlapping range images. The algorithm further refines the initial pose estimate by minimizing the geometric distance between corresponding polygonal features extracted from overlapping range images. Our polygon-based registration combined with camera pose estimation executes in real-time and much faster compared to point-based scan registration techniques. We present experimental results obtained while building indoor maps and quantitative analysis of the algorithms used in map construction of indoor environments.

  • THEORETICAL METHODS FOR BLUR-CORRECTION IN ELECTRON AND SOFT X-RAY MICROSCOPY

    Author:
    Joanna Klukowska
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Gabor Herman
    Abstract:

    The process of object reconstruction from projections is widely used in many fields. One of the applications is the reconstruction of biological specimens from two-dimensional projections in transmission electron microscopy and transmission x-ray microscopy. Various methods have been developed for correcting the blurring that occurs when the projections are obtained by a real instrument. As the attainable resolution increases, new issues become apparent and need to be taken into account in the imaging model. In this dissertation we concentrate on the point spread function and its impact on the quality and usefulness of the reconstructions from images obtained according to image formation models for the two types of microscopy. Specifically, we consider spatial variance of the point spread function in the direction of the electron or x-ray propagation. The correction methods for this type of blurring in both cases are related, but not identical due to nature of the respective imaging processes. We propose correction methods and demonstrate their efficacy using computer simulations.

  • Comparing AI Search Algorithms and Their Efficiency When Applied to Path Finding Problems

    Author:
    Erdal Kose
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Danny Kopec
    Abstract:

    Various Artificial Intelligence (AI) search algorithms have been investigated and classified as unidirectional or bidirectional. We start our discussion by presenting certain unidirectional and bidirectional search algorithms (BDS). We continued our study by presenting contributions to the field of search algorithms in AI. The focus of this research is the study of the bidirectional search and certain classes of AI problems and some new approaches to the domain of AI search algorithms have been explored. The second contribution of this research is to compare problem representations and to exploit built-in features of diverse programming paradigms. The programing paradigms have been classified by the problem domains which they might be more suitable for. This has been justified by the fact that the evaluation of search algorithms is a well-studied area of Artificial Intelligence (AI). However evaluation of the performance of programming paradigms when applied to search algorithms has not been studied well. We conclude our discussion with experimental results and more detailed information about our implementations.