Tech Reports in Computer Science and Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/5

The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu

Browse

Now showing 1 - 20 of 1220

Hypothesis Testing with Errors in the Variables
(1995-02-06) David, Nancy; Stewart, G. W.
In this paper we give reason to hope that errors in regression variables are not as harmful as one might expect. Specifically, we will show that although the errors can change the values of the quantities one computes in a regression analysis, under certain conditions they leave the distributions of the quantities approximately unchanged.
An Iterative Method for Solving Linear Inequalities
(1995-02-06) Stewart, G. W.
This paper describes and analyzes a method for finding nontrivial solutions of the inequality $Ax \geq 0$, where $A$ is an $m \times n$ matrix of rank $n$. The method is based on the observation that a certain function $f$ has a unique minimum if and only if the inequality {\it fails to have} a nontrivial solution. Moreover, if there is a solution, an attempt to minimize $f$ will produce a sequence that will diverge in a direction that converges to a solution of the inequality. The technique can also be used to solve inhomogeneous inequalities and hence linear programming problems, although no claims are made about competitiveness with existing methods.
A Two-Stage Iteration for Solving Nearly Uncoupled Markov Chains
(1995-02-06) Stewart, G. W.; Stewart, W. J.; McAllister, D. F.
This paper is concerned with an iteration for determining the steady-state probability vector of a nearly uncoupled Markov Chain. The states of these chains can be partitioned into aggregates with low probabilities of transitions between aggregates. The iteration consists of alternating block Gauss--Seidel iterations with Rayleigh--Ritz refinements. Under natural regularity conditions, the composite iteration reduces the error by a factor proportional to the size of the coupling between aggregates, so that the more loosely the chain is coupled, the faster the convergence.
Invariant Subspaces and Capital Punishment (A Participatory Paper)
(1995-02-06) Stewart, G. W.
The notion of invariant subspaces is useful in a number of theoretical and practical applications. In this paper we give an elementary treatment of invariant subspaces that stresses their connection with simple eigenvalues and their eigenvectors.
A Study of File Manipulation by Novices Using Commands vs. Direct Manipulation
(1995-04-13) Margono, Sepeedeh; Shneiderman, Ben
There are three basic interactive styles of control in human interfaces with computers: command, menu, and direct manipulation. In the past few years, these three styles have become the subject of many studies. However, few comparisons have been done between interfaces that use direct manipulation and command styles. This experiment compares file manipulation operations on the Apple Macintosh, which has a direct manipulation interface, with the IBM PC with MS-DOS, which has the command interface. After a brief training period, novices accomplished file manipulation tasks more rapidly, with fewer errors and greater satisfaction with the Apple Macintosh. Problems arising for both versions are discussed and suggestions for improvements are made. (Also cross-referenced as CAR-TR-264)
Semantics for HTN Planning
(1998-10-15) Erol, Kutluhan; Hendler, James; Nau, Dana S.
(Also cross-referenced as ISR-TR-95-9) One big obstacle to understanding the nature of hierarchical task network (HTN) planning has been the lack of a clear theoretical framework. In particular, no one has yet presented a clear and concise HTN algorithm that is sound and complete. In this paper, we present a formal syntax and semantics for HTN planning. Based on this syntax and semantics, we are able to define an algorithm for HTN planning and prove it sound and complete. We also develop several definitions of expressivity for planning languages and prove that HTN Planning is strictly more expressive than STRIPS-style planning according to those definitions. (Also cross-referenced as UMIACS-TR-94-31)
Extraction of Rules from Discrete-Time Recurrent Neural Networks
(1998-10-15) Omlin, Christian W.; Giles, C. Lee
The extraction of symbolic knowledge from trained neural networks and the direct encoding of (partial) knowledge into networks prior to training are important issues. They allow the exchange of information between symbolic and connectionist knowledge representations. The focus of this paper is on the quality of the rules that are extracted from recurrent neural networks. Discrete-time recurrent neural networks can be trained to correctly classify strings of a regular language. Rules defining the learned grammar can be extracted from networks in the form of deterministic finite-state automata (DFA's) by applying clustering algorithms in the output space of recurrent state neurons. Our algorithm can extract different finite-state automata that are consistent with a training set from the same network. We compare the generalization performances of these different models and the trained network and we introduce a heuristic that permits us to choose among the consistent DFA's the model which best approximates the learned regular grammar. (Also cross-referenced as UMIACS-TR-95-54)
The Triangular Matrices of Gaussian Elimination and Related Decompositions
(1998-10-15) Stewart, G. W.
It has become a commonplace that triangular systems are solved to higher accuracy than their condition would warrant. This observation is not true in general, and counterexamples are easy to construct. However, it is often true of the triangular matrices from pivoted LU or QR decompositions. It is shown that this fact is closely connected with the rank-revealing character of these decompositions. (Also cross-referenced as UMIACS-TR-95-91)
1993 Human-Computer Interaction Laboratory Video Reports
(1998-10-15) Plaisant, Catherine (Editor)
Introduction and table of contents - Ben Shneiderman, [4:00] Dynamaps: dynamic queries on a health statistics atlas - Catherine Plaisant and Vinit Jain, [6:34], Hierarchical visualization with Treemaps: making sense of pro basketball data - Dave Turo, [10:47], TreeViz: file directory browsing - Brian Johnson, [10:04], HyperCourseware: computer integrated tools in the AT&T Teaching Theater - Kent Norman, [7:08], Improving access to medical abstracts: Grateful Med Interface prototype - Gary Marchionini, [6:08], Layout appropriateness: guiding interface desi gn with simple task descriptions - Andrew Sears, [4:00] (Also cross-referenced as CAR-TR-793)
Modeling Bit Rate Variations in MPEG Sources
(1998-10-15) Krunz, Marwan; Tripathi, Satish K.
In this paper, we propose a traffic model for the characterization of VBR MPEG-coded video streams. This model provides the means to generate synthetic MPEG streams that can be used in performance studies of ATM networks. The model is appropriately fitted to three long empirical video sequences taken from different movies. We use multiple components to model bit rate variations in an MPEG stream. These components have different time scales. Long-term variations in the bit rate are captured at the scene level. Within a scene, the sizes of I frames tend to slightly fluctuate around some average. Hence, we measure the activity of the scene by the average size of I frames in that scene. This average varies from one scene to another, and its randomness is reasonably approximated by a lognormal distribution. For a given scene, the fluctuations of the sizes of I frames about- their mean are modeled as an AR(2) time series. Finally, we show that the sizes of P and B frames can be appropriately fitted by lognormal distributions, with corresponding parameters. Using the compression pattern, the complete frame size sequence is formed by intermixing three subsequences, each of which describes the frame size sequence for a particular frame type. The validity of the model is demonstrated by the similarity between a synthetic stream and an actual trace, in terms of the correlation structure, the marginal distribution, the sample paths, and more importantly, the queueing performance. (Also cross-referenced as UMIACS-TR-95-120)
A Study of Query Execution Strategies for Client-Server Database Systems
(1998-10-15) Kossmann, Donald; Franklin, Michael J.
Query processing in a client-server database system raises the question of where to execute queries to minimize the communication costs and response time of a query, and to load-balance the system. This paper evaluates the two common query execution strategies, data shipping and query shipping, and a policy referred to as hybrid shipping. Data shipping determines that queries be executed at clients; query shipping determines that queries be executed at servers; and hybrid shipping provides the flexibility to execute queries at clients and servers. The experiments with a client-server model confirm that the query execution policy is critical for the performance of a system. Neither data nor query shipping are optimal in all situations, and the performance penalities can be substantial. Hybrid shipping at least matches the best performance of data and query shipping and shows better performance than both in many cases. The performance of hybrid shipping plans, however, is shown to be sensitive to changes in the state of the system (e.g., the load of machines and the contents of caches). Initial experiments indicate that an extended version of a 2-step optimization may be an effective strategy for adjusting plans according to the state of the system at runtime. (Also cross-referenced as UMIACS-TR-95-85)
Digital Dynamic Telepathology -- the Virtual Microscope
(1998-10-15) Afework, Asmara; Beynon, Michael D.; Bustamante, Fabian; Demarzo, Angelo, M.D.; Ferreira, Renato; Miller, Robert, M.D.; Silberman, Mark, M.D.; Saltz, Joel, M.D., Ph.D.; Sussman, Alan, Ph.D.; Tsang, Hubert
The Virtual Microscope is being designed as an integrated computer hardware and software system that generates a highly realistic digital simulation of analog, mechanical light microscopy. We present our work over the past year in meeting the challenges in building such a system. The enhancements we made are discussed, as well as the planned future improvements. Performance results are provided that show that the system scales well, so that many clients can be adequately serviced by an appropriately configured data server. (Also cross-referenced as UMIACS-TR-98-23)
Understanding the Sources of Variation in Software Inspections
(1998-10-15) Porter, Adam A.; Siy, Harvey; Mockus, Audris; Votta, Lawrence G.
In a previous experiment, we determined how various changes in three structural elements of the software inspection process (team size, and number and sequencing of session), altered effectiveness and interval. our results showed that such changes did not significantly influence the defect detection reate, but that certain combinations of changes dramatically increased the inspection interval. We also observed a large amount of unexplained variance in the data, indicating that other factors much be affecting inspection performance. The nature and extent of these other factos now have to be determined to ensure that they had not biased our earlier results. Also, identifying these other factors might suggest additional ways to improve the efficiency of inspection. Acting on the hypothesis that the "inputs" into the inspection process (reviewers, authors, and code units) were significant sources of variation, we modeled their effects on inspection performance. We found that they were responsible for much more variation in defect detection than was process structure. This leads us to conclude that better defect detection techniques, not better process structures, at the key to improving inspection effectiveness. The combined effects of process inputs and process structure on the inspection interval accounted for only a small percentage of the variance in inspection interval. Therefore, there still remain other factors which need to be identified. (Also cross-referenced as UMIACS-TR-97-22)
Thinking takes time: a modal active-logic for reasoning in time
(1998-10-15) Nirkhe, Madhura; Kraus, Sarit; Perlis, Don
Most common sense reasoning formalisms do not account for the passage of time a s the reasoning occurs, and hence are inadequate from the point of view of modeling an agent's {\em ongoing} process of reasoning. We present a modal active-logic that treats time as a valuable resource that is consumed in each step of the agent's reasoning. We provide a sound and complete characterization for this logic and examine how it addresses the problem of logical omniscience. (Also cross-referenced as UMIACS-TR-94-39)
SIMPLE: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMPs)
(1998-10-15) Bader, David A.; JaJa, Joseph
We describe a methodology for developing high performance programs running on clusters of SMP nodes. Our methodology is based on a small kernel (SIMPLE) of collective communication primitives that make efficient use of the hybrid shared and message passing environment. We illustrate the power of our methodology by presenting experimental results for sorting integers, two-dimensional fast Fourier transforms (FFT), and constraint-satisfied searching. Our testbed is a cluster of DEC AlphaServer 2100 4/275 nodes interconnected by an ATM switch. (Also cross-referenced as UMIACS-TR-97-48.)
Scheduling Issues in Real-Time Systems
(1998-10-15) Chen, Chia-Mei
The most important objective of real-time systems is to fulfill time-critical missions in satisfying their application requirements and timing constraints. Software utilities can analyze real-time tasks and extract their characteristics and requirements for assisting the systems to guarantee schedulability. Real- time scheduling is the core of the real-time system design. It should allow real-time systems to exhibit predictable timing correctness regardless of possible uncertainty in run-time environments. In this dissertation, we study the problem of scheduling real-time tasks with resource and fault-tolerance requirements. For tasks with resource requirements, two types of platforms are examined: multiprocessor hard real-time systems and real-time database systems; for task with fault-tolerance requirements, we focus on hard real-time systems. We investigate preemptive priority-based scheduling for tasks with resource requirements in context of hard real-time systems. Rate-monotonic and earliest deadline first priority assignment strategies can meet deadlines if the schedulability conditions are satisfied. We propose resource control protocols, for these scheduling strategies, based on the concepts of priority inheritance and priority ceiling and describe schedulability conditions for meeting deadlines. Real-time database systems have different objectives for transaction scheduling. Minimizing miss ratio usually is the major concern. We study the significance of the knowledge of execution time in system performance and propose a class of optimistic concurrency control protocols using the knowledge of execution time. Our simulation results indicate that the knowledge of execution time substantially improve system performance. Fault-tolerance is an ability to maintain system in a safe and stable state such that the real-time application functions correctly and its timing constraints are satisfied even in the presence of faults. We develop a scheduling algorithm which attempts to build as many fault-tolerant tasks as possible into a schedule. We approximate system reliability by Markov chain models and illustrate the applicability of the proposed reliability models. We compare the proposed fault-tolerance scheduling approach with the basic fault-tolerance scheduling schemes and the simulation results show that our method provides better reliability than the basic scheduling schemes. (Also cross-referenced as UMIACS-TR-95-73)
Browsing Hierarchical Data with Multi-Level Dynamic Queries and Pruning
(1998-10-15) Kumar, Harsha; Plaisant, Catherine; Shneiderman, Ben
Users often must browse hierarchies with thousands of nodes in search of those that best match their information needs. The PDQ Tree-browser (Pruning with Dynamic Queries) visualization tool was specified, designed and developed for this purpose. This tool presents trees in two tightly-coupled views, one a detailed view and the other an overview. Users can use dynamic queries, a method for rapidly filtering data, to filter nodes at each level of the tree. The dynamic query panels are user-customizable. Subtrees of unselected nodes are pruned out, leading to compact views of relevant nodes. Usability testing of the PDQ Tree-browser, done with 8 subjects, helped assess strengths and identify possible improvements. The PDQ Tree-browser was used in Network Management (600 nodes) and UniversityFinder (1100 nodes) applications. A controlled experiment, with 24 subjects, showed that pruning significantly improved performance speed and subjective user satisfaction. Future research directions are suggested. (Also cross-referenced as CAR-TR-772) (Also cross-referenced as ISR-TR-95-53)
Split menus: Effectively using selection frequency to organize menus
(1998-10-15) Sears, Andrew; Shneiderman, Ben
When some items in a menu are selected more frequently than others, as is often the case, designers or individual users may be able to speed performance and improve satisfaction by placing several high-frequency items at the top of the menu. Design guidelines for split menus were developed and applied. Split menus were implemented and tested in two field studies and a controlled experiment. In the field study conditions performance times were reduced from 17 or 58% depending on the site and menus. In the controlled experiment split menus were significantly faster than alphabetic menus and yielded significantly higher subjective preferences. A possible resolution to the continuing debate among cognitive theorists about predicting menu selection times is offered. We conjecture and offer evidence that the logarithmic model applies to familiar (high-frequency) items and the linear model applies to unfamiliar (low-frequency) items. (Also cross-referenced as CAR-TR-649) ACM Transactions on Computer-Human Interaction, vol. 1, #1 (March 1994) 27-51 %I Human Computer Interaction Laboratory
On the Sensitivity of Nearly Uncoupled Markov Chains
(1998-10-15) Stewart, G. W.
Nearly uncoupled Markov chains (aka nearly completely decomposable Markov chains) arise in a variety of applications, where they model loosely coupled systems. In such systems it may be difficult to determine the transitions probabilities with high accuracy. This paper investigates the sensitivity of the limiting distribution of the chain to perturbations in the transition probabilities. The conclusion is that nearly uncoupled Markov chains are quite sensitive to such perturbations but the perturbation of the limiting distribution is not arbitrary. (Also cross-referenced as UMIACS-TR-90-18) Appeared in Numerical Solutions of Markov Chains, W. J. Stewart ed., Dekker, New York, 1990.
Understanding and Predicting the Process of Software Maintenance Releases
(1998-10-15) Basili, Victor R.; Briand, Lionel; Condon, Steve; Kim, Yong-Mi; Melo, Walcelio L.; Valett, Jon
One of the major concerns of any maintenance organization is how to estimate the cost of subsequent releases of software systems. Planning the next release, maximizing the increase in functionality and improving the quality are vital to successful maintenance management. The objective of this paper is to present the results of a case study in which an incremental and inductive approach was used to build a model for predicting software maintenance releases in a large-scale software maintenance organization. This study was conducted in the Flight Dynamics Division (FDD) of the NASA Goddard Space Flight Center (GSFC). This organization is representative of many other software maintenance organizations. Over one hundred software systems totalling about 4.5 million lines of code are maintained by this organization. Many of these systems have been maintained for many years and regularly produce new releases. The maintenance costs in this organization have increased considerably over the last few years. This paper shows the predictive model developed for the FDD's software maintenance release process. Lessons learned during the establishment of a measurement-based software maintenance improvement program in this organization are also described and future work is outlined. (Also cross-referenced as UMIACS-TR-95-79)