Computer Sciences Commons^™

An Improved Analysis For A Greedy Remote-Clique Algorithm Using Factor-Revealing Lps, Benjamin E. Birnbaum, Kenneth J. Goldman

All Computer Science and Engineering Research

Given a complete graph with nonnegative edge weights satisfying the triangle inequality and a positive integer p, the remote-clique problem is to find a subset of p vertices having a maximum-weight induced subgraph. A simple greedy algorithm for the problem has been shown to have an approximation ratio of 4, but a tight example has not been provided. In this paper, we use the technique of factor revealing linear programs to prove that this algorithm actually achieves an approximation ratio of 2, matching the best-known ratio for the problem. The greedy algorithm's running time of O(pn) makes it the fastest …

Agilla: A Mobile Agent Middleware For Sensor Networks, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu

All Computer Science and Engineering Research

Agilla is a mobile agent middleware for sensor networks. Mobile agents are special processes that can migrate across sensors. They increase network flexibility by enabling active in-network reprogramming. Neighbor lists and tuple spaces are used for agent coordination. Agilla was originally implemented on Mica2 motes, but has been ported to other platforms. Its Mica2 implementation consumes 41.6KB of code and 3.59KB of data memory. Agents can move five hops in less than 1.1s with over 92% success. Agilla was used to develop multiple applications related to fire detection and tracking, cargo container monitoring, and robot navigation.

Feature Detection Using Curvature Maps And The Min-Cut/Max-Flow Graph Cut Algorithm, Timothy Gatzke, Cindy Grimm

All Computer Science and Engineering Research

Automatic detection of features in three-dimensional objects is a critical part of shape matching tasks such as object registration and recognition. Previous approaches to local surface matching have either focused on man-made objects, where features are generally well-defined, or required some type of user interaction to select features. Manual selection of corresponding features and subjective determination of the difference between objects are time consuming processes requiring a high level of expertise. Curvature is a useful property of a surface, but curvature calculation on a discrete mesh is often noisy and not always accurate. However, the em Curvature Map, which represents …

Distributed Utilization Control For Real-Time Clusters With Load Balancing, Yong Fu, Hongan Wang, Chenyang Lu, Ramu S. Chandra

All Computer Science and Engineering Research

Recent years have seen rapid growth of online services that rely on large-scale server clusters to handle high volume of requests. Such clusters must adaptively control the CPU utilizations of many processors in order to maintain desired soft real-time performance and prevent system overload in face of unpredictable workloads. This paper presents DUC-LB, a novel distributed utilization control algorithm for cluster-based soft real-time applications. Compared to earlier works on utilization control, a distinguishing feature of DUC-LB is its capability to handle system dynamics caused by load balancing, which is a common and essential component of most clusters today. Simulation results …

Mobiwork: Mobile Workflow For Manets, Gregory Hackmann, Rohan Sen, Mart Haitjema, Gruia-Catalin Roman, Gill

All Computer Science and Engineering Research

The workflow model is well suited for scenarios where many entities work collaboratively towards a common goal, and is used widely today to model complex business processes. However, the fundamental workflow model is very powerful and can be applied to a wider variety of application domains. This paper represents an initial investigation into the possibility of using workflows to model collaboration in an ad hoc mobile environment. Moving to a mobile setting introduces many challenges as the mobility of the participants in a workflow imposes constraints on allocation of workflow tasks, coordination among participants, and marshaling of results. We present …

Efficient Mapping Of Virtual Networks Onto A Shared Substrate, Jing Lu, Jonathan Turner

All Computer Science and Engineering Research

Virtualization has been proposed as a vehicle for overcoming the growing problem of internet ossification [1]. This paper studies the problem of mapping diverse virtual networks onto a common physical substrate. In particular, we develop a method for mapping a virtual network onto a substrate network in a cost-efficient way, while allocating sufficient capacity to virtual network links to ensure that the virtual network can handle any traffic pattern allowed by a general set of traffic constraints. Our approach attempts to find the best topology in a family of backbone-star topologies, in which a subset of nodes constitute the backbone, …

Adaptive Embedded Roadmaps For Sensor Networks, Gazihan Alankus, Nuzhet Atay, Chenyang Lu, Burchan Bayazit

All Computer Science and Engineering Research

In this paper, we propose a new approach to wireless sensor network assisted navigation while avoiding moving dangers. Our approach relies on an embedded roadmap in the sensor network that always contains safe paths. The roadmap is adaptive, i.e., it adapts its topology to changing dangers. The mobile robots in the environment uses the roadmap to reach their destinations. We evaluated the performance of embedded roadmap both in simulations using realistic conditions and with real hardware. Our results show that the proposed navigation algorithm is better suited for sensor networks than traditional navigation field based algorithms. Our observations suggest that …

Control Of Decoherence In Open Quantum Systems, Narayan Ganesan

All Computer Science and Engineering Research

No abstract provided.

Knuth-Bendix Completion With Modern Termination Checking, Master's Thesis, August 2006, Ian Wehrman

All Computer Science and Engineering Research

Knuth-Bendix completion is a technique for equational automated theorem proving based on term rewriting. This classic procedure is parametrized by an equational theory and a (well-founded) reduction order used at runtime to ensure termination of intermediate rewriting systems. Any reduction order can be used in principle, but modern completion tools typically implement only a few classes of such orders (e.g., recursive path orders and polynomial orders). Consequently, the theories for which completion can possibly succeed are limited to those compatible with an instance of an implemented class of orders. Finding and specifying a compatible order, even among a small number …

Sliver: A Bpel Workflow Process Execution Engine For Mobile Devices, Gregory Hackmann, Mart Haitjema, Christopher Gill, Catalin-Gruia Roman

All Computer Science and Engineering Research

The Business Process Execution Language (BPEL) has become the dominant means for expressing traditional business processes as workflows. The widespread deployment of mobile devices like PDAs and mobile phones has created a vast computational and communication resource for these workflows to exploit. However, BPEL so far has been deployed only on relatively heavyweight server platforms such as Apache Tomcat, leaving the potential created by these lower-end devices untapped. This paper presents Sliver, a BPEL workflow process execution engine that supports a wide variety of devices ranging from mobile phones to desktop PCs. We discuss the design decisions that allow Sliver …

Reusable Models For Timing And Liveness Analysis Of Middleware For Distributed Real-Time And Embedded Systems, Venkita Subramonian, Christopher Gill, Cesar Sanchez, Henny Sipma

All Computer Science and Engineering Research

Distributed real-time and embedded (DRE) systems have stringent constraints on timeliness and other properties whose assurance is crucial to correct system behavior. Formal tools and techniques play a key role in verifying and validating system properties. However, many DRE systems are built using middleware frameworks that have grown increasingly complex to address the diverse requirements of a wide range of applications. How to apply formal tools and techniques effectively to these systems, given the range of middleware configuration options available, is therefore an important research problem. This paper makes three contributions to research on formal verification and validation of middleware-based …

Multimodal Congestion Control For Low Stable-State Queuing, Maxim Podlesny, Sergey Gorinsky

All Computer Science and Engineering Research

To discover an efficient fair sending rate for a flow, Transmission Control Protocol (TCP) saturates the bottleneck link and its buffer until the router discards a packet. Such TCP-caused queuing is detrimental for interactive and other delay-sensitive applications. In this paper, we present Multimodal Control Protocol (MCP) which strives to maintain low queues and avoid congestion losses at network links. The multimodal MCP engages routers and hosts in limited explicit communication. A distinguishing property of MCP is stable transmission after converging to efficient fair states. To ensure convergence to fairness, MCP incorporates an innovative mechanism that enables a flow to …

Dynamic Resource Management In A Static Network Operating System, Kevin Klues, Vlado Handziski, David Culler, David Gay, Phillip Levis Levis, Chenyang Lu, Adam Wolisz

All Computer Science and Engineering Research

We present novel approaches to managing three key resources in an event-driven sensornet OS: memory, energy, and peripherals. We describe the factors that necessitate using these new approaches rather than existing ones. A combination of static allocation and compile-time virtualization isolates resources from one another, while dynamic management provides the flexibility and sharing needed to minimize worst-case overheads. We evaluate the effectiveness and efficiency of these management policies in comparison to those of TinyOS 1.x, SOS, MOS, and Contiki. We show that by making memory, energy, and peripherals first-class abstractions, an OS can quickly, efficiently, and accurately adjust itself to …

Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Kevin Klues, Guoliang Xing, Chenyang Lu

All Computer Science and Engineering Research

Radio power management is of paramount concern in wireless sensor networks that must achieve long lifetimes on scarce amounts of energy. While a multitude of power management protocols have been proposed in the past, the lack of system support for flexibly integrating them with a diverse set of applications and network platforms has made them difficult to use. Instead of proposing yet another power management protocol, this paper focuses on providing link layer support towards realizing a Unified Power Management Architecture (UPMA) for flexible radio power management in wireless sensor networks. In contrast to the monolithic approaches adopted by existing …

Cian: A Language And Middleware For Collaboration In Ad Hoc Networks, Rohan Sen, Gruia-Catalin Roman, Andrew Frank

All Computer Science and Engineering Research

Designing software that supports collaboration among multiple users in mobile ad hoc networks is challenging due to the dynamic network topology and inherent unpredictability of the environment. However, as we increasingly migrate to using mobile computing platforms, there is a pertinent need for software that can support a wide range of collaborative activities anywhere and at any time without relying on any external infrastructure. In this paper, we adopt the workflow model to represent the structure of an activity that involves multiple tasks being performed in a structured, collaborative fashion by multiple users. Using the workflow model as a base, …

Virtualization For A Network Processor Runtime System, Brandon Heller, Jonathan Turner, John Dehart, Patrick Crowley

All Computer Science and Engineering Research

The continuing ossification of the Internet is slowing the pace of network innovation. Network diversification presents one solution to this problem, by virtualizing the network at multiple layers. Diversified networks consist of a shared physical substrate, virtual routers (metarouters), and virtual links (metalinks). Virtualizing routers enables smooth and incremental upgrades to new network services. Our current priority for a diversified router prototype is to enable reserved slices of the network for researchers to perform repeatable, high-speed network experiments. General-purpose processors have well established techniques for virtualization, but do not scale efficiently to multi-gigabit speeds. To achieve these speeds, we employ …

Auto-Pipe And The X Language: A Toolset And Language For The Simulation, Analysis, And Synthesis Of Heterogeneous Pipelined Architectures, Master's Thesis, August 2006, Eric J. Tyson

All Computer Science and Engineering Research

Pipelining an algorithmis a popularmethod of increasing the performance of many computation-intensive applications. Often, one wants to form pipelines composed mostly of commonly used simple building blocks such as DSP components, simple math operations, encryption, or pattern matching stages. Additionally, one may desire to map these processing tasks to different computational resources based on their relative performance attributes (e.g., DSP operations on an FPGA). Auto-Pipe is composed of the X Language, a flexible interface language that aids the description of complex dataflow topologies (including pipelines); X-Com, a compiler for the X Language; X-Sim, a tool for modeling pipelined architectures based …

K-Spmm: A Database Of Murine Spermatogenic Promoters Modules & Motifs, Yi Lu, Adrian E. Platts, G Charles Ostermeier, Stephen A. Krawetz

Wayne State University Associated BioMed Central Scholarship

Abstract

Background

Understanding the regulatory processes that coordinate the cascade of gene expression leading to male gamete development has proven challenging. Research has been hindered in part by an incomplete picture of the regulatory elements that are both characteristic of and distinctive to the broad population of spermatogenically expressed genes.

Description

K-SPMM, a database of murine Spermatogenic Promoters Modules and Motifs, has been developed as a web-based resource for the comparative analysis of promoter regions and their constituent elements in developing male germ cells. The system contains data on 7,551 genes and 11,715 putative promoter regions …

Fm-Test: A Fuzzy-Set-Theory-Based Approach To Differential Gene Expression Data Analysis, Lily R. Liang, Shiyong Lu, Xuena Wang, Yi Lu, Vinay Mandal, Dorrelyn Patacsil, Deepak Kumar

Wayne State University Associated BioMed Central Scholarship

Abstract

Background

Microarray techniques have revolutionized genomic research by making it possible to monitor the expression of thousands of genes in parallel. As the amount of microarray data being produced is increasing at an exponential rate, there is a great demand for efficient and effective expression data analysis tools. Comparison of gene expression profiles of patients against those of normal counterpart people will enhance our understanding of a disease and identify leads for therapeutic intervention.

Results

In this paper, we propose an innovative approach, fuzzy membership test (FM-test), based on fuzzy set theory to identify disease associated genes from microarray …

Call-By-Name Calculus Of Records And Its Basic Properties, Elena Machkasova, Emily Christiansen

Faculty Working Papers

No abstract provided.

Ceg 490/690-01: Technology-Based Ventures, Forouzan Golshani, S. Narayanan

Computer Science & Engineering Syllabi

No abstract provided.

Cs 205-04,05,06: Computer Literacy And Office Automation, Terri Bauer

Computer Science & Engineering Syllabi

No abstract provided.

Driving Deep Semantics In Middleware And Networks: What, Why And How?, Amit P. Sheth

Kno.e.sis Publications

No abstract provided.

Knowledge Modeling And Its Application In Life Sciences: A Tale Of Two Ontologies, Satya S. Sahoo, Christopher Thomas, Amit P. Sheth, William S. York, Samir Tartir

Kno.e.sis Publications

High throughput glycoproteomics, similar to genomics and proteomics, involves extremely large volumes of distributed, heterogeneous data as a basis for identification and quantification of a structurally diverse collection of biomolecules. The ability to share, compare, query for and most critically correlate datasets using the native biological relationships are some of the challenges being faced by glycobiology researchers. As a solution for these challenges, we are building a semantic structure, using a suite of ontologies, which supports management of data and information at each step of the experimental lifecycle. This framework will enable researchers to leverage the large scale of glycoproteomics …

Show Me What You Mean! Exploiting Domain Semantics In Ontology Visualization, Ravi Pavagada, Christopher Thomas, Amit P. Sheth, William S. York

Kno.e.sis Publications

Ontologies build the backbone for many life-sciences applications. These ontologies, however, are represented in XML based languages that are meant for machine-consumption and hence are difficult for humans to comprehend. For a meaningful visualization of these ontologies, it is important that the display of entities and relationships captures the cognitive representation of the domain as perceived by the domain experts. In this paper we present OntoVista, an ontology visualization tool that is adaptable to the needs of different domains, especially in the life sciences. While keeping the graph structures as the predominant model, we provide a semantically enhanced graph display …

Electronic Mathematics, Aidan O'Donoghue

Theses

Recent times have seen an explosion in the use of interactive technologies in the delivery of learning content to students in all educational sectors in Ireland. This expansion has led to the creation of modem day phenomenons such as global and ‘teacherless’ classrooms.

The research study I have undertaken is to determine if students perform to the same standard when learning through an interactive educational software application as opposed to a more traditional setting of learning ’through’ a teacher in a classroom. The application being developed for this study enables students to learn the ordinary level leaving certificate mathematics course …

Image-Based Material Editing, Erum Khan

Electronic Theses and Dissertations

Photo editing software allows digital images to be blurred, warped or re-colored at the touch of a button. However, it is not currently possible to change the material appearance of an object except by painstakingly painting over the appropriate pixels. Here we present a set of methods for automatically replacing one material with another, completely different material, starting with only a single high dynamic range image, and an alpha matte specifying the object. Our approach exploits the fact that human vision is surprisingly tolerant of certain (sometimes enormous) physical inaccuracies. Thus, it may be possible to produce a visually compelling …

The Antecedents Of M-Commerce Adoption, Morris Kalliny, Michael S. Minor

Business and Information Technology Faculty Research & Creative Works

The growth of Internet shopping has been attributed to rapid advances in technology and other influences such as convenience. We empirically investigate the relationship between demographics, ease of use, convenience, usefulness and enjoyment and intention to use m-commerce and attitude toward m-commerce. Two studies were conducted where a student and a non student sample was used. Data analysis revealed age, gender and educational level of customers do not play a role in influencing intention to use m-commerce. However, convenience, ease of use, usefulness and enjoyment all play a role in the customer's intention to use m-commerce.

Adaptive And Probabilistic Power Control Algorithms For Dense Rfid Reader Network, Kainan Cha, Anil Ramachandran, Jagannathan Sarangapani

Electrical and Computer Engineering Faculty Research & Creative Works

In radio frequency identification (RFID) systems, the detection range and read rates may suffer from interferences between high power devices such as readers. In dense networks, this problem grows severely and degrades system performance. In this paper, we investigate feasible power control schemes to ensure overall coverage area of the system while maintaining a desired data rate. The power control should dynamically adjust the output power of a RFID reader by adapting to the noise level seen during tag reading and acceptable signal-to-noise ratio (SNR). We present a novel distributed adaptive power control (DAPC) and probabilistic power control (PPC) as …

Neuro Control Of Nonlinear Discrete Time Systems With Deadzone And Input Constraints, Pingan He, Wenzhi Gao, Jagannathan Sarangapani

Electrical and Computer Engineering Faculty Research & Creative Works

A neural network (NN) controller in discrete time is designed to deliver a desired tracking performance for a class of uncertain nonlinear systems with unknown deadzones and magnitude constraints on the input. The NN controller consists of two NNs: the first NN for compensating the unknown deadzones; and the second NN for compensating the uncertain nonlinear system dynamics. The magnitude constraints on the input are modeled as saturation nonlinearities and they are dealt with in the Lyapunov-based controller design. The uniformly ultimate boundedness (UUB) of the closed-loop tracking errors and the neural network weights estimation errors is demonstrated via Lyapunov …