Digital Commons Network^™

Bit-Sequences: A New Cache Invalidation Method In Mobile Environments, Jin Jing, Ahmed K. Elmagarmid, Abdelsalam Helal, Rafael Alonso

Department of Computer Science Technical Reports

No abstract provided.

Partitioned Data Management In Mobile Environments, Ahmed K. Elmagarmid, Jin Jing, Abdelsalam Helal, Rafael Alonso

Department of Computer Science Technical Reports

No abstract provided.

The New Jersey Machine-Code Toolkit, Norman Ramsey, Mary F. Fernáyesndez

Department of Computer Science Technical Reports

No abstract provided.

Lightweight Write Detection And Checkpointing For Fine-Grained Persistence, Antony L. Hosking, J. Eliot B. Moss

Department of Computer Science Technical Reports

No abstract provided.

Sliced Configuration Spaces For Curved Planar Bodies, Elisha Sacks, Chandrajit Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Inverse Pattern Matching, Amihood Amir, Alberto Apostolico, Moshe Lewenstein

Department of Computer Science Technical Reports

No abstract provided.

Adaptive Methods For Distributed Video Presentation, Crispin Cowan, Shanwei Cen, Jonathan Walpole, Carlton Pu

Computer Science Faculty Publications and Presentations

This paper describes problems and solutions for delivering real-time, multi-media presentations across the Internet. A key characteristic of presentations of continuous media datatypes, such as digital video and audio, is their need for predictable real-time data delivery. For example, an NTSC quality video presentation requires video frames to be displayed every 1/30th of a second. Variations in this display rate can be observable as stalls or glitches in the video stream and reduce the quality of the presentation [6]. Delivering such presentations across the Internet is difficult because highly variable band- width and latency make it difficult to predict the …

A 2-2/3 Approximation For The Shortest Superstring Problem, Chris Armen, Clifford Stein

Computer Science Technical Reports

Given a collection of strings S={s_1, ..., s_n} over an alphabet \Sigma, a superstring \alpha of S is a string containing each s_i as a substring; that is, for each i, 1<=i<=n, \alpha contains a block of |s_i| consecutive characters that match s_i exactly. The shortest superstring problem is the problem of finding a superstring \alpha of minimum length. The shortest superstring problem has applications in both data compression and computational biology. In data compression, the problem is a part of a general model of string compression proposed by Gallant, Maier and Storer (JCSS '80). Much of the recent interest in the problem is due to its application to DNA sequence assembly. The problem has been shown to be NP-hard; in fact, it was shown by Blum et al.(JACM '94) to be MAX SNP-hard. The first O(1)-approximation was also due to Blum et al., who gave an algorithm that always returns a superstring no more than 3 times the length of an optimal solution. Several researchers have published results that improve on the approximation ratio; of these, the best previous result is our algorithm ShortString, which achieves a 2 3/4-approximation (WADS '95). We present our new algorithm, G-ShortString, which achieves a ratio of 2 2/3. It generalizes the ShortString algorithm, but the analysis differs substantially from that of ShortString. Our previous work identified classes of strings that have a nested periodic structure, and which must be present in the worst case for our algorithms. We introduced machinery to descibe these strings and proved strong structural properties about them. In this paper we extend this study to strings that exhibit a more relaxed form of the same structure, and we use this understanding to obtain our improved result.

Intelligent Multimedia Tutoring For Manufacturing Education, Erika Rogers, Yolanda Kennedy, T. Walton, P. Nelms, I. Sherry

Computer Science and Software Engineering

This paper describes current work on the design and implementation of intelligent multimedia tutoring modules which are intended to supplement short training courses in Nondestructive Inspection for the Boeing Defense and Space group.

Multi-View Access Protcols For Large-Scale Replication, Xiangning (Sean) Liu, Abdelsalam (Sumi) Helal, Bharat K. Bhargava

Department of Computer Science Technical Reports

No abstract provided.

A Simple Solver For Linear Equations Containing Nonlinear Operators, Norman Ramsey

Department of Computer Science Technical Reports

No abstract provided.

Sequence Alignment In Molecular Biology, Alberto Apostolico, Raffaele Fiancarlo

Department of Computer Science Technical Reports

No abstract provided.

On The Impact Of Forgetting On Learning Machines, Rūsiņš Freivalds, Efim Kinber, Carl H. Smith

School of Computer Science & Engineering Faculty Publications

People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For …

Measurement Of The Bs0 Lifetime And Production Rate With Ds- ℓ+ Combinations In Z Decays, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

A precise determination of the effective Bs0→K+K− lifetime can be used to constrain contributions from physics beyond the Standard Model in the Bs0 meson system. Conventional approaches select B meson decay products that are significantly displaced from the B meson production vertex. As a consequence, B mesons with low decay times are suppressed, introducing a bias to the decay time spectrum which must be corrected. This analysis uses a technique that explicitly avoids a lifetime bias by using a neural network based trigger and event selection. Using 1.0fb−1 of data recorded by the LHCb experiment, the effective Bs0→K+K− lifetime is …

Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier

Computer Science Faculty Publications and Presentations

Multimedia computing promises access to any type of visual or aural medium on the desktop. But in this networked future, will every type of media be accessible from every terminal device? Current multimedia standards do not allow content that is authored for high-bandwidth workstations to scale down for low-bandwidth applications. The problem is that application requests are commonly interpreted as requests for the highest possible quality and resource overloads are handled by ad hoc methods. We can begin to solve this problem by specifying Quality of Service (QOS) requirements based on functionality rather than on content encoding and device capabilities.

Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier

Computer Science Faculty Publications and Presentations

Multimedia computing promises access to any type of visual or aural medium on the desktop. But in this networked future, will every type of media be accessible from every terminal device? Current multimedia standards do not allow content that is authored for high-bandwidth workstations to scale down for low-bandwidth applications. The problem is that application requests are commonly interpreted as requests for the highest possible quality and resource overloads are handled by ad hoc methods. We can begin to solve this problem by specifying Quality of Service (QOS) requirements based on functionality rather than on content encoding and device capabilities.

Customizable Operating Systems, Jonathan Walpole, Crispin Cowan, Andrew P. Black, Jon Inouye, Calton Pu, Shanwei Cen

Computer Science Faculty Publications and Presentations

A customizable operating system is one that can adapt to improve its functionality or performance. The need for customizable and application-specific operating systems has been recognized for many years, but they have yet to appear in the commercial market. This paper explores the notion of operating system customizability and examines the limits of existing approaches. The paper begins by surveying system structuring approaches for the safe and efficient execution of customizable operating systems. Then it discusses the burden that existing approaches impose on application software, and explores techniques for reducing this burden. Finally, support for customizability in the Synthetix project …

Quality Of Service Specification For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier

Computer Science Faculty Publications and Presentations

The bandwidth limitations of multimedia systems force tradeoffs between presentation data fidelity and real-time performance. For example, digital video is commonly encoded with lossy compression to reduce bandwidth and frames may be skipped during playback to maintain synchronization. These tradeoffs depend on device performance and physical data representations that are hidden by a database system. If a multimedia database is to support digital video and other continuous media data types, we argue that the database should provide a Quality of Service (QOS) interface to allow application control of presentation timing and information loss tradeoffs.

This paper proposes a data model …

Automatic Visual Recognition Using Parallel Machines, Yui-Liang Chen

Dissertations

Invariant features and quick matching algorithms are two major concerns in the area of automatic visual recognition. The former reduces the size of an established model database, and the latter shortens the computation time. This dissertation, will discussed both line invariants under perspective projection and parallel implementation of a dynamic programming technique for shape recognition. The feasibility of using parallel machines can be demonstrated through the dramatically reduced time complexity.

In this dissertation, our algorithms are implemented on the AP1000 MIMD parallel machines. For processing an object with a features, the time complexity of the proposed parallel algorithm is O(n) …

Complexity Analysis Of Two Permutations Used By Fast Cosine Transform Algorithms, Sean S.B. Moore, Leonard F. Wisniewski

Computer Science Technical Reports

Recently developed fast cosine transform (FCT) algorithms require fewer operations than any other known general algorithm. Similar to related fast transform algorithms (e.g., the FFT), these algorithms permute the data before, during, or after the computation of the transform. The choice of this permutation may be an important consideration in reducing the complexity of the permutation algorithm. In this paper, we derive the complexity to generate the permutation mappings used in these FCT algorithms for power-of-2 data sets by representing them as linear index transformations and translating them into combinational circuits. Moreover, we show that one of these permutations not …

Estimating Time Available For Sensor Fusion Exception Handling, Robin R. Murphy, Erika Rogers

Computer Science and Software Engineering

In previous work, we have developed a generate, test, and debug methodology for detecting, classifying, and responding to sensing failures in autonomous and semi-autonomous mobile robots. An important issue has arisen from these efforts: how much time is there available to classify the cause of the failure and determine an alternative sensing strategy before the robot mission must be terminated?

In this paper, we consider the impact of time for teleoperation applications where a remote robot attempts to autonomously maintain sensing in the presence of failures yet has the option to contact the local for further assistance. Time limits are …

Formal Methods: How, When, And Why They Are Used, Beth Arrowsmith, Bruce Mcmillin, Ralph Wilkerson

Computer Science Technical Reports

Formal methods, theoretically a wonderful concept for ensuring a program's correctness, are not widely used in practice. This dichotomy between what theory advocates and practice might be due to programmers' lack of experience with formal methods. To determine if this was the case, a module on Formal Methods was introduced into a graduate course on distributed systems. This module first introduced the students to the theory of formal methods and then required students to program a distributed problem in CCSP, a subset of CSP, using formal methods. The results were abysmal. Students avoided using formal methods. When they did use …

Atomic Broadcast In Heterogeneous Distributed Systems, Osman Zeineldine

Computer Science Theses & Dissertations

Communication services have long been recognized as possessing a dominant effect on both performance and robustness of distributed systems. Distributed applications rely on a multitude of protocols for the support of these services. Of crucial importance are multicast protocols. Reliable multicast protocols enhance the efficiency and robustness of distributed systems. Numerous reliable multicast protocols have been proposed, each differing in the set of assumptions adopted, especially for the communication network. These assumptions make each protocol suitable for a specific environment. The presence of different distributed applications that run on different LANs and single distributed applications that span different LANs mandate …

Text Independent Speaker Verification Using Binary-Pair Partitioned Neural Networks, Claude A. Norton Iii

Electrical & Computer Engineering Theses & Dissertations

A method is presented for the application of binary-pair partitioned neural networks to the task of speaker verification. This technique is based on a previously developed neural network classifier for speaker identification.

The main focus of this research was the development and testing of the algorithms necessary to extend the binary-pair partitioning approach from speaker identification to speaker verification. The method is based on the development of a user profile which is obtained from discriminative data provided by the binary-pair partitioned neural networks.

Experimental results are provided which demonstrate the viability of this approach, using the TIMIT speech corpus for …

A Provably Convergent Dynamic Training Method For Multi-Layer Perceptron Networks, Timothy L. Andersen, Tony R. Martinez

Faculty Publications

This paper presents a new method for training multi-layer perceptron networks called DMP1 (Dynamic Multilayer Perceptron 1). The method is based upon a divide and conquer approach which builds networks in the form of binary trees, dynamically allocating nodes and layers as needed. The individual nodes of the network are trained using a genetic algorithm. The method is capable of handling real-valued inputs and a proof is given concerning its convergence properties of the basic model. Simulation results show that DMP1 performs favorably in comparison with other learning algorithms.

Structured Permuting In Place On Parallel Disk Systems, Leonard F. Wisniewski

Computer Science Technical Reports

The ability to perform permutations of large data sets in place reduces the amount of necessary available disk storage. The simplest way to perform a permutation often is to read the records of a data set from a source portion of data storage, permute them in memory, and write them to a separate target portion of the same size. It can be quite expensive, however, to provide disk storage that is twice the size of very large data sets. Permuting in place reduces the expense by using only a small amount of extra disk storage beyond the size of the …

Implementation Of A Campuswide Distributed Mass Storage Service: The Dream Versus Reality, Betty Jo Armstead, Stephen Prahst

Armstead Publications and Presentations

In 1990, a technical team at NASA Lewis Research Center, Cleveland, Ohio, began defining a Mass Storage Service to provide long-term archival storage, short-term storage for very large files, distributed Network File System access, and backup services for critical data that resides on workstations and personal computers. Because of software availability and budgets, the total service was phased in over 3 years. During the process of building the service from the commercial technologies available, our Mass Storage Team refined the original vision and learned from the problems and mistakes that occurred. We also enhanced some technologies to better meet the …

Calibration Of The System Evaluation And Estimation Of Resources Software Estimation Model (Seer-Sem) For The Air Force Space And Missile Systems Center (Smc), Kolin D. Rathmann

Theses and Dissertations

This study examined whether calibration of the SEER-SEM impacted the effort estimates generated by the model for software developments- A historical database was provided by the Space and Missile System's Center Los Angeles, and used as the model's input data. The data was stratified into four usable platforms, military ground command and-control, military ground signal processing, military specification avionics, and military mobile. Each platform's data sets were split, the majority of points for calibration of the model, and the rest for model validation. The accuracy of SEER to this particular data set is limited, yet the model did respond to …

Calibration Of The Software Architecture Sizing And Estimation Tool (Saset), Carl D. Vegas

Theses and Dissertations

This study attempted to analyze the effect of calibration on the performance of the SASET computer software cost estimating model. Data used for input into the model were drawn from the most current USAF SMC Software Database (SWDB). Once all the records to be used for analysis were identified, the DBMS-Calibration tool (which is part of SASET) was used to perform regression analysis on the relationship between program size (measured in SLOC) and the effort required to develop the program (measured in man-months). Productivity information reported from this tool was then input into equations used to calculate the Productivity Calibration …

A Comparative Evaluation Of Voice Versus Keypad Input For Manipulating Electronic Technical Data For Flight Line Maintenance Technicians, David A. Chapman, James R. Simmons

Theses and Dissertations

Interactive Electronic Technical Manuals will soon become a requirement for aircraft maintenance technicians. An important aspect in their development is the selection of an input device that will enhance, rather than impede, technician performance. The purpose of this thesis was to evaluate two types of input devices that can he used: a voice recognition input and a keypad input. Studies to date have evaluated the superiority of digital data over paper data, and advantages of using a Head Mounted Display Device over a flat screen laptop computer. No research has evaluated the input device. An experiment was conducted to determine …