Physical Sciences and Mathematics Commons^™

A Study Of Correlations Between The Definition And Application Of The Gene Ontology, Yuji Mo

Computer and Electronics Engineering: Dissertations, Theses, and Student Research

When using the Gene Ontology (GO), nucleotide and amino acid sequences are annotated by terms in a structured and controlled vocabulary organized into relational graphs. The usage of the vocabulary (GO terms) in the annotation of these sequences may diverge from the relations defined in the ontology. We measure the consistency of the use of GO terms by comparing GO's defined structure to the terms' application. To do this, we first use synthetic data with different characteristics to understand how these characteristics influence the correlation values determined by various similarity measures. Using these results as a baseline, we found that …

Location Cheating: A Security Challenge To Location-Based Social Network Services, Mai Ren

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Location-based mobile social network services such as Foursquare and Gowalla have grown exponentially over the past several years. These location-based services utilize the geographical position to enrich user experiences in a variety of contexts, including location-based searching and location-based mobile advertising. To attract more users, the location-based mobile social network services provide real-world rewards to the user, when a user checks in at a certain venue or location. This gives incentives for users to cheat on their locations.

In this thesis, we investigate the threat of location cheating attacks, find the root cause of the vulnerability, and outline the possible …

Distributed Algorithms For Energy Savings In The Core Network, Lin Liu

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Recently, many efforts have been undertaken to reduce the energy consumption of core networks. Bundle link is a commonly deployed technique in core networks to combine several high-speed physical sublinks into a virtual connection to achieve bandwidth upgrade flexibility and network reliability. The traffic passing through a bundle link can be carried fully over the first few sublinks (bin packing) or evenly distributed over all sublinks (load balancing). In the current network when a bundle link is on, all of its sublinks are on, thus, selectively shutting down a few sublinks during periods of low traffic could save a large …

Relational Neighborhood Inverse Consistency For Constraint Satisfaction: A Structure-Based Approach For Adjusting Consistency & Managing Propagation, Robert J. Woodward

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Freuder and Elfe [1996] introduced Neighborhood Inverse Consistency (NIC) as a local consistency property defined on the values in the variables' domains of a Constraint Satisfaction Problem (CSP). Debruyne and Bessiere [2011] showed that enforcing NIC on binary CSPs is ineffective on sparse graph and too costly on dense graphs. In this thesis, we propose Relational Neighborhood Inverse Consistency (RNIC), an extension of NIC defined as a local consistency property on the tuples of the relations of a CSP. We characterize RNIC for both binary and non-binary CSPs, and propose an algorithm for enforcing it whose complexity is bounded by …

Use Of Constraint Solving For Testing Software Product Lines, Jiangfan Shi

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

A new software engineering methodology, software product line (SPL) engineering, has been increasingly studied in academia and adopted inindustry in the past decade. It allows the delivery of similar, but customized, software products to customers in the same domain within a short timeperiod. Software product line engineering produces an SPL by defining feature commonality and variability, and is supported by a well-managed asset base. SPL engineering can improve productivity from three to ten times, however, we require more efficient testing methods, so that we canensure the correctness of SPLs with the same resource allocation percentage as in the traditional software …

Efficient Traffic Crash And Snow Complaint Gis System, Anthony B. Ngo

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

We describe the design and implementation of a traffic crash and snow complaint GIS system developed for the Lincoln Public Works department. We also describe a novel geocoding algorithm that was used to move data from the older Criminal Justice Information System, which is a relational database, to the new GIS system. In addition, we describe the implementation of several indexing algorithms that enable the system to efficiently answer rectangular range queries and queries about the relative locations of moving objects. Finally, in many applications (on-line analysis or mobile GIS), we need to execute spatial query efficiently (fast and small), …

Relational Neighborhood Inverse Consistency For Constraint Satisfaction, Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Technical Reports

Freuder and Elfe [1996] introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for Constraint Satisfaction Problems (CSPs) that filters the domains of variables. Two advantages of the algorithm for enforcing NIC is that it automatically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. In this document, we discuss Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to filter relations introduced in [Woodward et al., 2011a], how we enhance the propagation effectiveness by reformulating the dual graph of the CSP. We also describe an automated selection policy …

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

CSE Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

Tcp Congestion Avoidance Algorithm Identification (Caai), Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, Ying Lu

CSE Conference and Workshop Papers

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of …

Adaptive Neighborhood Inverse Consistence As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Contributions

1.The property Relational Neighborhood Inverse Consistency (RNIC)
2.Characterization of RNIC in relation to previously known properties
3.An efficient algorithm for enforcing RNIC, bounded by degree of the dual graph
4.Three reformulations of the dual graph to address topological limitations of the dual graph
5.An adaptive, automatic selection policy for choosing the appropriate dual graph
6.Empirical evidence on difficult CSP benchmarks

Definition

A Constraint Satisfaction Problem (CSP) is a combinatorial decision problem defined by a set of variables {A,B,C,…}, a set of domain values for these variables, and a set of constraints {R₁,R₂,R₃,…} restricting …

Classification For Mass Spectra And Comprehensive Two-Dimensional Chromatograms, Xue Tian

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Mass spectra contain characteristic information regarding the molecular structure and properties of compounds. The mass spectra of compounds from the same chemically related group are similar. Classification is one of the fundamental methodologies for analyzing mass spectral data. The primary goals of classification are to automatically group compounds based on their mass spectra, to find correlation between the properties of compounds and their mass spectra, and to provide a positive identification of unknown compounds.

This dissertation presents a new algorithm for the classification of mass spectra, the most similar neighbor with a probability-based spectrum similarity measure (MSN-PSSM). Experimental results demonstrate …

Molecular Dynamics Simulation Based On Hadoop Mapreduce, Chen He

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Molecular Dynamics (MD) simulation is a computationally intensive application used in multiple fields. It can exploit a distributed environment due to inherent computational parallelism. However, most of the existing implementations focus on performance enhancement. They may not provide fault-tolerance for every time-step.

MapReduce is a framework first proposed by Google for processing huge amounts of data in a distributed environment. The simplicity of the programming model and fault- tolerance for node failure during run-time make it very popular not only for commercial applications but also in scientific computing.

In this thesis, we develop a novel communication-free and each time-step fault- …

Real-Time Divisible Load Scheduling For Cluster Computing, Anwar Mamat

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Cluster computing has become an important paradigm for solving large-scale problems. However, as the size of a cluster increases, so does the complexity of resource management and maintenance. Therefore, automated performance control and re- source management are expected to play critical roles in sustaining the evolution of cluster computing. The current cluster scheduling practice is similar in sophistication to early supercomputer batch scheduling algorithms, and no consideration is given to desired quality-of-service (QoS) attributes. To fully avail the power of computational clusters, new scheduling algorithms that provides high performance, QoS assurance, fault-tolerance, energy savings and streamlined management of the cluster …

Simcol: A Simulation Tool For Computer-Supported Collaborative Learning, Nobel Khandaker, Leen-Kiat Soh

School of Computing: Faculty Publications

Researchers designing the multiagent tools and techniques for computer-supported collaborative learning (CSCL) environments are often faced with high cost, time, and effort required to investigate the effectiveness of their tools and techniques in large scale and longitudinal studies in a real-world environment containing human users. Here, we propose SimCoL, a multiagent environment that simulates collaborative learning among students and agents providing support to the teacher and the students. Our goal with SimCoL is to provide a comprehensive test bed for multiagent researchers to investigate 1) theoretical multiagent research issues, e.g., coalition formation, multiagent learning, and communication, where humans are involved …

Comparative Analysis Of Peak-Detection Techniques For Comprehensive Two-Dimensional Chromatography, Indu Latha, Stephen E. Reichenbach, Qingping Tao

School of Computing: Faculty Publications

Comprehensive two-dimensional gas chromatography (GC×GC) is a powerful technology for separating complex samples. The typical goal of GC×GC peak detection is to aggregate data points of analyte peaks based on their retention times and intensities. Two techniques commonly used for two-dimensional peak detection are the two-step algorithm and the watershed algorithm. A recent study [4] compared the performance of the two-step and watershed algorithms for GC×GC data with retention-time shifts in the second-column separations.In that analysis,the peak retention-time shifts were corrected while applying the two-step algorithm but the watershed algorithm was applied without shift correction. The results indicated that the …

A Reservation-Based Smart Parking System, Hongwei Wang

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

In metropolitan areas, parking management influences drivers search time and cost for parking spaces, parking revenue, and traffic congestion. The wide deployment of wireless parking meters with sensing and communications capabilities allows the parking authority to monitor the state of each parking space in real time and optimize the parking management.

In this thesis, we study state-of-the-art parking policies in smart parking systems, and show that the smart parking system needs to be "smarter". Our design goals of the smart parking systems include: (1) simplify the operations of parking systems, (2) improve drivers' satisfaction, (3) increase parking revenue, and (4) …

A Study On Facility Planning Using Discrete Event Simulation: Case Study Of A Grain Delivery Terminal., Sarah M. Asio

Department of Industrial and Management Systems Engineering: Dissertations, Theses, and Student Research

The application of traditional approaches to the design of efficient facilities can be tedious and time consuming when uncertainty and a number of constraints exist. Queuing models and mathematical programming techniques are not able to capture the complex interaction between resources, the environment and space constraints for dynamic stochastic processes. In the following study discrete event simulation is applied to the facility planning process for a grain delivery terminal. The discrete event simulation approach has been applied to studies such as capacity planning and facility layout for a gasoline station and evaluating the resource requirements for a manufacturing facility. To …

Campus Grids: A Framework To Facilitate Resource Sharing, Derek J. Weitzel

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

It is common at research institutions to maintain multiple clusters. These might fulfill different needs and policies, or represent different owners or generations of hard- ware. Many of these clusters are under utilized while researchers at other departments may require these resources. This may be solved by linking clusters with grid mid- dleware. This thesis describes a distributed high throughput computing framework to link clusters without changing security or execution environments. The framework initially keeps jobs local to the submitter, overflowing if necessary to the campus, and regional grid. The framework is implemented spanning two campuses at the Holland Computing …

Multiagent Coalition Formation In Uncertain Environments With Type-Changing Influences And Its Application Towards Forming Human Coalitions, Nobel A. Khandaker

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

We aim to solve the problem forming multiagent coalitions in uncertain environments where the coalition members’ capability of solving tasks change due to their learning. The MCFP-Mproblem for the agents refers to forming or joining coalitions on behalf of a set of human users so that those human users can solve tasks and improve their types (expertise) to improve their performances over time. MCFP-A problem for a set of agents refers to their forming or joining coalitions so that they are able to solve a set of assigned tasks while optimize their performance over time. We propose the Integrated Human …

Protein Structure – Based Method For Identification Of Horizontal Gene Transfer In Bacteria, Swetha Billa

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Horizontal Gene Transfer is defined as the movement of genetic material from one strain of species to another. Bacteria, being an asexual organism were always believed to transfer genes vertically. But recent studies provide evidence that shows bacteria can also transfer genes horizontally.

HGT plays a major role in evolution and medicine. It is the major contributor in bacterial evolution, enabling species to acquire genes to adapt to the new environments. Bacteria are also believed to develop drug resistance to antibiotics through the phenomenon of HGT. Therefore further study of HGT and its implications is necessary to understand the effects …

Ontology For Psychophysiological Dysregulation Of Anger/Aggression, Swathi Vasanthapuram

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

The advancement of Information Technology in the last four decades led to the use of computers in medicine. A new area called Medical Informatics has emerged. This area comprises the application of IT to healthcare with the aim of creating tools that help healthcare personnel diagnose and treat patients more accurately and efficiently. IT not only provides tools for storing, integrating, and updating patient information base but also for processing information efficiently. One of such tools is a Clinical Decision Support System. Ontologies are an integral part of clinical decision support systems because they help formalize and integrate domain knowledge. …

Exploiting Program And Property Structure For Efficient Runtime Monitoring, Rahul Purandare

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Modern software systems are complex and often built using components that are provided with their application programming interface (API) to assist a user. However, this API is informal and if used incorrectly, may lead to bugs that are hard to detect. In order to address the problem of API conformance checking, researchers have proposed various analysis techniques including static and dynamic typestate analysis. However, it is extremely challenging to develop a static analysis that is both precise and scalable. On the other hand, dynamic analysis or runtime monitoring of programs may incur heavy overhead, thereby limiting its application only to …

Understanding User Generated Content Characteristics : A Hot-Event Perspective, Miao Wang, Guodong Li, Jie Feng, Lisong Xu, Byrav Ramamurthy, Wei Li, Xiaohong Guan

CSE Conference and Workshop Papers

Nowadays, millions of Internet users watch and upload a large number of videos on User Generated Content (UGC) sites (e.g., Youtube) everyday. Moreover, online videos about hot events, such as breaking news and Olympic games, attract lots of users. In this paper, we study the characteristics of hot-event videos by collecting video traces of the largest UGC site in China for 28 days. We first empirically study statistical properties of such videos and find that hot-event videos contribute a large number of views, even though the total number of hotevent videos is relatively small. In addition, there exist extremely active …

Multi-Channel Peer-To-Peer Streaming Systems As Resource Allocation Problems, Miao Wang

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

In the past few years, the Internet has witnessed the success of Peer-to-Peer (P2P) streaming technology, which has attracted millions of users. More recently, commercial P2P streaming systems have begun to support multiple channels and a user in such systems is allowed to watch more than one channel at a time. We refer to such systems as multi-channel P2P streaming systems. In this dissertation, we focus on designing multi-channel P2P streaming systems with the goal of providing optimal streaming quality for all channels, termed as system-wide optimal streaming quality. Specifically, we design the systems from the perspective of how to …

Offline Optimization Of Advance Reservation Of Bandwidth Over Dynamic Circuit Networks, Pragatheeswaran Angu

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

E-science projects require very high-speed and reliable networks to transfer data across various destinations in the world. Dynamic Circuit Network (DCN) is a networking service to make advance reservation of bandwidth between a source and a destination in a network. In this thesis we solve the problem of advance reservation of bandwidth in next-generation wavelength-division multiplexing (WDM) networks using a simulation based approach.
We implement a greedy algorithm and a genetic algorithm in parallel, in separate threads. The request for advance reservation is processed by both but the user gets the response only from the greedy algorithm. The genetic algorithm …

Computational Complexity Of Approximate And Precise Data With Constraint Automaton, Dipty Singh

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

The DNA molecules packaged in structures called chromosomes within the cells of living organisms encode hereditary information that is passed on to their offspring. Using transcription and translation, the genes within these DNA molecules help in protein synthesis. Thus chromosomal DNA serves as a blueprint for the chemical processes of life.

In order to analyze a DNA sequence by currently available technology, we have to cut it into small fragments, e.g. by using restriction enzymes. The application of different restriction enzymes to the multiple copies of the same DNA sequence generates many overlapping fragments. In order to construct the original …

Polygonal Spatial Clustering, Deepti Joshi

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Clustering, the process of grouping together similar objects, is a fundamental task in data mining to help perform knowledge discovery in large datasets. With the growing number of sensor networks, geospatial satellites, global positioning devices, and human networks tremendous amounts of spatio-temporal data that measure the state of the planet Earth are being collected every day. This large amount of spatio-temporal data has increased the need for efficient spatial data mining techniques. Furthermore, most of the anthropogenic objects in space are represented using polygons, for example – counties, census tracts, and watersheds. Therefore, it is important to develop data mining …

Propeller: A Scalable Metadata Organization For A Versatile Searchable File System, Lei Xu, Hong Jiang, Xue Liu, Lei Tian, Yu Hua, Jian Hu

CSE Technical Reports

The exponentially increasing amount of data in file systems has made it increasingly important for users, administrators and applications to be able to fast retrieve files using file-search services, instead of replying on the standard file system API to traverse the hierarchical namespaces. The quality of the file-search services is significantly affected by the file-indexing overhead, the file-search performance and the accuracy of search results. Unfortunately, the existing file-search solutions either are so poorly scalable that their performance degrades unacceptably when the systems scale up, or incur so much crawling delays that they produce acceptably inaccurate results. We believe that …

Identifying Horizontal Gene Transfer Using Anomalies In Protein Structures And Sequences, Venkat Ram B. Santosh

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

Genetics has traditionally focused on vertical gene transfer, which is the passing of the genetic material of an organism to its offspring. However, recent studies in genetics increased the awareness that horizontal gene transfer, which is the passing of the genetic material of an organism to another organism that is not its offspring, is also a significant phenomenon. Horizontal gene transfer is thought to play a major role in the natural evolution of bacteria, such as, when several different types of bacteria all suddenly develop the same drug resistance genes. Artificial horizontal gene transfer occurs in genetic engineering.

This thesis …

A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder

CSE Conference and Workshop Papers

In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that …