Technical Reports from UMIACS

Permanent URI for this collectionhttp://hdl.handle.net/1903/7

Browse

Now showing 1 - 20 of 950

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)
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)
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)
Calibrating, Counting, Grounding, Grouping
(1998-10-15) Elgot-Drapkin, Jennifer; Gordon, Diana; Kraus, Sarit; Miller, Michael; Nirkhe, Madhura; Perlis, Don
Even an ``elementary'' intelligence for control of the physical world will require very many kinds of knowledge and ability. Among these are ones related to perception, action, and reasoning about ``near space'': that region comprising one's body and the portion of space within reach of one's effectors; chief among these are individuation and categorization of objects. These in turn are made useful in part by the additional capacities to estimate category size, change one's beliefs about categories, and form new categories or revise old categories. In this position paper we point out some issues in knowledge representation that can arise with respect to the above capacities, and suggest that the framework of ``active logics'' (see below) may be marshaled toward solutions. We will conduct our discussion in terms of learning to understand in a semantically explicit way one's own sensori-motor system and its interactions with near-space objects. (Also cross-referenced as UMIACS-TR-94-63)
An On-line Variable Length Binary Encoding
(1998-10-15) Acharya, Tinku; JaJa, Joseph
We present a methodology of an on-line variable-length binary encoding of a set of integers. The basic principle of this methodology is to maintain the prefix property amongst the codes assigned on-line to a set of integers growing dynamically. The prefix property enables unique decoding of a string of elements from this set. To show the utility of this on-line variable length binary encoding, we apply this methodology to encode the LZW codes. Application of this encoding scheme significantly improves the compression achieved by the standard LZW scheme. This encoding can be applied in other compression schemes to encode the pointers using variable-length binary codes. (Also cross-referenced as UMIACS-TR-95-39)
Numerical Methods for M/G/1 Type Queues
(1998-10-15) Stewart, G. W.
Queues of M/G/1 type give rise to infinite embedded Markov chains whose transition matrices are upper block Hessenberg. The traditional algorithms for solving these queues have involved the computation of an intermediate matrix G. Recently a recursive descent method for solving block Hessenberg systems has been proposed. In this paper we explore the interrelations of the two methods. (Also cross-referenced as UMIACS-TR-95-37)
Stabbing Orthogonal Objects in 3-Space
(1998-10-15) Mount, David M.; Pu, Fan-Tao
We consider a problem that arises in the design of data structures for answering {\em visibility range queries}, that is, given a $3$-dimensional scene defined by a set of polygonal patches, we wish to preprocess the scene to answer queries involving the set of patches of the scene that are visible from a given range of points over a given range of viewing directions. These data structures recursively subdivide space into cells until some criterion is satisfied. One of the important problems that arise in the construction of such data structures is that of determining whether a cell represents a nonempty region of space, and more generally computing the size of a cell. In this paper we introduce a measure of the {\em size} of the subset of lines in 3-space that stab a given set of $n$ polygonal patches, based on the maximum angle and distance between any two lines in the set. Although the best known algorithm for computing this size measure runs in $O(n^2)$ time, we show that if the polygonal patches are orthogonal rectangles, then this measure can be approximated to within a constant factor in $O(n)$ time. (Also cross-referenced as UMIACS-TR-96-71)
A Review of Software Inspections
(1998-10-15) Porter, Adam A.; Siy, Harvey; Votta, Lawrence G.
For two decades, software inspections have proven effective for detecting defects in software. We have reviewed the different ways software inspections are done, created a taxonomy of inspection methods, and examined claims about the cost-effectiveness of different methods. We detect a disturbing pattern in the evaluation of inspection methods. Although there is universal agreement on the effectiveness of software inspection, their economics are uncertain. Our examination of several empirical studies leads us to conclude that the benefits of inspections are often overstated and the costs (especially for large software developments) are understated. Furthermore, some of the most influential studies establishing these costs and benefits are 20 years old now, which leads us to question their relevance to today's software development processes. Extensive work is needed to determine exactly how, why, and when software inspections work, and whether some defect detection techniques might be more cost-effective than others. In this article we ask some questions about measuring effectiveness of software inspections and determining how much they really cost when their effect on the rest of the development process is considered. Finding answers to these questions will enable us to improve the efficiency of software development. (Also cross-referenced as UMIACS-TR-95-104)
Scrambling Query Plans to Cope With Unexpected Delays
(1998-10-15) Amsaleg, Laurent; Franklin, Michael J.; Tomasic, A.; Urhan., T.
Accessing numerous widely-distributed data sources poses significant new challenges for query optimization and execution. Congestion or failure in the network introduce highly-variable response times for wide-area data access. This paper is an initial exploration of solutions to this variability. We investigate a class of dynamic, run-time query plan modification techniques that we call query plan scrambling. We present an algorithm which modifies execution plans on-the-fly in response to unexpected delays in data access. The algorithm both reschedules operators and introduces new operators into the plan. We present simulation results that show how our technique effectively hides delays in receiving the initial requested tuples from remote data sources. (Also cross-referenced as UMIACS-TR-96-35)
Implementation of the MPL Compiler
(1998-10-15) Rizzuto, Jan M.; Silva, James da
The Maruti Real-Time Operating System was developed for applications that must meet hard real-time constraints. In order to schedule real-time applications, the timing and resource requirements for the application must be determined. The development environment provided for Maruti applications consists of several stages that use various tools to assist the programmer in creating an application. By analyzing the source code provided by the programmer, these tools can extract and analyze the needed timing and resource requirements. The initial stage in development is the compilation of the source code for an application written in the Maruti Programming Language (MPL). MPL is based on the C programming language. The MPL Compiler was developed to provide support for requirement specification. This report introduces MPL and describes the implementation of the MPL Compiler. (Also cross-referenced as UMIACS-TR-95-17)
Development of Cross-Linguistic Syntactic and Semantic Parameters for Parsing and Generation
(1998-10-15) Dorr, Bonnie J.
This document reports on research conducted at the University of Maryland for the Korean/English Machine Translation (MT) project. The translation approach adopted here is interlingual i.e., a single underlying representation called Lexical Conceptual Structure (LCS) is used for both Korean and English. The primary focus of this investigation concerns the notion of `parameterization' i.e., a mechanism that accounts for both syntactic and lexical-semantic distinctions between Korean and English. We present our assumptions about the syntactic structure of Korean-type languages vs. English-type languages and describe our investigation of syntactic parameterization for distinguishing between these two types of languages. We also present the details of the LCS structure and describe how this representation is parameterized so that it accommodates both languages. We address critical issues concerning interlingual machine translation such as locative postpositions and the dividing line between the interlingua and the knowledge representation. Difficulties in translation and transliteration of Korean are discussed and complex morphological properties of Korean are presented. Finally, we describe recent work on lexical acquisition and conclude with a discussion about two hypotheses concerning semantic classification that are currently being tested. (Also cross-referenced as UMIACS-TR-94-26)