Computer Sciences Commons^™

Dsim: A Distance-Based Indexing Method For Genomic Sequences, Xia Cao, Beng-Chin Ooi, Hwee Hwa Pang, Kian-Lee Tan, Anthony K. H. Tung

Research Collection School Of Computing and Information Systems

In this paper, we propose a Distance-based Sequence Indexing Method (DSIM) for indexing and searching genome databases. Borrowing the idea of video compression, we compress the genomic sequence database around a set of automatically selected reference words, formed from high-frequency data substrings and substrings in past queries. The compression captures the distance of each non-reference word in the database to some reference word. At runtime, a query is processed by comparing its substrings with the compressed data strings, through their distances to the reference words. We also propose an efficient scheme to incrementally update the reference words and the compressed …

Nil Is Not Nothing: Recognition Of Chinese Network Informal Language Expressions, Yunqing Xia, Wong, Wei Gao, Wei Gao

Research Collection School Of Computing and Information Systems

Informal language is actively used in network-mediated communication, e.g. chat room, BBS, email and text message. We refer the anomalous terms used in such context as network informal language (NIL) expressions. For example, “偶(ou3)” is used to replace “我(wo3)” in Chinese ICQ. Without unconventional resource, knowledge and techniques, the existing natural language processing approaches exhibit less effectiveness in dealing with NIL text. We propose to study NIL expressions with a NIL corpus and investigate techniques in processing NIL expressions. Two methods for Chinese NIL expression recognition are designed in NILER system. The experimental results show that pattern matching method produces …

Common Pattern Discovery Using Earth Mover's Distance And Local Flow Maximization, Hung-Khoon Tan, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

In this paper, we present a novel segmentation-insensitive approach for mining common patterns from 2 images. We develop an algorithm using the earth movers distance (EMD) framework, unary and adaptive neighborhood color similarity. We then propose a novel local flow maximization approach to provide the best estimation of location and scale of the common pattern. This is achieved by performing an iterative optimization in search of the most stable flows' centroid. Common pattern discovery is difficult owing to the huge search space and problem domain. We intend to solve this problem by reducing the search space through identifying the location …

Towards Semantic Service Request Of Web Service Composition, Qianhui Althea Liang, Jen-Yao Chung, Steven M. Miller

Research Collection School Of Computing and Information Systems

When meeting the challenges in automatic and semi-automatic Web service composition, capturing the user's service demand and preferences is as important as knowing what the services can do. This paper discusses the idea of semantic service requests for composite services, and presents a way to model the elements of a composite service request as user preferences and constraints. The model is based on an interactive and iterative strategy meant to obtain the exact requirements from potential service consumers. The markup vocabularies and associated inference mechanism of OWL-S are used as a means to bring semantics to service requests. Language constructs …

Automatic 3d Face Modeling Using 2d Active Appearance Models, Jianke Zhu, Steven Hoi, Michael R. Lyu

Research Collection School Of Computing and Information Systems

Although a lot of promising research findings have been studied on 3D face modeling in the past years, it is still a challenge to generate realistic 3D human face models and facial animations. This paper presents a novel approach to model 3D faces automatically from still images or video sequences without manual interactions. Our proposed scheme comprises three steps. First, we offline construct 3D shape models using Active Appearance Models (AAMs), which saves large computation costs for online modeling. Second, based on the computed 3D shape models, we propose an efficient algorithm to estimate the parameters of 3D pose and …

Informal Animation Sketching With K-Sketch, Richard C. Davis

Research Collection School Of Computing and Information Systems

Animation is a powerful medium that is accessible to few, because current animation tools are extremely complex. This complexity arises partially from current tools’ focus on precise, often unnecessary details and partially from the difficulty of finding a small but sufficiently powerful set of tool features. We are designing K-Sketch, an informal 2D animation tool that uses sketching and demonstration to radically reduce the time needed to create an animation. Our field studies investigating the needs of current anima-tion tool users and would-be users are helping us to mini-mize complexity by showing us how to prioritize the many possible tool …

Performance Evaluation Of Distributed Security Protocols Using Discrete Event Simulation, Meiyuan Zhao

Dartmouth College Ph.D Dissertations

The Border Gateway Protocol (BGP) that manages inter-domain routing on the Internet lacks security. Protective measures using public key cryptography introduce complexities and costs. To support authentication and other security functionality in large networks, we need public key infrastructures (PKIs). Protocols that distribute and validate certificates introduce additional complexities and costs. The certification path building algorithm that helps users establish trust on certificates in the distributed network environment is particularly complicated. Neither routing security nor PKI come for free. Prior to this work, the research study on performance issues of these large-scale distributed security systems was minimal. In this thesis, …

Phylogenetic Analysis Of Large Sequence Data Sets, Hyrum Carroll, Mark J. Clement, Keith Crandall, Quinn O. Snell

Faculty Publications

Phylogenetic analysis is an integral part of biological research. As the number of sequenced genomes increases, available data sets are growing in number and size. Several algorithms have been proposed to handle these larger data sets. A family of algorithms known as disc covering methods (DCMs), have been selected by the NSF funded CIPRes project to boost the performance of existing phylogenetic algorithms. Recursive Iterative Disc Covering Method 3 (Rec-I-DCM3), recursively decomposes the guide tree into subtrees, executing a phylogenetic search on the subtree and merging the subtrees, for a set number of iterations. This paper presents a detailed analysis …

Rate-Adaptive Runlength Limited Encoding For High-Speed Infrared Communication, James Cyril Funk

Theses and Dissertations

My thesis will demonstrate that Rate Adaptive Runlength Limited encoding (RA-RLL) achieves high data rates with acceptable error rate over a wide range of signal distortion/attenuation, and background noise. RA-RLL has performance superior to other infrared modulation schemes in terms of bandwidth efficiency, duty cycle control, and synchronization frequency. Rate adaptive techniques allow for quick convergence of RA-RLL parameters to acceptable values. RA-RLL may be feasibly implemented on systems with non-ideal timing and digital synchronization.

Expanding The Use Of Cellular Automata, Joseph Bertles

Computer Science Honors Theses

Cellular automata are a type of simulation based upon dividing space into cells. More specifically, cellular automata are characterized by parallelism, locality, and homogeneity. A simulation is run by conducting a series of updates, consisting of running a set of rules that all cells follow. The rules typically consist of looking at a cell's immediate neighbors and/or itself to determine what will be in the cell at the next step. The rules are applied to all the cells at exactly the same time in exactly the same manner. The use of cellular automata has been limited to computer scientists, those …

Development Of Database And Web Site For D3multisport, Jay Garrison

Regis University Student Publications (comprehensive collection)

Before this project, D3Multisport.com did not have a software application to track and monitor personal and progress information on athletes training for triathlon events. The previous process was manual, and although it helped provide a training schedule for an athlete it required the data be updated by hand. The process of developing a training program on an excel spreadsheet provided a good basis for the athlete to start the program, but was not suited to make dynamic adjustments if not optimally suited for the athlete. The application created in this project was designed to keep a coach updated on the …

Continuations From Generalized Stack Inspection, Greg Pettyjohn, John Clements, Joe Marshall, Shriram Krishnamurthi, Matthias Felleisen

Computer Science and Software Engineering

Implementing first-class continuations can pose a challenge if the target machine makes no provisions for accessing and re-installing the run-time stack. In this paper, we present a novel translation that overcomes this problem. In the first half of the paper, we introduce a theoretical model that shows how to eliminate the capture and the use of first-class continuations in the presence of a generalized stack inspection mechanism. The second half of the paper explains how to translate this model into practice in two different contexts. First, we reformulate the servlet interaction language in the PLT Web server, which heavily relies …

Structured Object-Oriented Co-Analysis/Co-Design Of Hardware/Software For The Facts Powers System, Matt Ryan, Sojan Markose, Xiaoqing Frank Liu, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

There are several approaches to the hardware/software design in embedded systems, ranging from the traditional sequential methods which focus on the determination of the hardware architecture prior to software design, to newer object-oriented approaches that attempt to apply software engineering methods to hardware design without a systematic process. This paper discusses a structured object-oriented methodology for the integrated co-analysis and co-design of hardware/software systems using an extended high order object-oriented modeling technique (HOOMT). This methodology offers a uniform method for hardware and software developers to jointly develop the specifications for and partitioning of the hardware and software components of a …

Laziness Without All The Hard Work: Combining Lazy And Strict Languages For Teaching, Eli Barzilay, John Clements

Computer Science and Software Engineering

Students have trouble understanding the difference between lazy and strict programming. It is difficult to compare the two directly, because popular strict languages and popular lazy languages differ in their syntax, in their type systems, and in other ways unrelated to the lazy/strict evaluation discipline. While teaching programming languages courses, we have discovered that an extension to PLT Scheme allows the system to accommodate both lazy and strict evaluation in the same system. Moreover, the extension is simple and transparent. Finally, the simple nature of the extension means that the resulting system provides a rich environment for both lazy and …

A Motion Planning Processor On Reconfigurable Hardware, Nuzhet Atay, Burchan Bayazit

All Computer Science and Engineering Research

Motion planning algorithms enable us to find feasible paths for moving objects. These algorithms utilize feasibility checks to differentiate valid paths from invalid ones. Unfortunately, the computationally expensive nature of such checks reduces the effectiveness of motion planning algorithms. However, by using hardware acceleration to speed up the feasibility checks, we can greatly enhance the performance of the motion planning algorithms. Of course, such acceleration is not limited to feasibility checks; other components of motion planning algorithms can also be accelerated using specially designed hardware. A Field Programmable Gate Array (FPGA) is a great platform to support such an acceleration. …

Importance Resampling For Global Illumination, Justin F. Talbot

Theses and Dissertations

This thesis develops a generalized form of Monte Carlo integration called Resampled Importance Sampling. It is based on the importance resampling sample generation technique. Resampled Importance Sampling can lead to significant variance reduction over standard Monte Carlo integration for common rendering problems. We show how to select the importance resampling parameters for near optimal variance reduction. We also combine RIS with stratification and with Multiple Importance Sampling for further variance reduction. We demonstrate the robustness of this technique on the direct lighting problem and achieve up to a 33% variance reduction over standard techniques. We also suggest using RIS as …

On-Disk Sequence Cache (Odsc): Using Excess Disk Capacity To Increase Performance, Christopher Ryan Slade

Theses and Dissertations

We present an on-disk sequence cache (ODSC), which improves disk drive performance. An ODSC uses a separate disk partition to store disk data in the order that the operating system requests it. Storing data in this order reduces the amount of seeking that the disk drive must do. As a result, the average disk access time is reduced. Reducing the disk access time improves the performance of the system, especially when booting the operating system, loading applications, and when main memory is limited. Experiments show that our ODSC speeds up application loads by as much as 413%. Our ODSC also …

Sink-To-Sensors Congestion Control, Ramanuja Vedantham, Raghupathy Sivakumar, Seung Jong Park

Computer Science Faculty Research & Creative Works

The problem of congestion in sensor networks is significantly different from conventional ad-hoc networks and has not been studied to any great extent thus far. In this paper, we focus on providing congestion control from the sink to the sensors in a sensor field. We identify the different reasons for congestion from the sink to the sensors and show the uniqueness of the problem in sensor network environments. We propose a scalable, distributed approach that addresses congestion from the sink to the sensors in a sensor network. Through ns2 based simulations, we evaluate the proposed framework, and show that it …

The Open Network Laboratory (A Resource For High Performance Networking Research), John Dehart, Fred Kuhns, Jyoti Parwatikar, Jonathan Turner, Ken Wong

All Computer Science and Engineering Research

The Open Network Laboratory (ONL) is a remotely accessible network testbed designed to enable network researchers to conduct experiments using high performance routers and applications. ONL™s Remote Laboratory Interface (RLI) allows users to easily configure a network topology, initialize and modify the routers™ routing tables, packet classification tables and queuing parameters. It also enables users to add software plugins to the embedded processors available at each of the routers™ ports, enabling the introduction of new functionality. The routers provide a large number of built-in counters to track various aspects of system usage, and the RLI software makes these available through …

Linear Equality Constraints And Homomorphous Mappings In Pso, Christopher K. Monson, Kevin Seppi

Faculty Publications

We present a homomorphous mapping that converts problems with linear equality constraints into fully unconstrained and lower-dimensional problems for optimization with PSO. This approach, in contrast with feasibility preservation methods, allows any unconstrained optimization algorithm to be applied to a problem with linear equality constraints, making available tools that are known to be effective and simplifying the process of choosing an optimizer for these kinds of constrained problems. The application of some PSO algorithms to a problem that has undergone the mapping presented here is shown to be more effective and more consistent than other approaches to handling linear equality …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 22, Number 1, September 2005, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Forms Of Expression For Designing Visual Languages For Animation, Richard Christopher Davis, James A. Landay

Research Collection School of Computing and Information Systems

We present further steps in our research into visual languages for animation. Animation is a rich mode of communication that is currently accessible to few, because animation systems are complex. Some systems try to make animation simple but put severe limits on users’ creative expression. Our field studies are demonstrating that would-be animators need to express animation in a wide variety of ways. We are developing a taxonomy of forms of expression for animation that will help the designers of visual languages for animation to determine which expressive forms to support. Our end goal is to build animation sketching systems …

Tracing Requirements To Defect Reports: An Application Of Information Retrieval Techniques, Suresh Yadla, Jane Huffman Hayes, Alex Dekhtyar

Computer Science and Software Engineering

To support debugging, maintenance, verification and validation (V&V) and/or independent V&V (IV&V), it is necessary to understand the relationship between defect reports and their related artifacts. For example, one cannot correct a code-related defect report without being able to find the code that is affected. Information retrieval (IR) techniques have been used effectively to trace textual artifacts to each other. This has generally been applied to the problem of dynamically generating a trace between artifacts in the software document hierarchy after the fact (after development has proceeded to at least the next lifecycle phase). The same techniques can also be …

Revisiting The Semantics Of Interval Probabilistic Logic Programs, Alex Dekhtyar, Michael I. Dekhtyar

Computer Science and Software Engineering

Two approaches to logic programming with probabilities emerged over time: bayesian reasoning and probabilistic satisfiability (PSAT). The attractiveness of the former is in tying the logic programming research to the body of work on Bayes networks. The second approach ties computationally reasoning about probabilities with linear programming, and allows for natural expression of imprecision in probabilities via the use of intervals.
In this paper we construct precise semantics for one PSAT-based formalism for reasoning with inteval probabilities, probabilistic logic programs (p-programs), orignally considered by Ng and Subrahmanian. We show that the probability ranges of atoms and formulas in p-programs cannot …

Co-Generation Of Text And Graphics, David Novick, Brian Lowe

Selected Works Temporary Series

content in documentation, it is possible to produce both text and graphics from a single common source. One approach to co-generation of text and graphics uses a single logical specification; a second approach starts with CAD-based representation and produces a corresponding textual account. This paper explores these two different approaches, reports the results of using prototypes embodying the approaches to represent simple figures, and discusses issues that were identified through use of the prototypes. While it appears feasible to co-generate text and graphics automatically, the process raises deep issues of design of communications, including the intent of the producer of …

Usability Over Time, Valerie Mendoza, David Novick

Selected Works Temporary Series

Testing of usability could perhaps be more accurately described as testing of learnability. We know more about the problems of novice users than we know of the problems of experienced users. To understand how these problems differ, and to understand how usability problems change as users change from novice to experienced, we conducted a longitudinal study of usability among middle-school teachers creating Web sites. The study looked at the use both the use of documentation and the underlying software, tracking the causes and extent of user frustration over eight weeks. We validated a categorization scheme for frustration episodes. We found …

Root Causes Of Lost Time And User Stress In A Simple Dialog System, Nigel Ward, Anais Rivera, Karen Ward, David Novick

Selected Works Temporary Series

As a priority-setting exercise, we compared interactions between users and a simple spoken dialog system to interactions between users and a human operator. We observed usability events, places in which system behavior differed from human behavior, and for each we noted the impact, root causes, and prospects for improvement. We suggest some priority issues for research, involving not only such core areas as speech recognition and synthesis and language understanding and generation, but also less-studied topics such as adaptive or flexible timeouts, turn-taking and speaking rate.

Ga-Facilitated Knn Classifier Optimization With Varying Similarity Measures, Michael R. Peterson, Travis E. Doom, Michael L. Raymer

Kno.e.sis Publications

Genetic algorithms are powerful tools for k-nearest neighbors classifier optimization. While traditional knn classification techniques typically employ Euclidian distance to assess pattern similarity, other measures may also be utilized. Previous research demonstrates that GAs can improve predictive accuracy by searching for optimal feature weights and offsets for a cosine similarity-based knn classifier. GA-selected weights determine the classification relevance of each feature, while offsets provide alternative points of reference when assessing angular similarity. Such optimized classifiers perform competitively with other contemporary classification techniques. This paper explores the effectiveness of GA weight and offset optimization for knowledge discovery using knn classifiers with …

Wireless Technology And Its Application In Wireless Local Area Networks Using The Ieee 802.11 Standards, Philip Curneen

Theses

This research thesis examines the area of wireless communication and its use in Wireless Local Area Networks (WLANs). It examines the Spread Spectrum methods of Frequency Hopping Spread Spectrum (FHSS) and Direct Sequence Spread Spectrum (DSSS) used in WLANs. The International Governing body, the Institute of Electrical and Electronic Engineers (IEEE) have devised standards and protocols called 802.11 to be used as guidelines for semiconductor chip and WLAN equipment manufacturers. These protocols have been adopted in implementing WLANs. Their specifications, which address data rates, bandwidth, power requirements, quality of service, spectrum management and security, are discussed in this thesis.

This …

Early Warning And Prediction Of Internet Attacks And Exploits, Brian P. Zeitz

Theses and Dissertations

A safe, secure, and functional information network is vital in today’s Air Force net centric environment. Information is more critical today than it has ever been. As more operational functions are placed in cyber space and greater computing power becomes available to everyone, keeping these networks safe and secure is an almost unattainable task. Network security entails Intrusion Detection Security, but another form of security or “insecurity” is quickly gaining attention. Honeypots allow the black hat community to attack and penetrate non-production systems. By monitoring and studying these attacks, network defenders can develop better Information Assurance tactics, techniques and procedures …