A new deterministic parallel sorting algorithm with an experimental evaluation - Helman,David R.; JaJa, Joseph F.; Bader,David A. (Journal of Experimental Algorithmics (JEA), 1998)
We introduce a new deterministic parallel sorting algorithm for distributed memory machines based on the regular sampling approach. The algorithm uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. Moreover, unlike previous variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. This algorithm was implemented in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2-WN, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, the performance compares closely to that of our random sample sort algorithm, which seems to outperform all similar algorithms known to the authors on these platforms. Together, their performance is nearly invariant over the set of input distributions, unlike previous efficient algorithms. However, unlike our randomized sorting algorithm, the performance and memory requirements of our regular sorting algorithm can be deterministically guaranteed.
Keywords: generalized sorting; integer sorting; Parallel algorithms; parallel performance; sorting by regular sampling

Overcoming Instability In Computing The Fundamental Matrix For A Markov Chain - Heyman,Daniel P.; O'Leary, Dianne P. (SIAM Journal on Matrix Analysis and Applications, 1998)
We present an algorithm for solving linear systems involving the probability or rate matrix for a Markov chain. It is based on a UL factorization but works only with a submatrix of the factor U. We demonstrate its utility on Erlang-B models as well as more complicated models of a telephone multiplexing system.
Keywords: decision process; fundamental matrix; Markov chains

A Parallel Sorting Algorithm With an Experimental Study - Helman,David R.; Bader,David A.; JaJa, Joseph F. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
Previous schemes for sorting on general-purpose parallel machineshave had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results are consistent with the theoretical analysis and illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare favorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark. (Also cross-referenced as UMIACS-TR-95-102)
Keywords: Technical Report

Performance measurement using low perturbation and high precision hardware assists - Mink, A.; Salamon, W.; Hollingsworth, Jeffrey K; Arunachalam, R. (, The 19th IEEE Real-Time Systems Symposium, 1998. Proceedings, 1998)
We present the design and implementation of MultiKron PCI, a hardware performance monitor that can be plugged into any computer with a free PCI bus slot. The monitor provides a series of high-resolution timers, and the ability to monitor the utilization of the PCI bus. We also demonstrate how the monitor can be integrated with online performance monitoring tools such as the Paradyn parallel performance measurement tools to improve the overhead of key timer operations by a factor of 25. In addition, we present a series of case studies using the MultiKron hardware performance monitor to measure and tune high-performance parallel completing applications. By using the monitor, we were able to find and correct a performance bug in a popular implementation of the MPI message passing library that caused some communication primitives to run at one half their potential speed
Keywords: Clocks; Computerized monitoring; Counting circuits; Debugging; Hardware; hardware performance monitor; high precision hardware assists; low perturbation; measurement; MPI message passing library; MultiKron hardware performance monitor; MultiKron PCI; NIST; online performance monitoring tools; Paradyn parallel performance measurement tools; PCI bus slot; performance bug; performance evaluation; performance measurement; program debugging; program testing; real-time systems; Runtime; Timing

PLAN: a packet language for active networks - Hicks, Michael W.; Kakkar,Pankaj; Moore,Jonathan T.; Gunter,Carl A.; Nettles,Scott (SIGPLAN Not., 1998)
PLAN (Packet Language for Active Networks) is a new language for programs that form the packets of a programmable network. These programs replace the packet headers (which can be viewed as very rudimentary programs) used in current networks. As such, PLAN programs are lightweight and of restricted functionality. These limitations are mitigated by allowing PLAN code to call node-resident service routines written in other, more powerful languages. This two-level architecture, in which PLAN serves as a scripting or 'glue' language for more general services, is the primary contribution of this paper. We have successfully applied the PLAN programming environment to implement an IP-free internetwork.PLAN is based on the simply typed lambda calculus and provides a restricted set of primitives and datatypes. PLAN defines a special construct called a chunk used to describe the remote execution of PLAN programs on other nodes. Primitive operations on chunks are used to provide basic data transport in the network and to support layering of protocols. Remote execution can make debugging difficult, so PLAN provides strong static guarantees to the programmer, such as type safety. A more novel property aimed at protecting network availability is a guarantee that PLAN programs use a bounded amount of network resources.

PLAN Security System - Hicks, Michael W. (Technical Reports (CIS), 1998)
Active Networks offer the ability to program the network on a per-router, per-user, or even per-packet basis. Unfortunately, this added programmability compromises the security of the system by allowing a wider range of potential attacks. Any feasible Active Network architecture therefore requires strong security guarantees. Of course, we should like these guarantees to come at the lowest possible price to the flexibility, performance, and usability of the system.The PLAN system is a distributed programming framework we have used to build an Active Network, PLANet [4]. In the PLAN system, code implementing distributed programs is broken into two parts: the PLAN level, and the Service Level. All programs in the PLAN level reside in the messages, or packets, that are sent between the nodes of the system. These programs are written in the Programming Language for Active Networks [6] (or simply, PLAN). PLAN programs serve to "glue" together Service level programs; PLAN may be thought of as a network scripting language. In contrast, Service level programs (or simply, services), reside at each node and are invoked by executing PLAN programs. Services are written in general-purpose languages (in particular, the language that the PLAN interpreter is written in) and may be dynamically loaded. The current Internet (IP and its supporting protocols) allows any user with a network connection to have some basic services. In addition to basic packet delivery provided by IP, basic information services like DNS, finger, and whois, and protocols like HTTP, FTP, TCP, SMTP, and so forth are provided. Similarly, a goal of PLANet is to allow any user of the network to have access to basic services; these services should naturally include some "activeness." This goal implies that some functionality, like packet delivery in the current Internet, should not require authentication; in PLANet, we allow "pure" PLAN programs to run unauthenticated. A PLAN program is considered "pure" if it only makes calls to services considered safe; for example, determining the name of the current host is a safe operation, while updating the host’s router table is not. Successfully calling unsafe services would require proper authorization. This security policy is stated more formally in the following subsection.

PLAN Service Programmer's Guide - Hicks, Michael W. (University of Pennsylvania, 1998)

The PLAN system for building Active Networks - Hicks, Michael W.; Kakkar,P.; Moore,J. T; Gunter,C. A; Alexander,D. S; Nettles,S. (University of Pennsylvania (February 27, 1998), 1998)

Prediction and Adaptation in Active Harmony - Hollingsworth, Jeffrey K; Keleher, Peter J. (High-Performance Distributed Computing, International Symposium on, 1998)
We describe the design and early functionality of the Active Harmony global resource management system. Harmony is an infrastructure designed to efficiently execute parallel applications in large-scale, dynamic environments.Harmony differs from other projects with similar goals in that the system automatically adapts ongoing computations to changing conditions through online reconfiguration. This reconfiguration can consist of system-directed migration of work at several different levels, or automatic application adaptation through the use of tuning options exported by Harmony-aware applications.We describe early experience with work migration at the level of procedures, processes and lightweight threads.
Keywords: adaptation; resource management.; scheduling

A Randomized Parallel Sorting Algorithm with an Experimental Study - Helman,David R.; Bader,David A.; JaJa, Joseph F. (Journal of Parallel and Distributed Computing, 1998)
Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. Moreover, unlike previous variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare favorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark.
Keywords: generalized sorting; integer sorting, sample sort, parallel performance; Parallel algorithms

A study of large object spaces - Hicks, Michael W.; Hornof,Luke; Moore,Jonathan T.; Nettles,Scott M. (Proceedings of the 1st international symposium on Memory management, 1998)
This paper examines the design space for copying garbage collectors (GCs) in which "large objects" are managed in a separate, non-copy-collected space. We focus on two main issues:1. how to set the policy for classifying objects as "large"2. how to manage the large object spaceWe explore these issues experimentally using the Oscar GC testbed. In particular, we vary the threshold size of large objects and also whether the objects may contain pointers. Furthermore, we compare the performance of treadmill collection to that of mark-and-sweep collection for managing the large object space.We find that for some heaps there is a minimum cutoff size below which adding objects to the large object space does not result in a performance improvement, while for others no such cutoff exists. In general, including pointer-containing objects in the large object space seems beneficial. Finally, the exact method used to collect the large object space does not significantly influence overall performance.

The SwitchWare active network architecture - Alexander,D. S; Arbaugh, William A.; Hicks, Michael W.; Kakkar,P.; Keromytis,A. D; Moore,J. T; Gunter,C. A; Nettles,S. M; Smith,J. M (IEEE Network, 1998)
Active networks must balance the flexibility of a programmable network infrastructure against the safety and security requirements inherent in sharing that infrastructure. Furthermore, this balance must be achieved while maintaining the usability of the network. The SwitchWare active network architecture is a novel approach to achieving this balance using three layers: active packets, which contain mobile programs that replace traditional packets; active extensions, which provide services on the network elements and can be dynamically loaded; and a secure active router infrastructure, which forms a high-integrity base on which the security of the other layers depends. In addition to integrity checking and cryptography-based authentication, security in our architecture depends heavily on verification techniques from programming languages, such as strong type checking
Keywords: active extensions; active packets; Authentication; Computer languages; Computer networks; cryptography; cryptography-based authentication; high-integrity base; integrity checking; IP networks; LAN interconnection; mobile programs; network operating systems; packet switching; programmable network infrastructure; programming languages; Protocols; Safety; safety requirements; scalability; secure active router infrastructure; Security; security requirements; services; strong type checking; Switches; SwitchWare active network architecture; telecommunication network routing; Tin; usability; verification techniques

The switchware active network implementation - Alexander,D. S; Hicks, Michael W.; Kakkar,P.; Keromytis,A. D; Shaw,M.; Moore,J. T; Gunter,C. A; Jim,T.; Nettles,S. M; Smith,J. M (The ML Workshop, International Conference on Functional Programming (ICFP), 1998)

A Thematic Hierarchy for Efficient Generation from Lexical-Conceptual Structure - Dorr, Bonnie J; Habash,Nizar; Traum,David (Machine Translation and the Information SoupMachine Translation and the Information Soup, 1998)
This paper describes an implemented algorithm for syntactic realization of a target-language sentence from an interlingual representation called Lexical Conceptual Structure (LCS). We provide a mapping between LCS thematic roles and Abstract Meaning Representation (AMR) relations; these relations serve as input to an off-the-shelf generator (Nitrogen). There are two contributions of this work: (1) the development of a thematic hierarchy that provides ordering information for realization of arguments in their surface positions; (2) the provision of a diagnostic tool for detecting inconsistencies in an existing online LCS-based lexicon that allows us to enhance principles for thematic-role assignment.

Trends in the Early Careers of Life Scientists - Tilghman,S; Astin,HS; Brinkley,W; Chilton,MD; Cummings, Michael P.; Ehrenberg,RG; Fox,MF; Glenn,K; Green,PJ; Hans,S; Kelman,A; LaPidus,J; et al. (National Academy Press, 1998)

Trends in the early careers of life scientists - Preface and executive summary - Tilghman,S; Astin,HS; Brinkley,W; Chilton,MD; Cummings, Michael P.; Ehrenberg,RG; Fox,MF; Glenn,K; Green,PJ; Hans,S; Kelman,A; LaPidus,J; et al. (Mol Biol Cell, 1998)

Types and intermediate representations - Hicks, Michael W. (Technical Reports (CIS), 1998)

Visualizing medical records with LifeLines - Plaisant, Catherine; Heller,Daniel; Li,Jia; Shneiderman, Ben; Mushlin,Rich; Karat,John (CHI 98 conference summary on Human factors in computing systems, 1998)
Keywords: healthcare; History; medical record; overview; timeline; Visualization

Accuracy and Stability of Numerical Algorithms - Higham,N. J; Stewart, G.W. (SIAM Review, 1997)

ADistributed Management System for Testing Document Image Database Analysis Algorithms - David Doermann; Sauvola,J.; Haapakoski,S.; Kauniskangas,H.; Seppanen,T.; Pietikainen,M. (ICDAR, 1997)

Designing interactive multimedia (panel) - Scarlatos,Lori L.; Darken,Rudolph P.; Harada,Komei; Heeter,Carrie; Muller,Richard; Shneiderman, Ben (Proceedings of the fifth ACM international conference on Multimedia, 1997)

Hardness of flip-cut problems from optical mapping - DANČÍK,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Journal of Computational Biology, 1997)

Hardness of flip-cut problems from optical mapping [DNA molecules application] - Dancik,V.; Hannenhalli, Sridhar; Muthukrishnan,S. (Compression and Complexity of Sequences 1997. Proceedings, 1997)
Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single “consensus” restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP
Keywords: binary shift cut; Biochemistry; Bioinformatics; biological techniques; Biology; biomedical optical imaging; combinatorial mathematics; combinatorial problem; computational complexity; computational problems; DNA; DNA molecule; exclusive binary flip cut; flip-cut problem hardness; Genetic engineering; Genomics; MATHEMATICS; molecular biology; molecular biophysics; molecule orientation; multiple partial restriction maps; NP-complete problem; optical mapping; polynomial time solutions; Polynomials; sequences

KidPad: a design collaboration between children, technologists, and educators - Druin, Allison; Stewart,J.; Proft,D.; Bederson, Benjamin B.; Hollan,J. (Proceedings of the SIGCHI conference on Human factors in computing systems, 1997)

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model - Agarwala,Richa; Batzoglou,Serafim; DančíK,Vlado; Decatur,Scott E.; Hannenhalli, Sridhar; Farach,Martin; Muthukrishnan,S.; Skiena,Steven (Journal of Computational Biology, 1997)
We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill (1985), which models protein as a chain of amino acid residues that are either hydrophobic or polar, and hydrophobic interactions are the dominant initial driving force for the protein folding. Hart and Istrail (1996a) gave approximation algorithms for folding proteins on the cubic lattice under the HP model. In this paper, we examine the choice of a lattice by considering its algorithmic and geometric implications and argue that the triangular lattice is a more reasonable choice. We present a set of folding rules for a triangular lattice and analyze the approximation ratio they achieve. In addition, we introduce a generalization of the HP model to account for residues having different levels of hydrophobicity. After describing the biological foundation for this generalization, we show that in the new model we are able to achieve similar constant factor approximation guarantees on the triangular lattice as were achieved in the standard HP model. While the structures derived from our folding rules are probably still far from biological reality, we hope that having a set of folding rules with different properties will yield more interesting folds when combined.

MDL: a language and compiler for dynamic program instrumentation - Hollingsworth, Jeffrey K; Niam, O.; Miller, B. P; Zhichen Xu; Goncalves,M. J.R; Ling Zheng (, 1997 International Conference on Parallel Architectures and Compilation Techniques., 1997. Proceedings, 1997)
We use a form of dynamic code generation, called dynamic instrumentation, to collect data about the execution of an application program. Dynamic instrumentation allows us to instrument running programs to collect performance and other types of information. The instrumentation code is generated incrementally and can be inserted and removed at any time. Our instrumentation currently runs on the SPARC, PA-RISC, Power 2, Alpha, and x86 architectures. Specification of what data to collect are written in a specialized language called the Metric Description Language, that is part of the Paradyn Parallel Performance Tools. This language allows platform independent descriptions of how to collect performance data. It also provides a concise way to specify, how to constrain performance data to particular resources such as modules, procedures, nodes, files, or message channels (or combinations of these resources). We also describe the details of how we weave instrumentation into a running program
Keywords: Alpha architecture; application program; application program interfaces; Application software; compiler generators; Computer science; dynamic code generation; Dynamic compiler; dynamic program instrumentation; Educational institutions; files; instrumentation code; Instruments; MDL; measurement; message channels; Message passing; Metric Description Language; modules; nodes; Operating systems; optimising compilers; PA-RISC; Paradyn Parallel Performance Tools; Parallel architectures; parallel programming; performance data; platform independent descriptions; Power 2 architecture; Power generation; procedures; program debugging; Program processors; running programs; Runtime; software metrics; SPARC; Specification languages; x86 architecture

The measured cost of copying garbage collection mechanisms - Hicks, Michael W.; Moore,Jonathan T.; Nettles,Scott M. (SIGPLAN Not., 1997)
We examine the costs and benefits of a variety of copying garbage collection (GC) mechanisms across multiple architectures and programming languages. Our study covers both low-level object representation and copying issues as well as the mechanisms needed to support more advanced techniques such as generational collection, large object spaces, and type segregated areas.Our experiments are made possible by a novel performance analysis tool, Oscar. Oscar allows us to capture snapshots of programming language heaps that may then be used to replay garbage collections. The replay program is self-contained and written in C, which makes it easy to port to other architectures and to analyze with standard performance analysis tools. Furthermore, it is possible to study additional programming languages simply by instrumenting existing implementations to capture heap snapshots.In general, we found that careful implementation of GC mechanisms can have a significant benefit. For a simple collector, we measured improvements of as much as 95%. We then found that while the addition of advanced features can have a sizeable overhead (up to 15%), the net benefit is quite positive, resulting in additional gains of up to 42%. We also found that results varied depending upon the platform and language. Machine characteristics such as cache arrangements, instruction set (RISC/CISC), and register pool were important. For different languages, average object size seemed to be most important.The results of our experiments demonstrate the usefulness of a tool like Oscar for studying GC performance. Without much overhead, we can easily identify areas where programming language implementors could collaborate with GC implementors to improve GC performance.

Multiresolution surface modeling - Heckbert,P.; Rossignac,J.; Hoppe,H.; Schroeder,W.; Soucy,M.; Varshney, Amitabh (SIGGRAPH 1997 Course Notes, 1997)

Regularization algorithms based on total least squares - Hansen,Per Christian; O'Leary, Dianne P. (Recent advances in total least squares techniques and errors-in-variables modeling (Leuven, 1996)Recent advances in total least squares techniques and errors-in-variables modeling (Leuven, 1996), 1997)

Regularization by Truncated Total Least Squares - Fierro,R. D.; Golub, G. H; Hansen,P. C.; O'Leary, Dianne P. (SIAM Journal on Scientific Computing, 1997)
The total least squares (TLS) method is a successful method for noise reduction in linear least squares problems in a number of applications. The TLS method is suited to problems in which both the coefficient matrix and the right-hand side are not precisely known. This paper focuses on the use of TLS for solving problems with very ill-conditioned coefficient matrices whose singular values decay gradually (so-called discrete ill-posed problems), where some regularization is necessary to stabilize the computed solution. We filter the solution by truncating the small singular values of the TLS matrix. We express our results in terms of the singular value decomposition (SVD) of the coefficient matrix rather than the augmented matrix. This leads to insight into the filtering properties of the truncated TLS method as compared to regularized least squares solutions. In addition, we propose and test an iterative algorithm based on Lanczos bidiagonalization for computing truncated TLS solutions.
Keywords: bidiagonalization; discrete ill-posed problems; regularization; total least squares

Run-time and compiler support for programming in adaptive parallel environments - Edjlali,G.; Agrawal,G.; Sussman, Alan; Humphries,J.; Saltz, J. (Scientific Programming, 1997)

A Service Layer Routing Protocol for PLAN - Moore,J. T; Hicks, Michael W. (PLAN documentation, September, 1997)

Using content-derived names for configuration management - Hollingsworth, Jeffrey K; Miller, E. L (ACM SIGSOFT Software Engineering Notes, 1997)

The virtual microscope. - Ferreira,R.; Moon,B.; Humphries,J.; Sussman, Alan; Saltz, J.; Miller,R.; Demarzo,A. (Proceedings of the AMIA Annual Fall Symposium, 1997)

Visual surveillance of human activity - Davis, Larry S.; Fejes,S.; Harwood,D.; Yacoob,Yaser; Hariatoglu,I.; Black,M. (Computer Vision—ACCV'98, 1997)

A zooming web browser - Bederson, Benjamin B.; Hollan,J.D.; Stewart,J.; Rogers,D.; Druin, Allison; Vick,D.; Ring,L.; Grose,E.; Forsythe,C. (Human Factors in Web Development, 1997)

An adaptive cost system for parallel program instrumentation - Hollingsworth, Jeffrey K; Miller, B. (Euro-Par'96 Parallel Processing, 1996)

Computational studies of synaptic alterations in Alzheimer’s disease - Ruppin,E.; Horn,D.; Levy,N.; Reggia, James A. (Neural modeling of brain and cognitive disorders, 1996)

Computing 3-D head orientation from a monocular image sequence - Horprasert,T.; Yacoob,Yaser; Davis, Larry S. (Automatic Face and Gesture Recognition, 1996., Proceedings of the Second International Conference on, 1996)
An approach for estimating 3D head orientation in a monocular image sequence is proposed. The approach employs recently developed image-based parameterized tracking for face and face features to locate the area in which a sub-pixel parameterized shape estimation of the eye's boundary is performed. This involves tracking of five points (four at the eye corners and the fifth is the lip of the nose). The authors describe an approach that relies on the coarse structure of the face to compute orientation relative to the camera plane. Our approach employs projective invariance of the cross-ratios of the eye corners and anthropometric statistics to estimate the head yaw, roll and pitch. Analytical and experimental results are reported
Keywords: 3D head orientation computation; anthropometric statistics; camera plane; coarse structure; eye; eye boundary; eye corners; face features; face recognition; Feature extraction; head pitch; head roll; head yaw; Image sequences; image-based parameterized tracking; monocular image sequence; projective cross-ratio invariance; sub-pixel parameterized shape estimation; tracking

Controlled topology simplification - He,Taosong; Hong,Lichan; Varshney, Amitabh; Wang,S.W. (Visualization and Computer Graphics, IEEE Transactions on, 1996)
We present a simple, robust, and practical method for object simplification for applications where gradual elimination of high frequency details is desired. This is accomplished by converting an object into multi resolution volume rasters using a controlled filtering and sampling technique. A multiresolution triangle mesh hierarchy can then be generated by applying the Marching Cubes algorithm. We further propose an adaptive surface generation algorithm to reduce the number of triangles generated by the standard Marching Cubes. Our method simplifies the topology of objects in a controlled fashion. In addition, at each level of detail, multilayered meshes can be used for an efficient antialiased rendering
Keywords: (computer; algorithm; adaptive; algorithm; controlled; antialiased; Cubes; Cubes; antialiasing; computational; details; multi; filtering; controlled; Frequency; generation; geometry; rendering; graphics); topology; hierarchy; object; Marching; mesh; meshes; multiresolution; rasters; multilayered; rendering; high; resolution; simplification; efficient; simplification; sampling; surface; technique; standard; Topology; triangle; volume

Fast sorting by reversal - Berman,Piotr; Hannenhalli, Sridhar (Combinatorial Pattern MatchingCombinatorial Pattern Matching, 1996)
Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. Following a series of work recently, Hannenhalli and Pevzner developed the first polynomial algorithm for the problem of sorting signed permutations by reversals and proposed an O(n 4 ) implementation of the algorithm. In this paper we exploit a few combinatorial properties of the cycle graph of a permutation and propose an O(n 2 (n)) implementation of the algorithm where is the inverse Ackerman function. Besides making this algorithm practical, our technique improves implementations of the other rearrangement distance problems.

Inferring phylogenies from DNA sequence data: The effects of sampling - Otto,S. P; Cummings, Michael P.; Wakeley,J. (New Uses for New PhylogeniesNew Uses for New Phylogenies, 1996)

Local tools: an alternative to tool palettes - Bederson, Benjamin B.; Hollan,J.D.; Druin, Allison; Stewart,J.; Rogers,D.; Proft,D. (Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996)

Modeling, Evaluation, and Testing of Paradyn Instrumentation System - Waheed, A.; Rover, D. T; Hollingsworth, Jeffrey K (Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, 1996, 1996)
This paper presents a case study of modeling, evaluating, and testing the data collection services (called an instrumentation system) of the Paradyn parallel performance measurement tool using well-known performance evaluation and experiment design techniques. The overall objective of the study is to use modeling- and simulation-based evaluation to provide feedback to the tool developers to help them choose system configurations and task scheduling policies that can significantly reduce the data collection overheads. We develop and parameterize a resource occupancy model for the Paradyn instrumentation system (IS) for an IBM SP-2 platform. This model is parameterized with a measurement-based workload characterization and subsequently used to answer several "what if" questions regarding configuration options and two policies to schedule instrumentation system tasks: collect-and-forward (CF) and batch-and-forward (BF) policies. Simulation results indicate that the BF policy can significantly reduce the overheads. Based on this feedback, the BF policy was implemented in the Paradyn IS as an option to manage the data collection. Measurement-based testing results obtained from this enhanced version of the Paradyn IS are reported in this paper and indicate more than 60% reduction in the direct IS overheads when the BF policy is used.
Keywords: Distributed control; Feedback; High performance computing; Instruments; Monitoring; Real time systems; Software measurement; Software systems; Software testing; System testing

A neural model of positive schizophrenic symptoms - Ruppin,E.; Reggia, James A.; Horn,D. (Schizophrenia Bulletin, 1996)

An online computation of critical path profiling - Hollingsworth, Jeffrey K (Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, 1996)

Parallel algorithms for image enhancement and segmentation by region growing, with an experimental study - Bader, D.A.; JaJa, Joseph F.; Harwood,D.; Davis, Larry S. (The Journal of Supercomputing, 1996)
This paper presents efficient and portable implementations of a powerful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique that makes use of the SNF and a variant of the conventional connected components algorithm which we call delta-Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations). Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.

Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract) - Helman,David R.; Bader,David A.; JaJa, Joseph F. (Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, 1996)

Pathogenesis of schizophrenic delusions and hallucinations: a neural model - Ruppin,E.; Reggia, James A.; Horn,D. (Schizophrenia bulletin, 1996)

Polynomial-time algorithm for computing translocation distance between genomes - Hannenhalli, Sridhar (Discrete Applied Mathematics, 1996)
With the advent of large-scale DNA physical mapping and sequencing, studies of genome rearrangements are becoming increasingly important in evolutionary molecular biology. From a computational perspective, the study of evolution based on rearrangements leads to a rearrangement distance problem, i.e., computing the minimum number of rearrangement events required to transform one genome into another. Different types of rearrangement events give rise to a spectrum of interesting combinatorial problems. The complexity of most of these problems is unknown. Multichromosomal genomes frequently evolve by a rearrangement event called translocation which exchanges genetic material between different chromosomes. In this paper we study the translocation distance problem, modeling the evolution of genomes evolving by translocations. The translocation distance problem was recently studied for the first time by Kececioglu and Ravi, who gave a 2-approximation algorithm for computing translocation distance. In this paper we prove a duality theorem leading to a polynomial time algorithm for computing translocation distance for the case when the orientations of the genes are known. This leads to an algorithm generating a most parsimonious (shortest) scenario, transforming one genome into another by translocations.

Positional sequencing by hybridization - Hannenhalli, Sridhar; Feldman,William; Lewis,Herbert F.; Skiena,Steven S.; Pevzner,Pavel A. (Computer applications in the biosciences : CABIOS, 1996)
Sequencing by hybridization (SBH) is a promising alternative to the classical DNA sequencing approaches. However, the resolving power of SBH is rather low: with 64kb sequencing chips, unknown DNA fragments only as long as 200 bp can be reconstructed in a single SBH experiment. To improve the resolving power of SBH, positional SBH (PSBH) has recently been suggested; this allows (with additional experimental work) approximate positions of every l-tuple in a target DNA fragment to be measured. We study the positional Eulerian path problem motivated by PSBH. The input to the positional eulerian path problem is an Eulerian graph G( V, E) in which every edge has an associated range of integers and the problem is to find an Eulerian path el, …, e|E| in G such that the range of ei, contains i. We show that the positional Eulerian path problem is NP-complete even when the maximum out-degree (in-degree) of any vertex in the graph is 2. On a positive note we present polynomial algorithms to solve a special case of PSBH (bounded PSBH), where the range of the allowed positions for any edge is bounded by a constant (it corresponds to accurate experimental measurements of positions in PSBH). Moreover, if the positions of every l-tuple in an unknown DNA fragment of length n are measured with O(log n) error, then our algorithm runs in polynomial time. We also present an estimate of the resolving power of PSBH for a more realistic case when positions are measured with Θ(n) error.

Practical parallel algorithms for personalized communication and integer sorting - Bader,David A.; Helman,David R.; JaJa, Joseph F. (Journal of Experimental Algorithmics (JEA), 1996)
A fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which efficiently execute on general-purpose parallel machines. With the emergence of message passing standards such as MPI, it has become easier to design efficient and portable parallel algorithms by making use of these communication primitives. While existing primitives allow an assortment of collective communication routines, they do not handle an important communication event when most or all processors have non-uniformly sized personalized messages to exchange with each other. We focus in this paper on the h-relation personalized communication whose efficient implementation will allow high performance implementations of a large class of algorithms. While most previous h-relation algorithms use randomization, this paper presents a new deterministic approach for h-relation personalized communication with asymptotically optimal complexity for h>p2. As an application, we present an efficient algorithm for stable integer sorting. The algorithms presented in this paper have been coded in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, and the Intel Paragon. Our experimental results are consistent with the theoretical analysis and illustrate the scalability and efficiency of our algorithms across different platforms. In fact, they seem to outperform all similar algorithms known to the authors on these platforms.

Quantitative Measurement of the Performance of Raster-to-vector Conversion Algorithms - Hori,O.; David Doermann (Graphics Recognition: Methods and ApplicationsGraphics Recognition: Methods and Applications, 1996)

On stratified sampling for high coverage estimations - Powell,David; Michel Cukier; Arlat,Jean (Dependable Computing — EDCC-2, 1996)
This paper addresses the problem of estimating the coverage of a fault tolerance mechanism through statistical processing of observations collected in faultinjection experiments. In an earlier paper, several techniques for sampling the fault/activity input space of a fault tolerance mechanism were presented. Various estimators based on simple sampling in the whole space and stratified sampling in a partitioned space were studied; confidence limits were derived based on a normal approximation. In this paper, the validity of this approximation is analyzed, especially for high coverage systems. The theory of confidence regions is then introduced to estimate the coverage without approximation when, for practical reasons, stratification is used. Three statistics are considered for defining confidence regions. It is shown that one of these statistics — a vectorial statistic — is often more conservative than the other two. However, only the vectorial statistic is computationally tractable. The results obtained are compared with those based on approximation by means of three hypothetical example systems.
Keywords: Computer science

Table-Form Structure Analysis Based on Box-Driven Reasoning - Hori,Osamu; David Doermann (IEICE TRANSACTIONS on Information and Systems, 1996)
Table-form document structure analysis is an important problem in the document processing domain. This paper presents a new method called Box-Driven Reasoning (BDR) to robustly analyze the structure of table-form documents that include touching characters and broken lines. Real documents are copied repeatedly and overlaid with printed data, resulting in characters that touch cells and lines that are broken. Most previous methods employ a line-oriented approach, but touching characters and broken lines make the procedure fail at an early stage. BDR deals with regions directly in contrast with other previous methods and a reduced resolution image is introduced to supplement information deteriorated by noise. Experimental tests show that BDR reliably recognizes cells and strings in document images with touching characters and broken lines.

To cut… or not to cut (applications of comparative physical maps in molecular evolution) - Hannenhalli, Sridhar; Pevzner,Pavel (Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, 1996)

Tuning the performance of I/O-intensive parallel applications - Acharya, A.; Uysal, M.; Bennett, R.; Mendelson, A.; Beynon, M.; Hollingsworth, Jeffrey K; Saltz, J.; Sussman, Alan (Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, 1996)

Where is information visualization technology going? - Hascoët-Zizi,Mountaz; Ahlberg,Chris; Korfhage,Robert; Plaisant, Catherine; Chalmers,Matthew; Rao,Ramana (Proceedings of the 9th annual ACM symposium on User interface software and technology, 1996)

Crystallization and preliminary X-ray investigation of the recombinant Trypanosoma brucei rhodesiense calmodulin - El‐Sayed, Najib M.; Patton,C. L; Harkins,P. C; Fox,R. O; Anderson,K. (Proteins: Structure, Function, and Bioinformatics, 1995)

Dissertations - Humphrey,Susanne M.; Shneiderman, Ben (ACM SIGCHI Bulletin, 1995)
The following are citations selected by title and abstract as being related to Computer-Human Interaction, resulting from a computer search, using Dialog Information Services, of the Dissertation Abstracts Online database produced by University Microfilms International (UMI). Included are UMI order number, title, author, degree, year, institution; number of pages, Dissertation Abstracts International (DAI) subject category chosen by the author, and abstract. Unless otherwise specified, paper or microform copies of dissertations may be ordered from University Microfilms International, Dissertation Copies, Post Office Box 1764, Ann Arbor, MI 48106; telephone for U.S. (except Michigan, Hawaii, Alaska): 1-800-521-3042, for Canada: 1-800-343-5299. Price lists and other ordering and shipping information are in the introduction to the published DAI. An alternate source for copies is sometimes provided. Dissertation titles and abstracts contained here are published with permission of University Microfilms International, publishers of Dissertation Abstracts International (copyright by University Microfilms International), and may not be reproduced without their prior permission.

Efficient image processing algorithms on the scan line array processor - Helman,D.; JaJa, Joseph F. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1995)
Develops efficient algorithms for low and intermediate level image processing on the scan line array processor, a SIMD machine consisting of a linear array of cells that processes images in a scan line fashion. For low level processing, the authors present algorithms for block DFT, block DCT, convolution, template matching, shrinking, and expanding which run in real-time. By real-time, the authors mean that, if the required processing is based on neighborhoods of size m times;m, then the output lines are generated at a rate of O(m) operations per line and a latency of O(m) scan lines, which is the best that can be achieved on this model. The authors also develop an algorithm for median filtering which runs in almost real-time at a cost of O(m log m) time per scan line and a latency of [m/2] scan lines. For intermediate level processing, the authors present optimal algorithms for translation, histogram computation, scaling, and rotation. The authors also develop efficient algorithms for labelling the connected components and determining the convex hulls of multiple figures which run in O(n log n) and O(n log2n) time, respectively. The latter algorithms are significantly simpler and easier to implement than those already reported in the literature for linear arrays
Keywords: algorithms; algorithms; intermediate; algorithms; rotation; scaling; scan; array; computation; image; DCT; block; DFT; convex; filtering; optimal; hulls; convolution; expanding; histogram; level; line; machine; block; matching; translation; convolution; image; PROCESSING; processing; labelling; low; processing; median; processing; parallel; processor; shrinking; template; SIMD

Generating compact code from dataflow specifications of multirate signal processing algorithms - Bhattacharyya, Shuvra S.; Buck,J. T; Ha,S.; Lee,E. A (Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on, 1995)

Genome Sequence Comparison and Scenarios for Gene Rearrangements: A Test Case - Hannenhalli, Sridhar; Chappey,Colombe; Koonin,Eugene V.; Pevzner,Pavel A. (Genomics, 1995)
As large portions of related genomes are being sequenced, methods for comparing complete or nearly complete genomes, as opposed to comparing individual genes, are becoming progressively more important. A major, widespread phenomenon in genome evolution is the rearrangement of genes and gene blocks. There is, however, no consistent method for genome sequence comparison combined with the reconstruction of the evolutionary history of highly rearranged genomes. We developed a schema for genome sequence comparison that includes three successive steps: (i) comparison of all proteins encoded in different genomes and generation of genomic similarity plots; (ii) construction of an alphabet of conserved genes and gene blocks; and (iii) generation of most parsimonious genome rearrangement scenarios. The approach is illustrated by a comparison of the herpesvirus genomes that constitute the largest set of relatively long, complete genome sequences available to date. Herpesviruses have from 70 to about 200 genes; comparison of the amino acid sequences encoded in these genes results in an alphabet of about 30 conserved genes comprising 7 conserved blocks that are rearranged in the genomes of different herpesviruses. Algorithms to analyze rearrangements of multiple genomes were developed and applied to the derivation of most parsimonious scenarios of herpesvirus evolution under different evolutionary models. The developed approaches to genome comparison will be applicable to the comparative analysis of bacterial and eukaryotic genomes as soon as their sequences become available.

A large-scale neural model linking local neuronal dynamics to positron emission tomography (PET) regional cerebral blood ffow (rCBF) data - Tagamets,M. A; Horwitz,B.; Reggia, James A. (Soc Neurosci Abstr, 1995)

A modified cellular automata model of nucleotide interactions and non-enzymatic transcription of DNA - Hilke,J.; Reggia, James A.; Navarro-Gonzalez,R.; Lohn,J. (inbs, 1995)

A neural model of delusions and hallucinations in schizophrenia - Ruppin,E.; Reggia, James A.; Horn,D. (Advances in Neural Information Processing Systems, 1995)

An Optimal Ear Decomposition Algorithm with Applications on Fixed-Size Linear Arrays - Huang,Y. M.; JaJa, Joseph F. (PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, 1995)

The Paradyn parallel performance measurement tool - Miller, B. P; Callaghan, M. D; Cargille, J. M; Hollingsworth, Jeffrey K; Irvin, R. B; Karavanic, K. L; Kunchithapadam, K.; Newhall, T. (Computer, 1995)
Paradyn is a tool for measuring the performance of large-scale parallel programs. Our goal in designing a new performance tool was to provide detailed, flexible performance information without incurring the space (and time) overhead typically associated with trace-based tools. Paradyn achieves this goal by dynamically instrumenting the application and automatically controlling this instrumentation in search of performance problems. Dynamic instrumentation lets us defer insertion until the moment it is needed (and remove it when it is no longer needed); Paradyn's Performance Consultant decides when and where to insert instrumentation
Keywords: Aerodynamics; Automatic control; automatic instrumentation control; Debugging; dynamic instrumentation; flexible performance information; high level languages; insertion; Instruments; large-scale parallel program; Large-scale systems; measurement; Paradyn parallel performance measurement tool; Parallel machines; parallel programming; Performance Consultant; Programming profession; scalability; software performance evaluation; software tools

Polynomial-time algorithm for computing translocation distance between genomes - Hannenhalli, Sridhar (Combinatorial Pattern MatchingCombinatorial Pattern Matching, 1995)
With the advent of large-scale DNA physical mapping and sequencing, studies of genome rearrangements are becoming increasingly important in evolutionary molecular biology. From a computational perspective, study of evolution based on rearrangements leads to rearrangement distance problem, i.e., computing the minimum number of rearrangement events required to transform one genome into another. Different types of rearrangement events give rise to a spectrum of interesting combinatorial problems. The complexity of most of these problems is unknown. Multichromosomal genomes frequently evolve by a rearrangement event called translocation which exchanges genetic material between different chromosomes. In this paper we study the translocation distance problem, modeling evolution of genomes evolving by translocations. Translocation distance problem was recently studied for the first time by Kececioglu and Ravi, who gave a 2-approximation algorithm for computing translocation distance. In this paper we prove a duality theorem leading to a polynomial algorithm for computing translocation distance for the case when the orientation of the genes are known. This leads to an algorithm generating a most parsimonious (shortest) scenario, transforming one genome into another by translocations.

The representation of document structure: A generic object-process approach - Dori,D.; David Doermann; Shin,C.; Haralick,R.; Phillips,I.; Buchman,M.; Ross,D. (University of Maryland, College Park, 1995)

Robust table-form structure analysis based on box-driven reasoning - Hori,O.; David Doermann (Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, 1995)
Table form document structure analysis is an important problem in the document processing domain. The paper presents a method called Box Driven Reasoning (BDR) to robustly analyze the structure of table form documents which include touching characters and broken lines. Most previous methods employ a line oriented approach. Real documents are copied repeatedly and overlaid with printed data, resulting in characters which touch cells and lines which are broken. BDR deals with regions directly, in contrast with other previous methods. Experimental tests show that BDR reliably recognizes cells and strings in document images with touching characters and broken lines
Keywords: analysis; table; analysis; touching; BDR; box; characters; character; document; domain; robust; driven; form; image; images; document; lines; document; mechanisms; PROCESSING; processing; inference; reasoning; broken; recognition; data; structure; structures; document; table

Techniques for performance measurement of parallel programs - Hollingsworth, Jeffrey K; Lumpp, J. E; Miller, B. P (Parallel computers: theory and practice, 1995)

Towards a computational theory of genome rearrangements - Hannenhalli, Sridhar; Pevzner,Pavel (Computer Science TodayComputer Science Today, 1995)
Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions for the species of Drosophila. However, until recently there were no computer science results allowing a biologist to analyze genome rearrangements. The paper describes combinatorial problems motivated by genome rearrangements, surveys recently developed algorithms for genomic sequence comparison and presents applications of these algorithms to analyze rearrangements in herpes viruses, plant organelles, and mammalian chromosomes.

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals - Hannenhalli, Sridhar; Pevzner,Pavel (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995)

Transforming men into mice (a computational theory of genome rearrangements) - Hannenhalli, Sridhar (The Pennsylvania State University, 1995)

Transforming men into mice (polynomial algorithm for genomic distance problem) - Hannenhalli, Sridhar; Pevzner,P.A. (Foundations of Computer Science, Annual IEEE Symposium on, 1995)
Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution.
Keywords: biology computing; combinatorial properties; comparative physical mapping data; computable parameters; duality (mathematics); duality theorem; evolution (biological); Genetics; genome rearrangement algorithm; genomic distance problem; genomic rearrangements; human-mouse evolution; mammalian evolution; multi chromosomal genomes; parsimonious rearrangement scenarios; pattern matching; polynomial algorithm; polynomial time algorithm; set theory; sorting; string matching; strings; zoo fish

Voxel based object simplification - He,Taosong; Hong,Lichan; Kaufman,A.; Varshney, Amitabh; Wang,S. (Proceedings of the 6th conference on Visualization '95, 1995)
Presents a simple, robust and practical method for object simplification for applications where gradual elimination of high-frequency details is desired. This is accomplished by sampling and low-pass filtering the object into multi-resolution volume buffers and applying the marching cubes algorithm to generate a multi-resolution triangle-mesh hierarchy. Our method simplifies the genus of objects and can also help existing object simplification algorithms achieve better results. At each level of detail, a multi-layered mesh can be used for an optional and efficient antialiased rendering.
Keywords: antialiased rendering; antialiasing; buffer storage; data visualisation; high-frequency detail elimination; low-pass filtering; low-pass filters; marching cubes algorithm; mesh generation; multi-layered mesh; multi-resolution triangle-mesh hierarchy; multi-resolution volume buffers; object genus; Rendering (computer graphics); sampling; Smoothing methods; voxel based object simplification

What is Fundamental for Markov Chains: First Passage Times, Fundamental Matrices, and Group Generalized Inverses - Heyman,D. P.; O'Leary, Dianne P. (Proceedings of the Second International Workshop on Markov ChainsProceedings of the Second International Workshop on Markov Chains, 1995)

AAAI 1994 Spring Symposium Series Reports - Woods,William; Uckun,Sendar; Kohane,Isaac; Bates,Joseph; Hulthage,Ingemar; Gasser,Les; Hanks,Steve; Gini,Maria; Ram,Ashwin; desJardins, Marie; Johnson,Peter; Etzioni,Oren; et al. (AI Magazine, 1994)

Dynamic program instrumentation for scalable performance tools - Hollingsworth, Jeffrey K; Miller, B. P; Cargille, J. (Scalable High-Performance Computing Conference, 1994., Proceedings of the, 1994)
Presents a new technique called `dynamic instrumentation' that provides efficient, scalable, yet detailed data collection for large-scale parallel applications. Our approach is unique because it defers inserting any instrumentation until the application is in execution. We can insert or change instrumentation at any time during execution by modifying the application's binary image. Only the instrumentation required for the currently selected analysis or visualization is inserted. As a result, our technique collects several orders of magnitude less data than traditional data collection approaches. We have implemented a prototype of our dynamic instrumentation on the CM-5, and present results for several real applications. In addition, we include recommendations to operating system designers, compiler writers, and computer architects about the features necessary to permit efficient monitoring of large-scale parallel systems
Keywords: Application software; binary image; compiler writing; Computer architecture; Computer displays; Computerized monitoring; Concurrent computing; data acquisition; data collection; data visualisation; Data visualization; dynamic program instrumentation; efficient monitoring; executing program; Instruments; large-scale parallel applications; Large-scale systems; operating system design; Operating systems; parallel programming; program analysis; program diagnostics; program visualization; Programming profession; Sampling methods; scalable performance tools; software tools

How normal flow constrains relative depth for an active observer - Huang, L.; Aloimonos, J. (Image and vision computing, 1994)

Integrated approaches for improving the effectiveness of Plan Reuse (A Progress Report) - Kambhampati,S.; Ihrig,L.; Katukam,S.; Chen,J.; Hendler,J. A; Agrawala, Ashok K. (ARPA/Rome Laboratory knowledge-based planning and scheduling initiative: workshop proceedings: Tuscon, Arizona, February 21-24, 1994, 1994)

Mission-oriented replication of periodic tasks in real-time distributed systems - Cheng,S. T; Hwang,S. I; Agrawala, Ashok K. (Computer Science Technical Report Series; Vol. CS-TR-3256, 1994)

A modified cellular automata model of nucleotide interactions and DNA replication - Hilke,James; Lohn,Jason; Reggia, James A.; Navarro,Rafael (University of Maryland at College Park, 1994)

QUEST—Query Environment for Science Teaching - Shneiderman, Ben; Rosenfeld, A.; Marchioni,G.; Holliday,W.; Ricart, G.; Faloutsos,С.; Dick,J. (Digital Libraries' 94, 1994)
QUery Environment for Science Teaching (QUEST) is a proposed digital library implementation consisting of a set of research projects dealing with data capture and organization, content analysis, information seeking and visual interfaces.The QUEST team includes a large number of renown technical collaborators and prominent source collaborators, as well as a significant number of contributors in the University of Maryland, the central, co-ordinating agency.A large collection of multidisciplinary materials in visual and textual formats, made accessible to us by our source collaborators, will be organized to allow integrated access by users from the science education community, that is elementary school through college level teachers. QUEST will be structured so as to provide seamless access to widespread resources on disparate subjects. We intend to provide first-rate subject analysis and representation in order to provide ready access. QUEST will be accessible nationally by means of Mosaic. We propose to provide highly sophisticated querying, browsing and information investigation facilities which will handle integrated textual and visual materials without difficulty. They will be augmented by online reference and referral services, immediately accessible by the user. QUEST will provide a comprehensive information resource for science education accessible through a dynamic, visual user interface.

Regularization by Truncated Total Least Squares - Fierro,Richardo; Golub, Gene H.; Hansen,Per Christian; O'Leary, Dianne P. (Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, 1994)

A SIMD solution to the sequence comparison problem on the MGAP - Borah,M.; Bajwa,R. S; Hannenhalli, Sridhar; Irwin,M. J (International Conference on Application Specific Array Processors, 1994. Proceedings, 1994)
Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128
Keywords: AT-optimal algorithm; Biological information theory; biology computing; biosequence comparison problem; computational complexity; Computer science; Costs; database size; Databases; DNA computing; dynamic programming; dynamic programming algorithms; fine-grained massively parallel processor array; Genetics; Heuristic algorithms; maximally similar sequence; MGAP parallel computer; Micro-Grain Array Processor; Military computing; molecular biology; molecular biophysics; Nearest neighbor searches; nearest-neighbor connections; Parallel algorithms; pipeline processing; pipelined SIMD solution; sequence alignment problem; sequences

Software reliability analysis of three successive generations of a Switching System - Kaâniche,M.; Kanoun,K.; Michel Cukier; Martini,M. (Dependable Computing — EDCC-1, 1994)
Most current approaches to software reliability evaluation are based on data collected on a single generation of products. However, many applications are developed through improvements of the existing software: to the families of products are added various generations as the need for new functionalities arises. Experimental studies dealing with the analysis of data collected on families of products are seldom reported. In this paper, we analyze the data (failure and correction reports) collected on the software of three successive generations of the Brazilian Switching System — TROPICO-R, during validation and operation. A comparative analysis of the three products is done and the main results are outlined. Emphasis is placed on the evolution of the software and the corresponding failures and corrected faults. The analysis addresses: i) the modifications introduced on system components, ii) the distribution of failures and corrected faults in the components and the functions fulfilled by the system, and iii) the evolution of the failure intensity functions.
Keywords: Computer science

A study of affine matching with bounded sensor error - Grimson,W. E.L; Huttenlocher,D. P; Jacobs, David W. (International Journal of Computer Vision, 1994)
Affine transformations of the plane have been used in a number of model-based recognition systems. Because the underlying mathematics are based on exact data, in practice various heuristics are used to adapt the methods to real data where there is positional uncertainty. This paper provides a precise analysis of affine point matching under uncertainty. We obtain an expression for the range of affine-invariant values that are consistent with a given set of four points, where each image point lies in an isin-disc of uncertainty. This range is shown to depend on the actualx-y-positions of the data points. In other words, given uncertainty in the data there are no representations that are invariant with respect to the Cartesian coordinate system of the data. This is problematic for methods, such as geometric hashing, that are based on affine-invariant representations. We also analyze the effect that uncertainty has on the probability that recognition methods using affine transformations will find false positive matches. We find that there is a significant probability of false positives with even moderate levels of sensor error, suggesting the importance of good verification techniques and good grouping techniques.

Usability Experiments for the Redesign of a Telepathology Workstation - Carr,D.; Plaisant, Catherine; Hasegawa,H. (Technical Report CS-TR-3270, University of Maryland, 1994)
Dynamic telepathology uses a remotely controlled microscope to allow a pathologist to viewsamples at a remote location. However, time delays introduced by remote operation have made use of a commercial dynamic telepathology system difficult and frustrating. This paper describes experiments to evaluate and redesign the user interface. We also make recommendations for further automation to support the pathology process and increase the usefulness of the system.

Applying the CHAOS/PARTI library to irregular problems in computational chemistry and computational aerodynamics - Das,R.; Hwang,Y. S; Uysal, M.; Saltz, J.; Sussman, Alan (Scalable Parallel Libraries Conference, 1993., Proceedings of the, 1993)

A distributed algorithm for ear decomposition - Hannenhalli, Sridhar; Perumalla,K.; Chandrasekharan,N.; Sridhar,R. (, Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93, 1993)
A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
Keywords: Asynchronous communication; asynchronous communication network; Automata; Communication networks; computational complexity; Computer networks; Computer science; decomposition graph; distributed algorithm; distributed algorithms; Distributed computing; Ear; ear decomposition; graph theory; message-optimal; network decomposition; sorting; Testing; time-optimal

Dynamic control of performance monitoring on large scale parallel systems - Hollingsworth, Jeffrey K; Miller, Barton P. (Proceedings of the 7th international conference on Supercomputing - ICS '93, 1993)

Exploring remote images: a telepathology workstation - Plaisant, Catherine; Carr,David A; Hasegawa,Hiroaki (Proceedings of the INTERACT '93 and CHI '93 conference on Human factors in computing systems, 1993)

A Krylov multisplitting algorithm for solving linear systems of equations - Huang,Chiou-Ming; O'Leary, Dianne P. (Linear Algebra and its Applications, 1993)
We consider the practical implementation of Krylov subspace methods (conjugate gradients, Gmres, etc.) for parallel computers in the case where the preconditioning matrix arises from a multisplitting. We show that the algorithm can be efficiently implemented by dividing the work into tasks that generate search directions and a single task that minimizes over the resulting subspace. Each task is assigned to a subset of processors. It is not necessary for the minimization task to send frequent information to the direction generating tasks, and this leads to high utilization with a minimum of synchronization. We study the convergence properties of various forms of the algorithm and present results of numerical examples on a sequential computer.

MANDATE: managing networks using database technology - Haritsa,J. R; Ball,M. O; Roussopoulos, Nick; Datta,A.; Baras,J. S (IEEE Journal on Selected Areas in Communications, 1993)
There has been a growing demand for the development of tools to manage enterprise communication networks. A management information database is the heart of a network management system-it provides the interface between all functions of the network management system and, therefore, has to provide sophisticated functionality allied with high performance. The authors introduce the design of MANDATE (MAnaging Networks using DAtabase TEchnology), a proposed database system for effectively supporting the management of large enterprise networks. The MANDATE design makes a conscious attempt to take advantage of the special characteristics of network data and transactions, and of advances in database technology, to efficiently derive some of the required management functionality
Keywords: Communication networks; database management systems; enterprise communication networks; Heart; Information management; interface; internetworking; Local area networks; management functionality; management information database; managing networks using database technology; MANDATE; Manufacturing; network operating systems; open systems; Optical fiber cables; Research and development management; Technology management; telecommunication network management; Transaction databases; wide area networks

Potentials and limitations of pen-based computers - Citrin,Wayne; Halbert,Dan; Hewitt,Carl; Meyrowitz,Norm; Shneiderman, Ben (Proceedings of the 1993 ACM conference on Computer science, 1993)
There are four possible genres of input devices that can be attached to personal workstations; keyboard, mouse, pen, and voice. For investigating potentials and limitations of pen-based computers, we propose to compare those four categories as different types of man-machine communication channel.Even though arrow keys allow a limited scope of 2D capability in keyboard usage, the primary use of a keyboard is typing. Typing generates a linear sequence of discrete characters. The maximum speed of typing is roughly 10 characters per second, hence the bandwidth of 100 (10×10) bps. A mouse is used primarily for pointing (menu item/object selection) and then for dragging (moving and re-sizing objects). Mouse pointing generates a discrete information of a point location on a 2D (planer) plane with the maximum speed of 2 clicking per second. Each pointing may generate 20 bits of information with the bandwidth of 40 (2×20) bps. Mouse dragging generates a continuous geometric pattern in 2D. Assuming the maximum rate of 40 selections per second in the eight (3 bits) possible directions of dragging, the bandwidth of mouse dragging peaks at 120 (40×3) bps. The usage of pen on a planer flat surface of LCD unit can be divided into scribing and tapping. By scribing we mean a generation of continuous pen strokes forming a character, a gesture, or a picture. Scribing includes drawing and gesturing. Tapping corresponds to a mouse clicking. Tapping may be considered as a special kind of gesture as in the PenPoint operating system. The bandwidth of scribing can be calculated in the same manner as for mouse dragging. With the maximum rate of 100 selections of direction per second for pen, scribing may produce strokes with the speed of 300 (100×3) bps. The bandwidth of pen tapping is almost the same as that of a mouse clicking except that a selection of a point is easier by a pen (3 tappings per second) than by a mouse (2 clickings per second). Talking through a microphone generates a linear sequence of continuous speech with a high degree of redundancy. Using the CELP speech compression algorithm, the bandwidth of normal speech can be reduced to 4800 bps. By vocal signaling we mean a generation of a sequence of discrete messages each of which consists of different pitches and loudness levels. The maximum rate of signaling could be 5 messages per second with 10 differentiable pitches and 10 levels of loudness producing the bandwidth of 35 (5×7) bps. Note that mouse dragging, pen scribing, and voice talking, each produces continuous data objects. Only after quantization by sampling, the data objects can be represented by discrete data structure. By precision we mean the degree of ease in duplicating the identical information using the same input technology. Keyboard is a high precision device because there is no difficulty in generating the same character over and over again. Drawing by a mouse is more difficult than drawing by a pen, because pen is easier to control than mouse. Precision of voice is low because it is difficult to duplicate the sound of the same pitch and the same volume. By latency we mean the set-up time necessary to start generating a stream of information. The latency of using keyboard and mouse is larger than the latency of using pen and voice. By translation we mean a process of converting the information generated by the input device into a sequence of discrete symbols, i.e., a transduction of a continuous data type to a discrete data type. Translation for a keyboard is not necessary. Translation of a mouse click on a menu item requires a finite table look-up which is rather simple operation. Translation of pen scribing and mouse dragging involves a handwriting recognition algorithm which is still a difficult problem at present time. Voice recognition is a very difficult problem. With the assumption that real-time translation is feasible for handwriting recognition and speech recognition, the efficiency of input device for text entry can be measured by how many characters can be entered in a second (cps). A simulated keyboard on CRT is used for entering text by a mouse. Long handwriting on a pen computer is used for a pen. When personal workstations become down-sized, the physical dimension of an input/output device becomes a dominant factor for the mobility of workstations. Keyboard and mouse are portable but intrusive. Wireless pen is mobile and less intrusive. Voice can be ubiquitous but intrusive. One conclusion we can draw from the above analysis is that pen is mightier than mouse. A pen can replace a mouse any time any place. However, keyboard, pen, and voice have different strong points and weak points. They compensate with each other. Therefore, we predict that future workstations will carry multi-modal user-interface with any combination of keyboard, pen, and voice.

Structural ambiguity and conceptual relations - Resnik, Philip; Hearst,M. (Proceedings of the Workshop on Very Large Corpora: Academic and Industrial Perspectives, 1993)

Use of lexical conceptual structure for intelligent tutoring - Dorr, Bonnie J; Hendler,J.; Blanksteen,S.; Migdalof,B. (University of Maryland, 1993)
We describe the use of an LCS-based semantics for question-answeringexercises in foreign language training. We start by reviewing the LCS model and show how this representation can be used to support a question answering lesson as well as a limited domain discourse. An authoring tool for entering the relevant semantic knowledge is also described.

The Use of the L-Curve in the Regularization of Discrete Ill-Posed Problems - Hansen,Per Christian; O'Leary, Dianne P. (SIAM Journal on Scientific Computing, 1993)
Regularization algorithms are often used to produce reasonable solutions to ill-posed problems. The L-curve is a plot—for all valid regularization parameters—of the size of the regularized solution versus the size of the corresponding residual. Two main results are established. First a unifying characterization of various regularization methods is given and it is shown that the measurement of “size” is dependent on the particular regularization method chosen. For example, the 2-norm is appropriate for Tikhonov regularization, but a 1-norm in the coordinate system of the singular value decomposition (SVD) is relevant to truncated SVD regularization. Second, a new method is proposed for choosing the regularization parameter based on the L-curve, and it is shown how this method can be implemented efficiently. The method is compared to generalized cross validation and this new method is shown to be more robust in the presence of correlated errors.
Keywords: discrepancy principle; generalized cross validation; ill-posed problems; L-curve; parameter choice; regularization

Behavioral Visual Motion Analysis," - Aloimonos, J.; Duriç,Z.; Fermüller, Cornelia; Huang, L.; Rivlin,E.; Sharma, R. (Proceedings, DARPA Image Understanding Workshop, 1992)

DISSERTATIONS: ABSTRACTS OF INTEREST - Humphrey,Susanne M.; Shneiderman, Ben (ACM SIGCHI Bulletin, 1992)
The following abstracts were selected from a computer search using the BRS Information Technologies retrieval services of the Dissertation Abstracts International (DAI) database produced by University Microfilms International.Unless otherwise specified, paper or microform copies of dissertations may be ordered, using the UM order number, from University Microfilms International, Dissertation Copies, Post Office Box 1794, Ann Arbor, MI 488106; telephone for U.S. (except Michigan, Hawaii, or Alaska): 800/521-3042, for Canada: 800/268-6090. Price lists, ordering, and shipping information are in the introduction to the published DAI. An alternative source for copies is sometimes provided at the end of the abstract.The dissertation titles and abstracts contained here are published with permission of University Microfilms International, publishers of Dissertation Abstracts International (copyright 1985) by University Microfilms International), and may not be reproduced without their prior permission.

The effects of time delays on a telepathology user interface. - Carr,D.; Hasegawa,H.; Lemmon,D.; Plaisant, Catherine (Proceedings of the Annual Symposium on Computer Application in Medical CareProc Annu Symp Comput Appl Med Care, 1992)
Telepathology enables a pathologist to examine physically distant tissue samples by microscope operation over a communication link. Communication links can impose time delays which cause difficulties in controlling the remote device. Such difficulties were found in a microscope teleoperation system. Since the user interface is critical to pathologist's acceptance of telepathology, we redesigned the user interface for this system, built two different versions (a keypad whose movement commands operated by specifying a start command followed by a stop command and a trackball interface whose movement commands were incremental and directly proportional to the rotation of the trackball). We then conducted a pilot study to determine the effect of time delays on the new user interfaces. In our experiment, the keypad was the faster interface when the time delay is short. There was no evidence to favor either the keypad or trackball when the time delay was longer. Inexperienced participants benefitted by allowing them to move long distances over the microscope slide by dragging the field-of-view indicator on the touchscreen control panel. The experiment suggests that changes could be made to the trackball interface which would improve its performance.

Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs - Chandrasekharan,N.; Hannenhalli, Sridhar (, Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92, 1992)
The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time
Keywords: chromatic polynomials; computational complexity; Computer science; graph colouring; graph theory; matching polynomial; Polynomials; series-parallel graphs; Terminology; Tree data structures; Tree graphs

Exploratory active vision: theory - Herve,J. -Y; Aloimonos, J. (Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992, 1992)
An active approach to the integration of shape from x modules-here shape from shading and shape from texture-is proposed. The question of what constitutes a good motion for the active observer is addressed. Generally, the role of the visual system is to provide depth information to an autonomous robot; a trajectory module will then interpret it to determine a motion for the robot, which in turn will affect the visual information received. It is suggested that the motion can also be chosen so as to improve the performance of the visual system
Keywords: active observer; Active shape model; active vision; Automation; autonomous robot; CAMERAS; Computer science; Computer vision; depth information; Laboratories; Layout; Mobile robots; Motion analysis; optical flow; Robots; shape from shading; shape from texture; shape from x modules; trajectory module; Visual system

Parallel program performance metrics: a comprison and validation - Hollingsworth, Jeffrey K; Miller, B. P (Proceedings of the 1992 ACM/IEEE conference on Supercomputing, 1992)

Preconditioning parallel multisplittings for solving linear systems of equations - Huang,Chiou-Ming; O'Leary, Dianne P. (Proceedings of the 6th international conference on Supercomputing, 1992)
We consider the practical implementation of Krylov subspace methods (conjugate gradients, GMRES, etc.) for parallel computers in the case where the preconditioning matrix is a multisplitting. The algorithm can be efficiently implemented by dividing the work into tasks that generate search directions and a single task that minimizes over the resulting subspace. Each task is assigned to a subset of processors. It is not necessary for the minimization task to send information to the direction generating tasks, and this leads to high utilization with a minimum of synchronization. We study the convergence properties of various forms of the algorithm.

Six Generations of Building Walkthrough: Final Technical Report to the National Science Foundation - Brooks,Frederick P.; Airey,John; Alspaugh,John; Bell,Andrew; Brown,Randolph; Hill,Curtis; Nimscheck,Uwe; Rheingans,Penny; Rohlf,John; Smith,Dana; Turner,Douglass; Varshney, Amitabh; et al. (University of North Carolina at Chapel Hill, 1992)

Splicing signals in Drosophila: intron size, information content, and consensus sequences - Mount, Stephen M.; Burks,Christian; Herts,Gerald; Stormo,Gary D.; White,Owen; Fields,Chris (Nucleic Acids ResearchNucl. Acids Res., 1992)
A database of 209 Drosophila Introns was extracted from Genbank (release number 64.0) and examined by a number of methods in order to characterize features that might serve as signals for messenger RNA splicing. A tight distribution of sizes was observed: while the smallest introns in the database are 51 nucleotides, more than half are less than 80 nucleotides in length, and most of these have lengths in the range of 59 – 67 nucleotides. Drosophila splice sites found in large and small introns differ in only minor ways from each other and from those found in vertebrate Introns. However, larger introns have greater pyrimidlne-richness in the region between 11 and 21 nucleotides upstream of 3′ splice sites. The Drosophila branchpoint consensus matrix resembles C T A A T (in which branch formation occurs at the underlined A), and differs from the corresponding mammalian signal in the absence of G at the position immediately preceding the branchpoint. The distribution of occurrences of this sequence suggests a minimum distance between 5′ splice shies and branchpoints of about 38 nucleotides, and a minimum distance between 3′ splice sites and branchpoints of 15 nucleotides. The methods we have used detect no information in exon sequences other than in the few nucleotides immediately adjacent to the splice sites. However, Drosophila resembles many other species in that there is a discontinuity in A + T content between exons and introns, which are A + T rich.

A study of affine matching with bounded sensor error - Grimson,W.; Huttenlocher,D.; Jacobs, David W. (Computer Vision—ECCV'92, 1992)
Affine transformations of the plane have been used by modelbased recognition systems to approximate the effects of perspective projection. Because the underlying mathematics are based on exact data, in practice various heuristics are used to adapt the methods to real data where there is positional uncertainty. This paper provides a precise analysis of affine point matching under uncertainty. We obtain an expression for the range of affine-invariant values consistent with a given set of four points, where each data point lies in an exist-disc. This range is shown to depend on the actual x- y-positions of the data points. Thus given uncertainty in the data, the representation is no longer invariant with respect to the Cartesian coordinate system. This is problematic for methods, such as geometric hashing, that depend on the invariant properties of the representation. We also analyze the effect that uncertainty has on the probability that recognition methods using affine transformations will find false positive matches. We find that such methods will produce false positives with even moderate levels of sensor error.

When an Intermediate View Matters a 2D-browser Experiment - Plaisant, Catherine; Carr,David A; Hasegawa,Hiroaki (Institute for Systems Research Technical Reports, 1992)
The browsing of two dimensional images can be found in a large number of application. When the image to be viewed is much larger than the screen available, a two dimensional browser has to be provided to allow users to access all parts of the image. We show the diversity of tasks and systems available and the need for 2D browser design guidelines. In the context of a microscope image browser, we investigate one common technique consisting of a global view of the whole image, coupled to a detailed, magnified view of part of the image. In particular we look at the benefits of providing an intermediate view when the detail- to-overview ratio over 20:1. Our experience is also a good example of a real world application for which added features and added hardware need to be justified.
Keywords: Human computer interaction; Supervisory control; Systems Integration

Gdr: A visualization tool for graph algorithms - Stallmann,M.; Cleaveland, Rance; Hebbar,P. (Citeseer, 1991)

The integration of application and system based metrics in a parallel program performance tool - Hollingsworth, Jeffrey K; Irvin, R. B; Miller, B. P (ACM Sigplan Notices, 1991)

Parallel transitive closure computations using topological sort - Hua,K. A; Hannenhalli, Sridhar (, Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991, 1991)
Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm
Keywords: Computer science; Concurrent computing; data partitioning; Database systems; database theory; deductive databases; File systems; horizontal partitioning; joins; local data fragments; message passing multiprocessor system; Multiprocessing systems; Parallel algorithms; PARALLEL PROCESSING; parallel programming; parallel transitive closure; processing nodes; relation tuples; Relational databases; sorting; topological sort

Reasoning about ignorance: A note on the Bush-Gorbachev problem - Kraus,S.; Perlis, Don; Horty,J. F (Fundam. Inform., 1991)

Relative depth from motion using normal flow: an active and purposive solution - Huang, Liuqing; Aloimonos, J. (Proceedings of the IEEE Workshop on Visual Motion, 1991, 1991)
The authors show how an active observer can compute the relative depth of (stationary or moving) objects in the field of view using only the spatiotemporal derivatives of the time varying image intensity function. The solution they propose is purposive in the sense that it solves only the relative depth from motion problem and cannot be used for other problems related to motion; active in the sense that the activity of the observer is essential for the solution of the problem. Results indicate that exact computation of retinal motion does not appear to be a necessary first step for some problems related to visual motion. In addition, optic flow, whose computation is an ill-posed problem, is related to the motion of the scene only under very restrictive assumptions. As a result, the use of optic flow in some quantitative motion analysis studies is questionable
Keywords: 3D information; Automation; Computer vision; Educational institutions; Image motion analysis; image recognition; Image sequences; Laboratories; Layout; Motion analysis; Motion estimation; Nonlinear optics; normal flow; optic flow; Optical computing; Optical sensors; relative depth; retinal motion; spatiotemporal derivatives; time varying image intensity function; visual motion

Trie hashing with controlled load - Litwin,W. A; Roussopoulos, Nick; Levy,G.; Hong,W. (IEEE Transactions on Software Engineering, 1991)
Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree
Keywords: B-tree file; Computer science; controlled load; Databases; disk access; dynamic files; file organisation; high load factor; information retrieval systems; key search; load factor; Military computing; ordered insertions; Predictive models; primary key access method; Protocols; random insertions; TH file; THCL; Tree data structures; trees (mathematics); trie hashing

Catastrophe theory and computational vision - Herve, J.; Aloimonos, J. (Proc. AAAI-90 Workshop on Qualitative Vision, 1990)

IPS-2: the second generation of a parallel program measurement system - Miller, B. P; Clark, M.; Hollingsworth, Jeffrey K; Kierstead, S.; Lim,S. -S; Torzewski, T. (IEEE Transactions on Parallel and Distributed Systems, 1990)
IPS, a performance measurement system for parallel and distributed programs, is currently running on its second implementation. IPS's model of parallel programs uses knowledge about the semantics of a program's structure to provide two important features. First, IPS provides a large amount of performance data about the execution of a parallel program, and this information is organized so that access to it is easy and intuitive. Secondly, IPS provides performance analysis techniques that help to guide the programmer automatically to the location of program bottlenecks. The first implementation of IPS was a testbed for the basic design concepts, providing experience with a hierarchical program and measurement model, interactive program analysis, and automatic guidance techniques. It was built on the Charlotte distributed operating system. The second implementation, IPS-2, extends the basic system with new instrumentation techniques, an interactive and graphical user interface, and new automatic guidance analysis techniques. This implementation runs on 4.3BSD UNIX systems, on the VAX, DECstation, Sun 4, and Sequent Symmetry multiprocessor
Keywords: 4.3BSD UNIX systems; automatic guidance techniques; Automatic testing; Charlotte distributed operating system; CPA; DECstation; design concepts; distributed programs; graphical user interface; Graphical user interfaces; Instruments; interactive program analysis; IPS-2; measurement; message systems; network operating systems; Operating systems; parallel program measurement system; parallel programming; parallel programs; Performance analysis; performance analysis techniques; performance evaluation; performance measurement system; Power system modeling; program bottlenecks; program diagnostics; Programming profession; semantics; Sequent Symmetry multiprocessor; shared-memory systems; software tools; Springs; Sun; Sun 4; Unix; VAX

Motion--Boundary Illusions and their Regularization - Aloimonos, J.; Huang, Liuqing (Proceedings of the Royal Society of London. Series B: Biological Sciences, 1990)
Humans use various cues to understand the structure of the world from images. One such cue is the contours of an object formed by occlusion or from surface discontinuities. It is known that contours in the image of an object provide various amounts of information about the shape of the object in view, depending on assumptions that the observer makes. Another powerful cue is motion. The ability of the human visual system to discern structure from a motion stimulus is well known and has a solid theoretical and experimental foundation. However, when humans interpret a visual scene they use various cues to understand what they observe, and the interpretation comes from combining the information acquired from the various modules devoted to specific cues. In such an integration of modules it seems that each cue carries a different weight and importance. We performed several experiments where we made sure that the only cues available to the observer were contour and motion. It turns out that when humans combine information from contour and motion to reconstruct the shape of an object in view, if the results of the two modules - shape from contour and structure from motion - are inconsistent, they experience a perceptual result which is due to the combination of the two modules, with the influence of the contour dominating, thus giving rise to the illusion. We describe here examples of such illusions and identify the conditions under which they happen. Finally, we introduce a computational theory for combining contour and motion using the theory of regularization. The theory explains such illusions and predicts many more. The same computational theory, when applied to retinal motion estimation, explains the effect of boundaries on the perception of motion that gives rise to a set of well-known illusions described by Wallach (1976).

Priorities in process algebras - Cleaveland, Rance; Hennessy,Matthew (Information and Computation, 1990)
An operational semantics for an algebraic theory of concurrency that incorporates a notion of priority into the definition of the execution of actions is developed. An equivalence based on strong observational equivalence is defined and shown to be a congruence, and a complete axiomatization is given for finite terms. Several examples higlight the novelty and usefulness of our approach.

Testing equivalence as a bisimulation equivalence - Cleaveland, Rance; Hennessy,M. (Automatic Verification Methods for Finite State Systems, 1990)

Experiences building a syntax-directed editor - Zelkowitz, Marvin V; Kowalchack,B.; Itkin,D.; Herman,L. (Software Engineering Journal, 1989)
The paper presents a set of techniques for building robust software using the development of a microprocessor SUPPORT programming environment as an example. It discusses some of the attributes built into the system to best handle the concerns of portability, functionality, and effectiveness that had to be dealt with for the system to be reliable on a small machine, and it describes some of the choices made to obtain the best use of available hardware
Keywords: applications; editing; editor; engineering; environment; environments; microcomputer; microprocessor; portability; Programming; robust; software; software; Support; syntax-directed; text

Functional and psychosocial effects of multimodality limb-sparing therapy in patients with soft tissue sarcomas - Chang,A. E; Steinberg,S. M; Culnane,M.; Lampert,M. H; Reggia, James A.; Simpson,C. G; Hicks,J. E; White,D. E; Yang,J. J; Glatstein,E. (Journal of Clinical Oncology, 1989)

Gabriel: A design environment for DSP - Lee,E. A; Ho,W. H; Goei,E. E; Bier,J. C; Bhattacharyya, Shuvra S. (Acoustics, Speech and Signal Processing, IEEE Transactions on, 1989)

A support tool for teaching computer programming - Zelkowitz, Marvin V; Kowalchack,B.; Itkin,D.; Herman,L. (Issues in software engineering educationIssues in software engineering education, 1989)

Correspondenceless detection of depth and motion for a planar surface - Aloimonos, J.; Hervé, J. Y (University of Maryland, 1988)

An empirical comparison of pie vs. linear menus - Callahan,J.; Hopkins,D.; Weiser,M.; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems, 1988)
Menus are largely formatted in a linear fashion listing items from the top to bottom of the screen or window. Pull down menus are a common example of this format. Bitmapped computer displays, however, allow greater freedom in the placement, font, and general presentation of menus. A pie menu is a format where the items are placed along the circumference of a circle at equal radial distances from the center. Pie menus gain over traditional linear menus by reducing target seek time, lowering error rates by fixing the distance factor and increasing the target size in Fitts's Law, minimizing the drift distance after target selection, and are, in general, subjectively equivalent to the linear style.

Intentionality as internality - Perlis, Don; Hall,R. (Behavioral and Brain Sciences, 1986)

Learning a menu selection tree: training methods compared - Parton,Diana; Huffman,Keith; Pridgen,Patty; Norman,Kent; Shneiderman, Ben (Behaviour & Information Technology, 1985)
Abstract Abstract. Menu selection systems sometimes present learning problems for novice users. This comparison of four training methods for novice users found that the global tree diagram of the menu system was superior to command sequence and frame presentation methods, and somewhat better than trial and error. Methods were evaluated on the basis of (1) number of target nodes found, (2) mean number of selections to a target node, (3) recall of the menu structure, and (4) subjective rating of ease of learning.Abstract Abstract. Menu selection systems sometimes present learning problems for novice users. This comparison of four training methods for novice users found that the global tree diagram of the menu system was superior to command sequence and frame presentation methods, and somewhat better than trial and error. Methods were evaluated on the basis of (1) number of target nodes found, (2) mean number of selections to a target node, (3) recall of the menu structure, and (4) subjective rating of ease of learning.

Computer-aided assessment of transient ischemic attacks. A clinical evaluation. - Reggia, James A.; Tabb,D. R.; Price,T. R.; Banko,M.; Hebel,R. (Archives of neurology, 1984)

SLIPS - Morris,M. S; Reggia, James A.; Ahuja,S. B; Hart,J.; Watson,V. (Journal of Medical Systems, 1984)

Software Engineering Practices in the US and Japan - Zelkowitz, Marvin V; Yeh,R. T; Hamlet,R.G.; Gannon,J. D; Basili, Victor R. (Computer, 1984)

An empirical comparison of two PLATO text editors. - Shneiderman, Ben; Hill,R.; Jacob,R.; Mah,W. (Journal of Computer-Based Instruction, 1983)
Two PLATO system text editors were evaluated with 14 nonprogrammers and 14 programmers who were either university staff or college students. Half of each group learned the "plain" editor, which had 8 commands and 3 screens of HELP material; while the other half of each group learned the "fancy" editor, which had 15 commands and 1 screen of HELP material. The fancy editor is a subset of the widely used TUTOR editor, but nonprogrammers preferred the plain editor. Faster learning, faster performance, fewer invocations of HELP material, and fewer requests for human assistance were characteristic of the plain editor.

Small Ribonucleoproteins from Eukaryotes: Structures and Roles in RNA Biogenesis - Steitz,J. A.; Wolin,S. L.; Rinke,J.; Pettersson,I.; Mount, Stephen M.; Lerner,E. A.; Hinterberger,M.; Gottlieb,E. (Cold Spring Harbor Symposia on Quantitative BiologyCold Spring Harb Symp Quant Biol, 1983)
Detailed reviews describing work presented at the annual Cold Spring Harbor Symposia on Quantitative Biology

The Software Industry: A State of the Art Survey - Zelkowitz, Marvin V; Yeh,R.; Hamlet,R.G.; Gannon,J. D; Basili, Victor R. (Foundations of Empirical Software Engineering: The Legacy of Victor R. Basili, 1983)

The U1 small nuclear RNA-protein complex selectively binds a 5′ splice site in vitro - Mount, Stephen M.; Pettersson,Ingvar; Hinterberger,Monique; Karmas,Aavo; Steitz,Joan A. (Cell, 1983)
The ability of purified U1 small nuclear RNA-protein complexes (U1 snRNPs) to bind in vitro to two RNAs transcribed from recombinant DNA clones by bacteriophage T7 RNA polymerase has been studied. A transcript which contains sequences corresponding to the small intron and flanking exons of the major mouse beta-globin gene is bound in marked preference to an RNA devoid of splice site sequences. The site of U1 snRNP binding to the globin RNA has been defined by T1 ribonuclease digestion of the RNA-U1 snRNP complex. A 15-17-nucleotide region, including the 5' splice site, remains undigested and complexed with the snRNP such that it can be co-precipitated by antibodies directed against the U1 snRNP. Partial proteinase K digestion of the U1 snRNP abolishes interaction with the globin RNA, indicating that the snRNP proteins contribute significantly to RNA binding. No RNA cleavage, splicing, or recognition of the 3' splice site by U1 snRNPs has been detected. Our results are discussed in terms of the probable role of U1 snRNPs in the messenger RNA splicing of eucaryotic cell nuclei.

Structure and function of small ribonucleoproteins from eukaryotic cells - Steitz,J. A.; Berg,C; Gottlieb,E.; Hardin,J A; Hashimoto,C; Hendrick,J P; Hinterberger,M.; Krikeles,M; Lerner,M R; Mount, Stephen M. (Princess Takamatsu symposiaInt. Symp. Princess Takamatsu Cancer Res. Fund, 1982)
Autoantibodies from patients with systemic lupus erythematosus and other related diseases have been used to identify and study small RNA-protein complexes from mammalian cells. Properties of three previously described and several new classes of small ribonucleoproteins (RNPs) are reviewed. The sequence of Drosophila U1 RNA reveals that the region proposed to pair with 5' splice junctions is conserved, while that proposed to interact with 3' junctions diverges; this forces some revision of the model for U1 small nuclear (sn)RNP participation in hnRNA splicing. Further characterization of the Ro and La small RNPs has shown that the Ro small cytoplasmic (sc)RNPs are a subclass of La RNPs. Both tRNA and 5S rRNA precursors are at least transiently associated with the La protein. This raises the possibility that the La protein may be an RNA polymerase III transcription factor.
Keywords: Antigen-Antibody Complex; Autoantibodies; HUMANS; Lupus Erythematosus, Systemic; Nucleoproteins; Ribonucleoproteins; RNA Polymerase III; Transcription, Genetic

Classification of Gynecologic Flow Cytometry Data: A Comparison of Methods - O'Leary,Timothy J; O'Leary, Dianne P.; Habbersett,Mary C.; Herman,Chester J. (Journal of Analytical and Quantitative Cytology, 1981)

Transcription of cloned tRNA and 5S RNA genes in a Drosophila cell free extract - Dingermann,Theodor; Sharp,Stephen; Appel,Bernd; DeFranco,Donald; Mount, Stephen M.; Heiermann,Reinhard; Pongs,Olaf; Söll,Dieter (Nucleic Acids ResearchNucl. Acids Res., 1981)
We describe the preparation of a cell-free extract from Drosophila Kc cells which allows transcription of a variety of cloned eukaryotic RNA polymerase III genes. The extract has low RNA-processing nuclease activity and thus the major products obtained are primary transcripts.

Experimental investigations of the utility of detailed flowcharts in programming - Shneiderman, Ben; Mayer,Richard; McKay,Don; Heller,Peter (Communications of the ACM, 1977)
This paper describes previous research on flowcharts and a series of controlled experiments to test the utility of detailed flowcharts as an aid to program composition, comprehension, debugging, and modification. No statistically significant difference between flowchart and nonflowchart groups has been shown, thereby calling into question the utility of detailed flowcharting. A program of further research is suggested.
Keywords: Debugging; experimental testing; flowcharts; human factors; modification; program composition; program comprehension

Two Exploratory Experiments in Program Comprehension - Shneiderman, Ben; Ho,M.H. (Indiana University, Computer Science Department, 1975)

A graph theoretic model of data structures - Heller,J.; Shneiderman, Ben (SIGIR Forum, 1972)
The widespread development of large shared data bases has proceeded mainly on empirical notions. Only in the past few years have there been attempts at formalizing the underlying concepts into a theory of data structures. The present models have been founded on the well-established mathematical theories of sets, relations and graphs, but few descriptions have been sufficiently developed to meet the needs of a complete theory of data structures. The set theoretic formalism offered by Childs(1) or Schwartz(2) or the relational model by Codd(3) are useful but fail to give a complete description of the complex structures found in modern data bases. The graph theoretic concepts found in papers by Harary and Hsiao(4) and Earley(5) are more appealing but need further elaboration. This paper is an attempt to develop a graph theoretic model into a useful formalism for describing and manipulating data structures.