Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 30 of 62
Full-Text Articles in Entire DC Network
Limit Crossing For Decision Problems, Sharlee Climer, Weixiong Zhang
Limit Crossing For Decision Problems, Sharlee Climer, Weixiong Zhang
All Computer Science and Engineering Research
Limit crossing is a methodology in which modified versions of a problem are solved and compared, yielding useful information about the original problem. Pruning rules that are used to exclude portions of search trees are excellent examples of the limit-crossing technique. In our previous work, we examined limit crossing for optimization problems. In this paper, we extend this methodology to decision problems. We demonstrate the use of limit crossing in our design of a tool for identifying K-SAT backbones. This tool is guaranteed to identify all of the backbone variables by solving at most n+1 formulae, where n is the …
The Real Effect Of Warm-Cool Colors, Reynold J. Bailey, Cindy M, Grimm, Chris Davoli
The Real Effect Of Warm-Cool Colors, Reynold J. Bailey, Cindy M, Grimm, Chris Davoli
All Computer Science and Engineering Research
The phenomenon of warmer colors appearing nearer in depth to viewers than cooler colors has been studied extensively by psychologists and other vision researchers. The vast majority of these studies have asked human observers to view physically equidistant, colored stimuli and compare them for relative depth. However, in most cases, the stimuli presented were rather simple: straight colored lines, uniform color patches, point light sources, or symmetrical objects with uniform shading. Additionally, the colors used were typically highly saturated. Although such stimuli are useful in isolating and studying depth cues in certain contexts, they leave open the question of whether …
The Remote-Clique Problem Revisited, Benjamin E. Birnbaum
The Remote-Clique Problem Revisited, Benjamin E. Birnbaum
All Computer Science and Engineering Research
Given a positive integer k and a complete graph with non-negative edge weights that satisfy the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this thesis, we present an algorithm called d-Greedy Augment that generalizes this greedy algorithm (they are equivalent when d = 1). We use the technique of factor-revealing linear programs to prove that d-Greedy Augment, which has a running time of …
Fast Packet Classification Using Bloom Filters, Sarang Dharmapurikar, Haoyu Song, Jonathan Turner, John Lockwood
Fast Packet Classification Using Bloom Filters, Sarang Dharmapurikar, Haoyu Song, Jonathan Turner, John Lockwood
All Computer Science and Engineering Research
While the problem of general packet classification has received a great deal of attention from researchers over the last ten years, there is still no really satisfactory solution. Ternary Content Addressable Memory (TCAM), although widely used in practice, is both expensive and consumes a lot of power. Algorithmic solutions, which rely on commodity memory chips, are relatively inexpensive and power-efficient, but have not been able to match the generality and performance of TCAMs. In this paper we propose a new approach to packet classification, which combines architectural and algorithmic techniques. Our starting point is the well-known crossproducting algorithm, which is …
Smooth Key-Framing Using The Image Plane, Leon Barrett, Cindy Grimm
Smooth Key-Framing Using The Image Plane, Leon Barrett, Cindy Grimm
All Computer Science and Engineering Research
This paper demonstrates the use of image-space constraints for key frame interpolation. Interpolating in image-space results in sequences with predictable and controlable image trajectories and projected size for selected objects, particularly in cases where the desired center of rotation is not fixed or when the key frames contain perspective distortion changes. Additionally, we provide the user with direct image-space control over {\em how} the key frames are interpolated by allowing them to directly edit the object's projected size and trajectory. Image-space key frame interpolation requires solving the inverse camera problem over a sequence of point constraints. This is a variation …
Control Of Decoherence In Open Quantum Systems, Narayan Ganesan
Control Of Decoherence In Open Quantum Systems, Narayan Ganesan
All Computer Science and Engineering Research
No abstract provided.
Smooth Surface Reconstruction Using Charts For Medical Data, Cindy Grimm, Tao Ju
Smooth Surface Reconstruction Using Charts For Medical Data, Cindy Grimm, Tao Ju
All Computer Science and Engineering Research
We present a surface reconstruction technique that constructs a smooth analytic surface from scattered data. The technique is robust to noise and both poorly and non-uniformly sampled data, making it well-suited for use in medical applications. In addition, the surface can be parameterized in multiple ways, making it possible to represent additional data, such as electromagnetic potential, in a different (but related) coordinate system to the geometric one. The parameterization technique also supports consistent parameterizations of multiple data sets.
Adaptive Embedded Roadmaps For Sensor Networks, Gazihan Alankus, Nuzhet Atay, Chenyang Lu, Burchan Bayazit
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 …
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 …
Design And Evaluation Of Packet Classification Systems, Doctoral Dissertation, December 2006, Haoyu Song
Design And Evaluation Of Packet Classification Systems, Doctoral Dissertation, December 2006, Haoyu Song
All Computer Science and Engineering Research
Although many algorithms and architectures have been proposed, the design of efficient packet classification systems remains a challenging problem. The diversity of filter specifications, the scale of filter sets, and the throughput requirements of high speed networks all contribute to the difficulty. We need to review the algorithms from a high-level point-of-view in order to advance the study. This level of understanding can lead to significant performance improvements. In this dissertation, we evaluate several existing algorithms and present several new algorithms as well. The previous evaluation results for existing algorithms are not convincing because they have not been done in …
Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Kevin Klues, Guoliang Xing, Chenyang Lu
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 …
Extending Byzantine Fault Tolerance To Replicated Clients, Ian Wehrman, Sajeeva L. Pallemulle, Kenneth J. Goldman
Extending Byzantine Fault Tolerance To Replicated Clients, Ian Wehrman, Sajeeva L. Pallemulle, Kenneth J. Goldman
All Computer Science and Engineering Research
Byzantine agreement protocols for replicated deterministic state machines guarantee that externally requested operations continue to execute correctly even if a bounded number of replicas fail in arbitrary ways. The state machines are passive, with clients responsible for any active ongoing application behavior. However, the clients are unreplicated and outside the fault-tolerance boundary. Consequently, agreement protocols for replicated state machines do not guarantee continued correct execution of long-running client applications. Building on the Castro and Liskov Byzantine Fault Tolerance protocol for unreplicated clients (CLBFT), we present a practical algorithm for Byzantine fault-tolerant execution of long-running distributed applications in which replicated deterministic …
Supporting Collaborative Behavior In Manets Using Workflows, Rohan Sen, Gregory Hackmann, Mart Haitjema, Gruia-Catalin Roman, Gill
Supporting Collaborative Behavior In Manets Using Workflows, Rohan Sen, Gregory Hackmann, Mart Haitjema, Gruia-Catalin Roman, Gill
All Computer Science and Engineering Research
Groupware activities provide a powerful representation for many collaborative tasks. Today, the technologies that support typical groupware applications often assume a stable wired network infrastructure. The potential for collaboration in scenarios that lack this fixed infrastructure remains largely untapped. Such scenarios include activities on construction sites, wilderness exploration, disaster recovery, and rapid intervention teams. Communication in these scenarios can be supported using wireless ad hoc networks, an emerging technology whose full potential is yet to be understood and realized. In this paper, we consider the fundamental technical issues that need to be addressed in order to introduce groupware concepts into …
A Query-Centric Approach To Supporting The Development Of Context-Aware Applications For Mobile Ad Hoc Networks, Doctoral Dissertation, August 2006, Jamie Payton
All Computer Science and Engineering Research
The wide-spread use of mobile computing devices has led to an increased demand for applications that operate dependably in opportunistically formed networks. A promising approach to supporting software development for such dynamic settings is to rely on the context-aware computing paradigm, in which an application views the state of the surrounding ad hoc network as a valuable source of contextual information that can be used to adapt its behavior. Collecting context information distributed across a constantly changing network remains a significant technical challenge. This dissertation presents a query-centered approach to simplifying context interactions in mobile ad hoc networks. Using such …
Perceptually Meaningful Image Editing: Depth, Reynold J. Bailey, Cindy Grimm
Perceptually Meaningful Image Editing: Depth, Reynold J. Bailey, Cindy Grimm
All Computer Science and Engineering Research
We introduce the concept of perceptually meaningful image editing and present two techniques for manipulating the apparent depth of objects in an image. The user loads an image, selects an object and specifies whether the object should appear closer or further away. The system automatically determines target values for the object and/or background that achieve the desired depth change. These depth editing operations, based on techniques used by traditional artists, manipulate either the luminance or color temperature of different regions of the image. By performing blending in the gradient domain and reconstruction with a Poisson solver, the appearance of false …
Design Of A Diversified Network Substrate, Jonathan Turner
Design Of A Diversified Network Substrate, Jonathan Turner
All Computer Science and Engineering Research
A diversified network substrate enables multiple end-to-end metanetworks to co-exist within a shared physical infrastructure. Metanetworks are implemented by metarouters, hosted by substrate routers, and metarouters are connected by metalinks. The substrate allocates resources (both link bandwidth and processing resources) to metarouters based on advance reservations received from metanetwork planning systems. It also enables dynamic creation of access metalinks, connecting end systems to metarouters, and supports mobility of end systems under the control of their metanetworks. This report defines a model for a diversified internet and presents a detailed design of the substrate that enables metanetworks to co-exist. The design …
A Proposed Architecture For The Geni Backbone Platform, Jonathan Turner
A Proposed Architecture For The Geni Backbone Platform, Jonathan Turner
All Computer Science and Engineering Research
The GENI Project (Global Environment for Network Innovation) is a major NSF-sponsored initiative that seeks to create a national research facility to enable experimental deployment of innovative new network architectures on a sufficient scale to enable realistic evaluation. One key component of the GENI system will be the GENI Backbone Platform (GBP) that provides the resources needed to allow multiple experimental networks to co-exist within the shared GENI infrastructure. This report reviews the objectives for the GBP, reviews the key issues that affect its design and develops a detailed reference architecture in order to provide a concrete example for how …
Virtualizing Network Processors, Ben Wun, Jonathan Turner, Patrick Crowley
Virtualizing Network Processors, Ben Wun, Jonathan Turner, Patrick Crowley
All Computer Science and Engineering Research
This paper considers the problem of virtualizing the resources of a network processor (NP) in order to allow multiple third-parties to execute their own virtual router software on a single physical router at the same time. Our broad interest is in designing such a router capable of supporting virtual networking. We discuss the issues and challenges involved in this virtualization, and then describe specific techniques for virtualizing both the control and data-plane processors on NPs. For Intel IXP NPs in particular, we present a dynamic, macro-based technique for virtualization that allows multiple virtual routers to run on multiple data plane …
Fair Efficiency, Or Low Average Delay Without Starvation, Christoph Jechlitschek, Sergey Gorinksky
Fair Efficiency, Or Low Average Delay Without Starvation, Christoph Jechlitschek, Sergey Gorinksky
All Computer Science and Engineering Research
Elastic applications are primarily interested in minimal delay achievable for their messages under current network load. In this paper, we investigate how to transmit such messages over a bottleneck link efficiently and fairly.
Feature Detection Using Curvature Maps And The Min-Cut/Max-Flow Graph Cut Algorithm, Timothy Gatzke, Cindy Grimm
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 …
Mobiwork: Mobile Workflow For Manets, Gregory Hackmann, Rohan Sen, Mart Haitjema, Gruia-Catalin Roman, Gill
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 …
The Meta-Theory Of Q_0 In The Calculus Of Inductive Constructions, Master's Thesis, May 2006, Li-Yang Tan
The Meta-Theory Of Q_0 In The Calculus Of Inductive Constructions, Master's Thesis, May 2006, Li-Yang Tan
All Computer Science and Engineering Research
The notion of a proof is central to all of mathematics. In the language of formal logic, a proof is a finite sequence of inferences from a set of axioms, and any statement one yields from such a finitistic procedure is called a theorem. For better or for worse, this is far from the form a traditional mathematical proof takes. Mathematicians write proofs that omit routine logical steps, and details deemed tangential to the central result are often elided. These proofs are fuzzy and human-centric, and a great amount of context is assumed on the part of the reader. While …
Efficient Mapping Of Virtual Networks Onto A Shared Substrate, Jing Lu, Jonathan Turner
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, …
Sliver: A Bpel Workflow Process Execution Engine For Mobile Devices, Gregory Hackmann, Mart Haitjema, Christopher Gill, Catalin-Gruia Roman
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 …
Real-Time Memory Management: Life And Times, Andrew Borg, Andy Wellings, Christopher Gill, Ron K. Cytron
Real-Time Memory Management: Life And Times, Andrew Borg, Andy Wellings, Christopher Gill, Ron K. Cytron
All Computer Science and Engineering Research
As high integrity real-time systems become increasingly large and complex, forcing a static model of memory usage becomes untenable. The challenge is to provide a dynamic memory model that guarantees tight and bounded time and space requirements without overburdening the developer with memory concerns. This paper provides an analysis of memory management approaches in order to characterise the tradeoffs across three semantic domains: space, time and a characterisation of memory usage information such as the lifetime of objects. A unified approach to distinguishing the merits of each memory model highlights the relationship across these three domains, thereby identifying the class …
Dynamic Conflict-Free Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, John Stankovic
Dynamic Conflict-Free Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, John Stankovic
All Computer Science and Engineering Research
With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services in such networks. To meet this challenge, we present Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose networks and workloads, DCQS is specifically designed for query services supporting in-network data aggregation. DCQS has several important features. First, it optimizes the query performance and energy efficiency by exploiting the temporal properties and precedence constraints introduced by data aggregation. Second, it can efficiently adapt to dynamic workloads …
Reusable Models For Timing And Liveness Analysis Of Middleware For Distributed Real-Time And Embedded Systems, Venkita Subramonian, Christopher Gill, Cesar Sanchez, Henny Sipma
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 …
Acceleration Of Gapped Alignment In Blastp Using The Mercury System, Brandon B. Harris
Acceleration Of Gapped Alignment In Blastp Using The Mercury System, Brandon B. Harris
All Computer Science and Engineering Research
Protein databases have grown exponentially over the last decade. This exponential growth has made extracting valuable information from these databases increasingly time consuming. This project presents a new method of accelerating a commonly used program for performing similarity searching on protein databases, BLASTP. This project describes the design and implementation of Mercury BLASTP, a customized hardware accelerated variant of BLASTP. This project focuses on the gapped alignment stage of Mercury BLASTP and provides design details and implementation results.
Design And Analysis Of An Accelerated Seed Generation Stage For Blastp On The Mercury System - Master's Thesis, August 2006, Arpith Jacob
Design And Analysis Of An Accelerated Seed Generation Stage For Blastp On The Mercury System - Master's Thesis, August 2006, Arpith Jacob
All Computer Science and Engineering Research
NCBI BLASTP is a popular sequence analysis tool used to study the evolutionary relationship between two protein sequences. Protein databases continue to grow exponentially as entire genomes of organisms are sequenced, making sequence analysis a computationally demanding task. For example, a search of the E. coli. k12 proteome against the GenBank Non-Redundant database takes 36 hours on a standard workstation. In this thesis, we look to address the problem by accelerating protein searching using Field Programmable Gate Arrays. We focus our attention on the BLASTP heuristic, building on work done earlier to accelerate DNA searching on the Mercury platform. We …
A Comprehensive Analysis Of The Effect Of Microarray Data, Monika Ray, Johannes Freudenberg, Weixiong Zhang
A Comprehensive Analysis Of The Effect Of Microarray Data, Monika Ray, Johannes Freudenberg, Weixiong Zhang
All Computer Science and Engineering Research
Background: Microarray data preprocessing, such as differentially expressed (DE) genes selection, is performed prior to higher level statistical analysis in order to account for technical variability. Preprocessing for the Affymetrix GeneChip includes background correction, normalisation and summarisation. Numerous preprocessing methods have been proposed with little consensus as to which is the most suitable. Furthermore, due to poor concordance among results from cross-platform analyses, protocols are being developed to enable cross-platform reproducibility. However, the effect of data analysis on a single platform is still unknown. The objective of our study is two-fold: first to determine whether there is consistency in the …