Computer Science Theses and Dissertations

Permanent URI for this collection

http://hdl.handle.net/1903/2756

Browse

Now showing 1 - 20 of 1000

Absolutely Continuous Spectrum for Parabolic Flows/Maps
(2016) Simonelli, Lucia Dora; Forni, Giovanni; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
This work is devoted to creating an abstract framework for the study of certain spectral properties of parabolic systems. Specifically, we determine under which general conditions to expect the presence of absolutely continuous spectral measures. We use these general conditions to derive results for spectral properties of time-changes of unipotent flows on homogeneous spaces of semisimple groups regarding absolutely continuous spectrum as well as maximal spectral type; the time-changes of the horocycle flow are special cases of this general category of flows. In addition we use the general conditions to derive spectral results for twisted horocycle flows and to rederive spectral results for skew products over translations and Furstenberg transformations.
Accessible On-Body Interaction for People With Visual Impairments
(2016) Oh, Uran Oh; Findlater, Leah; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
While mobile devices offer new opportunities to gain independence in everyday activities for people with disabilities, modern touchscreen-based interfaces can present accessibility challenges for low vision and blind users. Even with state-of-the-art screenreaders, it can be difficult or time-consuming to select specific items without visual feedback. The smooth surface of the touchscreen provides little tactile feedback compared to physical button-based phones. Furthermore, in a mobile context, hand-held devices present additional accessibility issues when both of the users’ hands are not available for interaction (e.g., on hand may be holding a cane or a dog leash). To improve mobile accessibility for people with visual impairments, I investigate on-body interaction, which employs the user’s own skin surface as the input space. On-body interaction may offer an alternative or complementary means of mobile interaction for people with visual impairments by enabling non-visual interaction with extra tactile and proprioceptive feedback compared to a touchscreen. In addition, on-body input may free users’ hands and offer efficient interaction as it can eliminate the need to pull out or hold the device. Despite this potential, little work has investigated the accessibility of on-body interaction for people with visual impairments. Thus, I begin by identifying needs and preferences of accessible on-body interaction. From there, I evaluate user performance in target acquisition and shape drawing tasks on the hand compared to on a touchscreen. Building on these studies, I focus on the design, implementation, and evaluation of an accessible on-body interaction system for visually impaired users. The contributions of this dissertation are: (1) identification of perceived advantages and limitations of on-body input compared to a touchscreen phone, (2) empirical evidence of the performance benefits of on-body input over touchscreen input in terms of speed and accuracy, (3) implementation and evaluation of an on-body gesture recognizer using finger- and wrist-mounted sensors, and (4) design implications for accessible non-visual on-body interaction for people with visual impairments.
An Accountability Architecture for the Internet
(2010) Bender, Adam; Bhattacharjee, Bobby; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
In the current Internet, senders are not accountable for the packets they send. As a result, malicious users send unwanted traffic that wastes shared resources and degrades network performance. Stopping such attacks requires identifying the responsible principal and filtering any unwanted traffic it sends. However, senders can obscure their identity: a packet identifies its sender only by the source address, but the Internet Protocol does not enforce that this address be correct. Additionally, affected destinations have no way to prevent the sender from continuing to cause harm. An accountable network binds sender identities to packets they send for the purpose of holding senders responsible for their traffic. In this dissertation, I present an accountable network-level architecture that strongly binds senders to packets and gives receivers control over who can send traffic to them. Holding senders accountable for their actions would prevent many of the attacks that disrupt the Internet today. Previous work in attack prevention proposes methods of binding packets to senders, giving receivers control over who sends what to them, or both. However, they all require trusted elements on the forwarding path, to either assist in identifying the sender or to filter unwanted packets. These elements are often not under the control of the receiver and may become corrupt. This dissertation shows that the Internet architecture can be extended to allow receivers to block traffic from unwanted senders, even in the presence of malicious devices in the forwarding path. This dissertation validates this thesis with three contributions. The first contribution is DNA, a network architecture that strongly binds packets to their sender, allowing routers to reject unaccountable traffic and recipients to block traffic from unwanted senders. Unlike prior work, which trusts on-path devices to behave correctly, the only trusted component in DNA is an identity certification authority. All other entities may misbehave and are either blocked or evicted from the network. The second contribution is NeighborhoodWatch, a secure, distributed, scalable object store that is capable of withstanding misbehavior by its constituent nodes. DNA uses NeighborhoodWatch to store receiver-specific requests block individual senders. The third contribution is VanGuard, an accountable capability architecture. Capabilities are small, receiver-generated tokens that grant the sender permission to send traffic to receiver. Existing capability architectures are not accountable, assume a protected channel for obtaining capabilities, and allow on-path devices to steal capabilities. VanGuard builds a capability architecture on top of DNA, preventing capability theft and protecting the capability request channel by allowing receivers to block senders that flood the channel. Once a sender obtains capabilities, it no longer needs to sign traffic, thus allowing greater efficiency than DNA alone. The DNA architecture demonstrates that it is possible to create an accountable network architecture in which none of the devices on the forwarding path must be trusted. DNA holds senders responsible for their traffic by allowing receivers to block senders; to store this blocking state, DNA relies on the NeighborhoodWatch DHT. VanGuard extends DNA and reduces its overhead by incorporating capabilities, which gives destinations further control over the traffic that sources send to them.
Accounting for Defect Characteristics in Empirical Studies of Software Testing
(2009) Strecker, Jaymie; Memon, Atif M; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Software testing is an indispensable activity in quality assurance and an enduring topic of research. For decades, researchers have been inventing new and better techniques to test software. However, no testing technique will ever be a panacea for all software defects. Therefore, while researchers should continue to develop new testing techniques, they also need to deeply understand the abilities and limitations of existing techniques, the ways they complement each other, and the trade-offs involved in using different techniques. This work contends that researchers cannot sufficiently understand software testing without also understanding software defects. This work is the first to show that simple, automatically-measurable characteristics of defects affect their susceptibility to detection by software testing. Unlike previous attempts to characterize defects, this work offers a characterization that is objective, practical, and proven to help explain why some defects and not others are detected by testing. More importantly, this work shows that researchers can and should account for defect characteristics when they study the effectiveness of software-testing techniques. An experiment methodology is presented that enables experimenters to compare the effectiveness of different techniques and, at the same time, to measure the influence of defect characteristics and other factors on the results. The methodology is demonstrated in a large experiment in the domain of graphical-user-interface testing. As the experiment shows, researchers who use the methodology will understand what kinds of defects tend to be detected by testing and what testing techniques are better at detecting certain kinds of defects. This information can help researchers develop more effective testing techniques, and it can help software testers make better choices about the testing techniques to use on their projects. As this work explains, it also has the potential to help testers detect more defects, and more important defects, during regression testing.
Accurate Data Approximation in Constrained Environments
(2005-06-15) Deligiannakis, Antonios; Roussopoulos, Nick; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Several data reduction techniques have been proposed recently as methods for providing fast and fairly accurate answers to complex queries over large quantities of data. Their use has been widespread, due to the multiple benefits that they may offer in several constrained environments and applications. Compressed data representations require less space to store, less bandwidth to communicate and can provide, due to their size, very fast response times to queries. Sensor networks represent a typical constrained environment, due to the limited processing, storage and battery capabilities of the sensor nodes. Large-scale sensor networks require tight data handling and data dissemination techniques. Transmitting a full-resolution data feed from each sensor back to the base-station is often prohibitive due to (i) limited bandwidth that may not be sufficient to sustain a continuous feed from all sensors and (ii) increased power consumption due to the wireless multi-hop communication. In order to minimize the volume of the transmitted data, we can apply two well data reduction techniques: aggregation and approximation. In this dissertation we propose novel data reduction techniques for the transmission of measurements collected in sensor network environments. We first study the problem of summarizing multi-valued data feeds generated at a single sensor node, a step necessary for the transmission of large amounts of historical information collected at the node. The transmission of these measurements may either be periodic (i.e., when a certain amount of measurements has been collected), or in response to a query from the base station. We then also consider the approximate evaluation of aggregate continuous queries. A continuous query is a query that runs continuously until explicitly terminated by the user. These queries can be used to obtain a live-estimate of some (aggregated) quantity, such as the total number of moving objects detected by the sensors.
Achieving Global Synchrony in a Distributed System with Free-Running Local Clocks
(2006-11-27) TRINH, MICHAEL; AGRAWALA, ASHOK; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
In any distributed system, there is an intrinsic need to coordinate the events between the nodes. In such a system, even though each individual node only has access to its local clock, global coordination often has to be carried out the basis of time, called the global time, that is common to every nodes. One way to achieve this globally synchronous behavior is to synchronize all local clocks with an external time source such as a Cesium clock. Local time then becomes in effect global time. There are, however, several drawbacks to such clock synchronization method. Highly precise clocks are expensive and can add to the cost of the hardware node. Some approaches depend on network characteristics such as symmetric latency, broadcast medium, or bus structure. Many are also centralized in that they assume the existence of a master node, and this adds additional complexity in terms of redundancy or reconfiguration to handle failures. In this dissertation, we introduce a new method for achieving global synchrony without performing clock synchronization. In our approach, called the Cyclone Network Synchronization (CNS) scheme, the local clocks are free-running and are not modified in any way. CNS relies on the ability of each node to send data at a time of its choosing. Such data are sent at regular interval, with the next instance being determined based only on the local information available at the node. Once the scheme converges, the interval for all nodes becomes exactly the same, supporting a synchronous operation across the whole network. The scheme can be used in many synchronous cyclic networks, and does not require a broadcast medium or depend on a symmetric latency. CNS is a decentralized scheme, as all of the nodes execute the same set of instructions, and can tolerate most topology changes without the need to reconfigure. There is very little overhead since no explicit synchronization messages are sent. A high degree of accuracy can be achieved with the algorithm, and both clock drift as well as latency perturbation are tolerated. Furthermore, this accuracy is not a function of the clock drift rate.
Acting, Planning, and Learning Using Hierarchical Operational Models
(2020) Patra, Sunandita; Nau, Dana; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
The most common representation formalisms for planning are descriptive models that abstractly describe what the actions do and are tailored for efficiently computing the next state(s) in a state-transition system. However, real-world acting requires operational models that describe how to do things, with rich control structures for closed-loop online decision-making in a dynamic environment. Use of a different action model for planning than the one used for acting causes problems with combining acting and planning, in particular for the development and consistency verification of the different models. As an alternative, this dissertation defines and implements an integrated acting-and-planning system in which both planning and acting use the same operational models, which are written in a general-purpose hierarchical task-oriented language offering rich control structures. The acting component, called Reactive Acting Engine (RAE), is inspired by the well-known PRS system, except that instead of being purely reactive, it can get advice from a planner. The dissertation also describes three planning algorithms which plan by doing several Monte Carlo rollouts in the space of operational models. The best of these three planners, Plan-with-UPOM uses a UCT-like Monte Carlo Tree Search procedure called UPOM (UCT Procedure for Operational Models), whose rollouts are simulated executions of the actor's operational models. The dissertation also presents learning strategies for use with RAE and UPOM that acquire from online acting experiences and/or simulated planning results, a mapping from decision contexts to method instances as well as a heuristic function to guide UPOM. The experimental results show that Plan-with-UPOM and the learning strategies significantly improve the acting efficiency and robustness of RAE. It can be proved that UPOM converges asymptotically by mapping its search space to an MDP. The dissertation also describes a real-world prototype of RAE and Plan-with-UPOM to defend software-defined networks, a relatively new network management architecture, against incoming attacks.
Action compositionality with focus on neurodevelopmental disorders
(2016) Claudino, Leonardo; Aloimonos, Yiannis; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
A central question in motor neuroscience is how the Central Nervous System (CNS) would handle flexibility at the effector level, that is, how the brain would solve the problem coined by Nikolai Bernstein as the “degrees of freedom problem”, or the task of controlling a much larger number of degrees of freedom (dofs) that is often needed to produce behavior. Flexibility is a bless and a curse: while it enables the same body to engage in a virtually infinite number of behaviors, the CNS is left with the job of figuring out the right subset of dofs to use and how to control and coordinate these degrees. Similarly, at the level of perception, the CNS seeks to obtain information pertaining to the action and actors involved based on perceived motion of other people’s dofs. This problem is believed to be solved with a particular dimensionality reduction strategy, where action production would consist of tuning only a few parameters that control and coordinate a small number of motor primitives, and action perception would take place by applying grouping processes that would solve the inverse problem, that is to identify the motor primitives and the corresponding tuning parameters used by an actor. These parameters can encode not only information on the action per se, but also higher-order cognitive cues like body language or emotion. This compositional view of action representation has an obvious parallel with language: we can think of primitives as words and cognitive systems (motor, perceptual) as different languages. Little is known, however, about how words/primitives would be formed from low-level signals measured at each dof. Here we introduce the SB-ST method, a bottom-up approach to find full-body postural primitives as a set of key postures, that is, vectors corresponding to key relationships among dofs (such as joint rotations) which we call spatial basis (SB) and second, we impose a parametric model to the spatio-temporal (ST) profiles of each SB vector. We showcase the method by applying SB vectors and ST parameters to study vertical jumps of young adults (YAD) typically developing (TD) children and children with Developmental Coordination Disorder (DCD) obtained with motion capture. We also go over a number of other topics related with compositionality: we introduce a top-down system of tool-use primitives based on kinematic events between body parts and objects. The kinematic basis of these events is inspired by the hand-to-object velocity signature reported by movement psychologists in the 1980’s. We discuss the need for custom-made movement measurement strategies to study action primitives on some target populations, for example infants. Having the right tools to record infant movement would be of help, for example, to research in Autism Spectrum Disorder (ASD) where early sensorimotor abnormalities were shown to be linked to future diagnoses of ASD and the development of the typical social traits ASD is mostly known for. We continue the discussion on infant movement measurement where we present an alternative way of processing movement data by using textual descriptions as re- placements to the actual movement signals observed in infant behavioral trials. We explore the fact that these clinical descriptions are freely available as a byproduct of the diagnosis process itself. A typical/atypical classification experiment shows that, at the level of sentences, traditionally used text features in Natural Language Processing such as term frequencies and TF-IDF computed from unigrams and bigrams can be potentially helpful. In the end, we sketch a conceptual, compositional model of action generation based on exploratory results on the jump data, according to which the presence of disorders would be related not to differences in key postures, but in how they are controlled throughout execution. We next discuss the nature of action and actor information representation by analyzing a second dataset with arm-only data (bi-manual coordination and object manipulations) with more target populations than in the jump dataset: TD and DCD children, YAD and seniors with and without Parkinson’s Disease (PD). Multiple group analyses on dofs coupled with explained variances at SB representations suggest that the cost of representing a task as performed by an actor may be equivalent to the cost of representing the task alone. Plus, group discriminating information appears to be more compressed than task-only discriminating information, and because this compression happens at the top spatial bases, we conjecture that groups may be recognized faster than tasks.
Active Data Collection Techniques to Understand Online Scammers and Cybercriminals
(2016) Park, Young Sam; Shi, Elaine; McCoy, Damon; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Nigerian scam, also known as advance fee fraud or 419 scam, is a prevalent form of online fraudulent activity that causes financial loss to individuals and businesses. Nigerian scam has evolved from simple non-targeted email messages to more sophisticated scams targeted at users of classifieds, dating and other websites. Even though such scams are observed and reported by users frequently, the community’s understanding of Nigerian scams is limited since the scammers operate “underground”. To better understand the underground Nigerian scam ecosystem and seek effective methods to deter Nigerian scam and cybercrime in general, we conduct a series of active and passive measurement studies. Relying upon the analysis and insight gained from the measurement studies, we make four contributions: (1) we analyze the taxonomy of Nigerian scam and derive long-term trends in scams; (2) we provide an insight on Nigerian scam and cybercrime ecosystems and their underground operation; (3) we propose a payment intervention as a potential deterrent to cybercrime operation in general and evaluate its effectiveness; and (4) we offer active and passive measurement tools and techniques that enable in-depth analysis of cybercrime ecosystems and deterrence on them. We first created and analyze a repository of more than two hundred thousand user-reported scam emails, stretching from 2006 to 2014, from four major scam reporting websites. We select ten most commonly observed scam categories and tag 2,000 scam emails randomly selected from our repository. Based upon the manually tagged dataset, we train a machine learning classifier and cluster all scam emails in the repository. From the clustering result, we find a strong and sustained upward trend for targeted scams and downward trend for non-targeted scams. We then focus on two types of targeted scams: sales scams and rental scams targeted users on Craigslist. We built an automated scam data collection system and gathered large-scale sales scam emails. Using the system we posted honeypot ads on Craigslist and conversed automatically with the scammers. Through the email conversation, the system obtained additional confirmation of likely scam activities and collected additional information such as IP addresses and shipping addresses. Our analysis revealed that around 10 groups were responsible for nearly half of the over 13,000 total scam attempts we received. These groups used IP addresses and shipping addresses in both Nigeria and the U.S. We also crawled rental ads on Craigslist, identified rental scam ads amongst the large number of benign ads and conversed with the potential scammers. Through in-depth analysis of the rental scams, we found seven major scam campaigns employing various operations and monetization methods. We also found that unlike sales scammers, most rental scammers were in the U.S. The large-scale scam data and in-depth analysis provide useful insights on how to design effective deterrence techniques against cybercrime in general. We study underground DDoS-for-hire services, also known as booters, and measure the effectiveness of undermining a payment system of DDoS Services. Our analysis shows that the payment intervention can have the desired effect of limiting cybercriminals’ ability and increasing the risk of accepting payments.
Active Vision Based Embodied-AI Design For Nano-UAV Autonomy
(2021) Jagannatha Sanket, Nitin; Aloimonos, Yiannis; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
The human fascination to mimic ultra-efficient flying beings like birds and bees hasled to a rapid rise in aerial robots in the recent decade. These aerial robots now posses a market share of over 10 Billion US Dollars. The future for aerial robots or Unmanned Aerial Vehicles (UAVs) which are commonly called drones is very bright because of their utility in a myriad of applications. I envision drones delivering packages to our homes, finding survivors in collapsed buildings, pollinating flowers, inspecting bridges, performing surveillance of cities, in sports and even as pets. In particular, quadrotors have become the go to platform for aerial robotics due to simplicity in their mechanical design, their vertical takeoff and landing capabilities and agility characteristics. Our eternal pursuit to improve drone safety and improve power efficiency has givenrise to the research and development of smaller yet smarter drones. Furthermore, smaller drones are more agile and task-distributable as swarms. Embodied Artificial Intelligence (AI) has been a big fuel to push this area further. Classically, the approach to designing such nano-drones possesses a strict distinction between perception, planning and control and relies on a 3D map of the scene that are used to plan paths that are executed by a control algorithm. On the contrary, nature’s never-ending quest to improve the efficiency of flyingagents through genetic evolution led to birds developing amazing eyes and brains tailored for agile flight in complex environments as a software and hardware co-design solution. In contrast, smaller flying agents such as insects that are at the other end of the size and computation spectrum adapted an ingenious approach – to utilize movement to gather more information. Early pioneers of robotics remarked at this observation and coined the concept of “Active Perception” which proposed that one can move in an exploratory way to gather more information to compensate for lack of computation and sensing. Such a controlled movement imposes additional constraints on the data being perceived to make the perception problem simpler. Inspired by this concept, in this thesis, I present a novel approach for algorithmicdesign on nano aerial robots (flying robots the size of a hummingbird) based on active perception by tightly coupling and combining perception, planning and control into sensorimotor loops using only on-board sensing and computation. This is done by re-imagining each aerial robot as a series of hierarchical sensorimotor loops where the higher ones require the inner ones such that resources and computation can be efficiently re-used. Activeness is presented and utilized in four different forms to enable large-scale autonomy at tight Size, Weight, Area and Power (SWAP) constraints not heard of before. The four forms of activeness are: 1. By moving the agent itself, 2. By employing an active sensor, 3. By moving a part of the agent’s body, 4. By hallucinating active movements. Next, to make this work practically applicable I show how hardware and software co-design can be performed to optimize the form of active perception to be used. Finally, I present the world’s first prototype of a RoboBeeHive that shows how to integrate multiple competences centered around active vision in all it’s glory. Following is a list of contributions of this thesis: • The world’s first functional prototype of a RoboBeeHive that can artificially pollinateflowers. • The first method that allows a quadrotor to fly through gaps of unknown shape,location and size using a single monocular camera with only on-board sensing and computation. • The first method to dodge dynamic obstacles of unknown shape, size and locationon a quadrotor using a monocular event camera. Our series of shallow neural networks are trained in simulation and transfers to the real world without any finetuning or re-training. • The first method to detect unmarked drones by detecting propellers. Our neuralnetwork is trained in simulation and transfers to the real world without any finetuning or re-training. • A method to adaptively change the baseline of a stereo camera system for quadrotornavigation. • The first method to introduce the usage of saliency to select features in a directvisual odometry pipeline. • A comprehensive benchmark of software and hardware for embodied AI whichwould serve as a blueprint for researchers and practitioners alike.
Adapting Swarm Intelligence for the Self-Assembly of Prespecified Artificial Structures
(2007-04-25) Grushin, Alexander; Reggia, James A; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
The self-assembly problem involves designing individual behaviors that a collection of agents can follow in order to form a given target structure. An effective solution would potentially allow self-assembly to be used as an automated construction tool, for example, in dangerous or inaccessible environments. However, existing methodologies are generally limited in that they are either only capable of assembling a very limited range of simple structures, or only applicable in an idealized environment having few or no constraints on the agents' motion. The research presented here seeks to overcome these limitations by studying the self-assembly of a diverse class of non-trivial structures (building, bridge, etc.) from different-sized blocks, whose motion in a continuous, three-dimensional environment is constrained by gravity and block impenetrability. These constraints impose ordering restrictions on the self-assembly process, and necessitate the assembly and disassembly of temporary structures such as staircases. It is shown that self-assembly under these conditions can be accomplished through an integration of several techniques from the field of swarm intelligence. Specifically, this work extends and incorporates computational models of distributed construction, collective motion, and communication via local signaling. These mechanisms enable blocks to determine where to deposit themselves, to effectively move through continuous space, and to coordinate their behavior over time, while using only local information. Further, an algorithm is presented that, given a target structure, automatically generates distributed control rules that encode individual block behaviors. It is formally proved that under reasonable assumptions, these rules will lead to the emergence of correct system-level coordination that allows self-assembly to complete in spite of environmental constraints. The methodology is also verified experimentally by generating rules for a diverse set of structures, and testing them via simulations. Finally, it is shown that for some structures, the generated rules are able to parsimoniously capture the necessary behaviors. This work yields a better understanding of the complex relationship between local behaviors and global structures in non-trivial self-assembly processes, and presents a step towards their use in the real world.
Adaptive Algorithms for Automated Processing of Document Images
(2011) Agrawal, Mudit; Davis, Larry; Doermann, David; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Large scale document digitization projects continue to motivate interesting document understanding technologies such as script and language identification, page classification, segmentation and enhancement. Typically, however, solutions are still limited to narrow domains or regular formats such as books, forms, articles or letters and operate best on clean documents scanned in a controlled environment. More general collections of heterogeneous documents challenge the basic assumptions of state-of-the-art technology regarding quality, script, content and layout. Our work explores the use of adaptive algorithms for the automated analysis of noisy and complex document collections. We first propose, implement and evaluate an adaptive clutter detection and removal technique for complex binary documents. Our distance transform based technique aims to remove irregular and independent unwanted foreground content while leaving text content untouched. The novelty of this approach is in its determination of best approximation to clutter-content boundary with text like structures. Second, we describe a page segmentation technique called Voronoi++ for complex layouts which builds upon the state-of-the-art method proposed by Kise [Kise1999]. Our approach does not assume structured text zones and is designed to handle multi-lingual text in both handwritten and printed form. Voronoi++ is a dynamically adaptive and contextually aware approach that considers components' separation features combined with Docstrum [O'Gorman1993] based angular and neighborhood features to form provisional zone hypotheses. These provisional zones are then verified based on the context built from local separation and high-level content features. Finally, our research proposes a generic model to segment and to recognize characters for any complex syllabic or non-syllabic script, using font-models. This concept is based on the fact that font files contain all the information necessary to render text and thus a model for how to decompose them. Instead of script-specific routines, this work is a step towards a generic character and recognition scheme for both Latin and non-Latin scripts.
Adaptive Constraint Reduction for Convex Quadratic Programming and Training Support Vector Machines
(2008-01-22) Jung, Jin Hyuk; O'Leary, Dianne P; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Convex quadratic programming (CQP) is an optimization problem of minimizing a convex quadratic objective function subject to linear constraints. We propose an adaptive constraint reduction primal-dual interior-point algorithm for convex quadratic programming with many more constraints than variables. We reduce the computational effort by assembling the normal equation matrix with a subset of the constraints. Instead of the exact matrix, we compute an approximate matrix for a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine scaling variant. A similar approach can be applied to Mehrotra's predictor-corrector type algorithms. An example of CQP arises in training a linear support vector machine (SVM), which is a popular tool for pattern recognition. The difficulty in training a support vector machine (SVM) lies in the typically vast number of patterns used for the training process. In this work, we propose an adaptive constraint reduction primal-dual interior-point method for training the linear SVM with $l_1$ hinge loss. We reduce the computational effort by assembling the normal equation matrix with a subset of well-chosen patterns. Starting with a large portion of the patterns, our proposed scheme excludes more and more unnecessary patterns as the iteration proceeds. We extend our approach to training nonlinear SVMs through Gram matrix approximation methods. Promising numerical results are reported.
Adaptive Database Systems Based On Query Feedback and Cached Results
(1994) Chen, Chung-Min; Roussopoulos, Nick; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md)
This dissertation explores the query optimization technique of using cached results and feedback for improving performance of database systems. Cached results and experience obtained by running queries are used to save execution time for follow–up queries, adapt data and system parameters, and improve overall system performance. First, we develop a framework which integrates query optimization and cache management. The optimizer is capable of generating efficient query plans using previous query results cached on the disk. Alternative methods to access and update the caches are considered by the optimizer based on cost estimation. Different cache management strategies are also included in this framework for comparison. Empirical performance study verifies the advantage and practicality of this framework. To help the optimizer in selecting the best plan, we propose a novel approach for providing accurate but cost-effective selectivity estimation. Distribution of attribute values is regressed in real time, using actual query result sizes obtained as feedback, to make accurate selectivity estimation. This method avoids the expensive off-line database access overhead required by the conventional methods and adapts fairly well to updates and query locality. This is verified empirically. To execute a query plan more efficiently, a buffer pool is usually provided for caching data pages in memory to reduce disk accesses. We enhance buffer utilization by devising a buffer allocation scheme for recurring queries using page fault feedback obtained from previous executions. Performance improvement of this scheme is shown by empirical examples and a systematic simulation.
Adaptive Finite Element Methods for Variational Inequalities: Theory and Applications in Finance
(2007-05-29) Zhang, Chensong; Nochetto, Ricardo H; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
We consider variational inequalities (VIs) in a bounded open domain Omega subset IR^d with a piecewise smooth obstacle constraint. To solve VIs, we formulate a fully-discrete adaptive algorithm by using the backward Euler method for time discretization and the continuous piecewise linear finite element method for space discretization. The outline of this thesis is the following. Firstly, we introduce the elliptic and parabolic variational inequalities in Hilbert spaces and briefly review general existence and uniqueness results. Then we focus on a simple but important example of VI, namely the obstacle problem. One interesting application of the obstacle problem is the American-type option pricing problem in finance. We review the classical model as well as some recent advances in option pricing. These models result in VIs with integro-differential operators. Secondly, we introduce two classical numerical methods in scientific computing: the finite element method for elliptic partial differential equations (PDEs) and the Euler method for ordinary different equations (ODEs). Then we combine these two methods to formulate a fully-discrete numerical scheme for VIs. With mild regularity assumptions, we prove optimal a priori convergence rate with respect to regularity of the solution for the proposed numerical method. Thirdly, we derive an a posteriori error estimator and show its reliability and efficiency. The error estimator is localized in the sense that the size of the elliptic residual is only relevant in the approximate noncontact region, and the approximability of the obstacle is only relevant in the approximate contact region. Based on this new a posteriori error estimator, we design a time-space adaptive algorithm and multigrid solvers for the resulting discrete problems. In the end, numerical results for $d=1,2$ show that the error estimator decays with the same rate as the actual error when the space meshsize and the time step tend to zero. Also, the error indicators capture the correct local behavior of the errors in both the contact and noncontact regions.
Adaptive Kernel Density Approximation and Its Applications to Real-Time Computer Vision
(2005-09-30) Han, Bohyung; Davis, Larry S; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Density-based modeling of visual features is very common in computer vision research due to the uncertainty of observed data; so accurate and simple density representation is essential to improve the quality of overall systems. Even though various methods, either parametric or non-parametric, are proposed for density modeling, there is a significant trade-off between flexibility and computational complexity. Therefore, a new compact and flexible density representation is necessary, and the dissertation provides a solution to alleviate the problems as follows. First, we describe a compact and flexible representation of probability density functions using a mixture of Gaussians which is called Kernel Density Approximation (KDA). In this framework, the number of Gaussians components as well as the weight, mean, and covariance of each Gaussian component are determined automatically by mean-shift mode-finding procedure and curvature fitting. An original density function estimated by kernel density estimation is simplified into a compact mixture of Gaussians by the proposed method; memory requirements are dramatically reduced while incurring only a small amount of error. In order to adapt to variations of visual features, sequential kernel density approximation is proposed in which a sequential update of the density function is performed in linear time. Second, kernel density approximation is incorporated into a Bayesian filtering framework, and we design a Kernel-based Bayesian Filter (KBF). Particle filters have inherent limitations such as degeneracy or loss of diversity which are mainly caused by sampling from discrete proposal distribution. In kernel-based Bayesian filtering, every relevant probability density function is continuous and the posterior is simplified by kernel density approximation so as to propagate a compact form of the density function from step to step. Since the proposal distribution is continuous in this framework, the problems in conventional particle filters are alleviated. The sequential kernel density approximation technique is naturally applied to background modeling, and target appearance modeling for object tracking. Also, the kernel-based Bayesian filtering framework is applied to object tracking, which shows improved performance with a smaller number of samples. We demonstrate the performance of kernel density approximation and its application through various simulations and experiments with real videos.
Adaptive Sampling for Geometric Approximation
(2020) Abdelrazek, Ahmed Abdelkader; Mount, David M; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Geometric approximation of multi-dimensional data sets is an essential algorithmic component for applications in machine learning, computer graphics, and scientific computing. This dissertation promotes an algorithmic sampling methodology for a number of fundamental approximation problems in computational geometry. For each problem, the proposed sampling technique is carefully adapted to the geometry of the input data and the functions to be approximated. In particular, we study proximity queries in spaces of constant dimension and mesh generation in 3D. We start with polytope membership queries, where query points are tested for inclusion in a convex polytope. Trading-off accuracy for efficiency, we tolerate one-sided errors for points within an epsilon-expansion of the polytope. We propose a sampling strategy for the placement of covering ellipsoids sensitive to the local shape of the polytope. The key insight is to realize the samples as Delone sets in the intrinsic Hilbert metric. Using this intrinsic formulation, we considerably simplify state-of-the-art techniques yielding an intuitive and optimal data structure. Next, we study nearest-neighbor queries which retrieve the most similar data point to a given query point. To accommodate more general measures of similarity, we consider non-Euclidean distances including convex distance functions and Bregman divergences. Again, we tolerate multiplicative errors retrieving any point no farther than (1+epsilon) times the distance to the nearest neighbor. We propose a sampling strategy sensitive to the local distribution of points and the gradient of the distance functions. Combined with a careful regularization of the distance minimizers, we obtain a generalized data structure that essentially matches state-of-the-art results specific to the Euclidean distance. Finally, we investigate the generation of Voronoi meshes, where a given domain is decomposed into Voronoi cells as desired for a number of important solvers in computational fluid dynamics. The challenge is to arrange the cells near the boundary to yield an accurate surface approximation without sacrificing quality. We propose a sampling algorithm for the placement of seeds to induce a boundary-conforming Voronoi mesh of the correct topology, with a careful treatment of sharp and non-manifold features. The proposed algorithm achieves significant quality improvements over state-of-the-art polyhedral meshing based on clipped Voronoi cells.
Adiabatic quantum computation: Noise in the adiabatic theorem and using the Jordan-Wigner transform to find effective Hamiltonians
(2008-04-22) O'Hara, Michael James; O'Leary, Dianne P; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
This thesis explores two mathematical aspects of adiabatic quantum computation. Adiabatic quantum computation depends on the adiabatic theorem of quantum mechanics, and (a) we provide a rigorous formulation of the adiabatic theorem with explicit definitions of constants, and (b) we bound error in the adiabatic approximation under conditions of noise and experimental error. We apply the new results to a standard example of violation of the adiabatic approximation, and to a superconducting flux qubit. Further, adiabatic quantum computation requires large ground-state energy gaps throughout a Hamiltonian evolution if it is to solve problems in polynomial time. We identify a class of random Hamiltonians with non-nearest-neighbor interactions and a ground-state energy gap of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the number of qubits. We also identify two classes of Hamiltonians with non-nearest-neighbor interactions whose ground state can be found in polynomial time with adiabatic quantum computing. We then use the Jordan-Wigner transformation to derive equivalent results for Hamiltonians defined using Pauli operators.
Advanced Language-based Techniques for Correct, Secure Networked Systems
(2020) Parker, James; Hicks, Michael; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
Developing correct and secure software is an important task that impacts many areas including finance, transportation, health, and defense. In order to develop secure programs, it is critical to understand the factors that influence the introduction of vulnerable code. To investigate, we ran the Build-it, Break-it, Fix-it (BIBIFI) contest as a quasi-controlled experiment. BIBIFI aims to assess the ability to securely build software, not just break it. In BIBIFI, teams build specified software with the goal of maximizing correctness, performance, and security. The latter is tested when teams attempt to break other teams’ submissions. Winners are chosen from among the best builders and the best breakers. BIBIFI was designed to be open-ended—teams can use any language, tool, process, etc. that they like. As such, contest outcomes shed light on factors that correlate with successfully building secure software and breaking insecure software. We ran three contests involving a total of 156 teams and three different programming problems. Quantitative analysis from these contests found that the most efficient build-it submissions used C/C++, but submissions coded in a statically-typed language were less likely to have a security flaw. Break-it teams that were also successful build-it teams were significantly better at finding security bugs. To improve secure development, we created LWeb, a tool for enforcing label-based, information flow policies in database-using web applications. In a nutshell, LWeb marries the LIO Haskell IFC enforcement library with the Yesod web programming framework. The implementation has two parts. First, we extract the core of LIO into a monad transformer (LMonad) and then apply it to Yesod’s core monad. Second, we extend Yesod’s table definition DSL and query functionality to permit defining and enforcing label-based policies on tables and enforcing them during query processing. LWeb’s policy language is expressive, permitting dynamic per-table and per-row policies. We formalize the essence of LWeb in the λLWeb calculus and mechanize the proof of noninterference in Liquid Haskell. This mechanization constitutes the first metatheoretic proof carried out in Liquid Haskell. We also used LWeb to build the web site hosting BIBIFI. The site involves 40 data tables and sophisticated policies. Compared to manually checking security policies, LWeb imposes a modest runtime overhead of between 2% to 21%. It reduces the trusted code base from the whole application to just 1% of the application code, and 21% of the code overall (when counting LWeb too). Finally, we verify the correctness of distributed applications based on conflict-free replicated data types (CRDTs). In order to do so, we add an extension to Liquid Haskell that facilitates stating and semi-automatically proving properties of typeclasses. Our work allows refinement types to be attached to typeclass method declarations, and ensures that instance implementations respect these types. The engineering of this extension is a modular interaction between GHC, the Glasgow Haskell Compiler, and Liquid Haskell’s core proof infrastructure. To verify CRDTs, we define them as a typeclass with refinement types that capture the mathematical properties CRDTs must satisfy, prove that these properties are sufficient to ensure that replicas’ states converge despite out-of-order delivery, implement (and prove correct) several instances of our CRDT typeclass, and use them to build two realistic applications, a multi-user calendar event planner and a collaborative text editor. In addition, we demonstrate the utility of our typeclass extension by using Liquid Haskell to modularly verify that 34 instances satisfy the laws of five standard typeclasses.
Advancing the State of Auto-tuning with Programming Languages
(2024) Chen, Ray Sun; Hollingsworth, Jeffrey K; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
In the realm of computer science, auto-tuning refers to techniques for software performance optimization. The focus of traditional auto-tuning research is to identify novel performance parameters to expand the optimization space for a given target software/platform combination, and improve the automated search within this optimization space. This makes high-performance computing (HPC) a prime candidate for auto-tuning research, as it sits at the nexus of architectural diversity and performance criticality. However, the major successes for HPC auto-tuning to date involve tailoring memory access patterns to specific cache hierarchies. While important, this is just a small piece of the overall performance portability puzzle. I argue that auto-tuning has room to expand and optimize a richer set of HPC application tuning parameters through the combination of novel non-intrusive programming language idioms and advanced lightweight online search techniques. I support my argument through four contributions to the field. This dissertation describes two techniques for expanding auto-tuning optimization spaces, and two techniques for distributing the auto-tuning search for parallel efficiency.

Browse

Browsing Computer Science Theses and Dissertations by Title

Results Per Page

Sort Options