Dynamic node management and measure estimation in a state-driven fault injector - Chandra,R.; Michel Cukier; Lefever,R.; Sanders,W.; others (2000)
Validation of distributed systems using fault injectionis difficult because of their inherent complexity, lack of a global clock, and lack of an easily accessible notion of a global state. To address these challenges, the Loki fault injector injects faults based on a partial view of the global state of a distributed system, and performs a post-runtime analysis using an off-line clock synchronization algorithm to determine whether the faults were properly injected. In this paper, we first describe an enhanced runtime architecture for the Loki fault injector and then present a new method for obtaining measures in Loki. The enhanced runtime allows dynamic entry and exit of nodes in the system. It also offers more efficient multicast of notification messages and more efficient communication between state machines on the same host, and is more scalable than the previous runtime. We then detail a new and flexible method for obtaining a wide range of performance and dependability measures in Loki.

Efficient expected-case algorithms for planar point location - Arya,S.; Cheng,S. W; Mount, Dave; Ramesh,H. (Algorithm Theory-SWAT 2000, 2000)

GCCS: A graphical coordination language for system specification - Cleaveland, Rance; Du,X.; Smolka,S. (Coordination Languages and Models, 2000)

The genome sequence of Drosophila melanogaster - Adams,M.D.; Celniker,S.E.; Holt,R.A.; Evans,C.A.; Gocayne,J.D.; Amanatides,P.G.; Scherer,S.E.; Li,P.W.; Hoskins,R.A.; Galle,R.F.; others (Science, 2000)
The fly Drosophila melanogaster is one of the most intensively studied organisms in biology and serves as a model system for the investigation of many developmental and cellular processes common to higher eukaryotes, including humans. We have determined the nucleotide sequence of nearly all of the ∼120-megabase euchromatic portion of theDrosophila genome using a whole-genome shotgun sequencing strategy supported by extensive clone-based sequence and a high-quality bacterial artificial chromosome physical map. Efforts are under way to close the remaining gaps; however, the sequence is of sufficient accuracy and contiguity to be declared substantially complete and to support an initial analysis of genome structure and preliminary gene annotation and interpretation. The genome encodes ∼13,600 genes, somewhat fewer than the smaller Caenorhabditis elegansgenome, but with comparable functional diversity.

Improved Algorithms via Approximations of Probability Distributions - Chari,Suresh; Rohatgi,Pankaj; Srinivasan, Aravind (Journal of Computer and System Sciences, 2000)
We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veličković.
Keywords: derandomization; discrepancy; explicit constructions; graph coloring; Parallel algorithms; small sample spaces

In search of illumination invariants - Chen,H. F; Belhumeur,P. N.; Jacobs, David W. (Computer Vision and Pattern Recognition, 2000. Proceedings. IEEE Conference on, 2000)
We consider the problem of determining functions of an image of an object that are insensitive to illumination changes. We first show that for an object with Lambertian reflectance there are no discriminative functions that are invariant to illumination. This result leads as to adopt a probabilistic approach in which we analytically determine a probability distribution for the image gradient as a function of the surface's geometry and reflectance. Our distribution reveals that the direction of the image gradient is insensitive to changes in illumination direction. We verify this empirically by constructing a distribution for the image gradient from more than 20 million samples of gradients in a database of 1,280 images of 20 inanimate objects taken under varying lighting condition. Using this distribution we develop an illumination insensitive measure of image comparison and test it on the problem of face recognition
Keywords: comparison; image; gradient; face; invariants; image; Lambertian; recognition; recognition; illumination; recognition; object; reflectance; face

An inverse method for the acoustic detection, localization and determination of the shape evolution of a bubble - Gumerov, Nail A.; Chahine,G. L (Inverse Problems, 2000)

Loki: a state-driven fault injector for distributed systems - Chandra,R.; Lefever,R.M.; Michel Cukier; Sanders,W. H. (2000)
Distributed applications can fail in subtle ways that depend on the state of multiple parts of a system. This complicates the validation of such systems via fault injection, since it suggests that faults should be injected based on the global state of the system. In Loki, fault injection is performed based on a partial view of the global state of a distributed system, i.e. faults injected in one node of the system can depend on the state of other nodes. Once faults are injected, a post-runtime analysis, using off-line clock synchronization, is used to place events and injections on a single global timeline and to determine whether the intended faults were properly injected. Finally, experiments containing successful fault injections are used to estimate the specified measures. In addition to briefly reviewing the concepts behind Loki and its organization, we detail Loki's user interface. In particular, we describe the graphical user interfaces for specifying state machines and faults, for executing a campaign and for verifying whether the faults were properly injected
Keywords: campaign execution; computer testing; distributed applications failure; distributed processing; distributed system validation; Fault diagnosis; fault event placement; fault specification; global system state; global timeline; Graphical user interfaces; Loki; off-line clock synchronization; post-runtime analysis; specified measures estimation; state machine specification; state-driven fault injection; Synchronisation

Meta-reasoning for intelligent dialog repair - Purang,K.; Traum,D.; Purushothaman,D.; Chong,W.; Okamato,Y.; Perlis, Don (Technical report, University of Maryland, 2000)
Under consideration for other conferences (specify)? We present a logical approach and implmentation of a real-time rational agent for dialogue management, which includes an ability to represent, reason about, and repair (both implicitly and explicitly) incoherence in dialogue. We exemplify a target problem of negative feedback in action directive subdialogues, with an ability to make reference resolution sensitive to dialogue context and like intentions. The resulting system is able to behave more sensibly in several situations than earlier dialogue management systems in these same conditions. Meta-reasoning for intelligent dialog repair We present a logical approach and implmentation of a real-time rational agent for dialogue management, which includes an ability to represent, reason about, and repair (both implicitly and explicitly) incoherence in dialogue. We exemplify a target problem of negative feedback in action directive subdialogues, with an ability to make reference resolution sensitive to dialogue context and like intentions. The resulting system is able to behave more sensibly in several situations than earlier dialogue management systems in these same conditions.

Optimizing retrieval and processing of multi-dimensional scientific datasets - Chang,Chialin; Kurc, T.; Sussman, Alan; Saltz, J. (Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International, 2000)
We have developed the Active Data Repository (ADR), an infrastructure that integrates storage, retrieval, and processing of large multi-dimensional scientific datasets on distributed memory parallel machines with multiple disks attached to each node. In earlier work, we proposed three strategies for processing range queries within the ADR framework. Our experimental results show that the relative performance of the strategies changes under varying application characteristics and machine configurations. In this work we investigate approaches to guide and automate the selection of the best strategy for a given application and machine configuration. We describe analytical models to predict the relative performance of the strategies where input data elements are uniformly distributed in the attribute space of the output dataset, restricting the output dataset to be a regular d-dimensional array
Keywords: active data repository; Area measurement; Computer science; Data analysis; distributed memory parallel machines; Educational institutions; Information retrieval; Information Storage and Retrieval; infrastructure; Microscopy; Microwave integrated circuits; multi-dimensional scientific datasets retrieval; PARALLEL PROCESSING; Pathology; range queries; regular d-dimensional array; Satellites; Tomography

Phylogenetic relationships of Acanthocephala based on analysis of 18S ribosomal RNA gene sequences - García-Varela,M; Pérez-Ponce de León,G.; de la Torre,P; Cummings, Michael P.; Sarma,SS; Laclette,J. P (J Mol Evol, 2000)
Acanthocephala (thorny-headed worms) is a phylum of endoparasites of vertebrates and arthropods, included among the most phylogenetically basal tripoblastic pseudocoelomates. The phylum is divided into three classes: Archiacanthocephala, Palaeacanthocephala, and Eoacanthocephala. These classes are distinguished by morphological characters such as location of lacunar canals, persistence of ligament sacs in females, number and type of cement glands in males, number and size of proboscis hooks, host taxonomy, and ecology. To understand better the phylogenetic relationships within Acanthocephala, and between Acanthocephala and Rotifera, we sequenced the nearly complete 18S rRNA genes of nine species from the three classes of Acanthocephala and four species of Rotifera from the classes Bdelloidea and Monogononta. Phylogenetic relationships were inferred by maximum-likelihood analyses of these new sequences and others previously determined. The analyses showed that Acanthocephala is the sister group to a clade including Eoacanthocephala and Palaeacanthocephala. Archiacanthocephala exhibited a slower rate of evolution at the nucleotide level, as evidenced by shorter branch lengths for the group. We found statistically significant support for the monophyly of Rotifera, represented in our analysis by species from the clade Eurotatoria, which includes the classes Bdelloidea and Monogononta. Eurotatoria also appears as the sister group to Acanthocephala.

Phylogenetic relationships of ıt Phytophthora species based on ribosomal ITS I DNA sequence analysis with emphasis on Waterhouse groups V and VI - Förster,H; Cummings, Michael P.; Coffey,M. D (Mycol Res, 2000)
Phylogenetic relationships among Phytophthora species were investigated by sequence analysis of the internal transcribed spacer region I of the ribosomal DNA repeat unit. The extensive collection of isolates included taxa from all six morphological groups recognized by Waterhouse (1963) including molecular groups previously identified using isozymes and mtDNA restriction fragment length polymorphisms. Similar to previous studies, the inferred relationships indicated that molecular groups of P. cryptooea/drechsleri-like and P. megasperma-like taxa are polyphyletic. Morphological groups V and VI, which are differentiated by the presence of amphigynous or paragynous antheridia, are not monophyletic: species of the two groups are interspersed in the tree. Species with papillate and semi-papillate sporangia (groups I-IV) clustered together and this cluster was distinct from those of species with non-papillate sporangia. There was no congruence between the mode of antheridial attachment, sporangial caducity, or homo- or heterothallic habit and the molecular grouping of the species. Our study provides evidence that the antheridial position together with homo- or heterothallic habit does not reflect phylogenetic relationships within Phytophthora. Consequently, confirming studies done previously (Cooke & Duncan 1997), this study provides evidence that the morphological characters used in Phytophthora taxonomy are of limited value for deducing phylogenetic relationships, because they exhibit convergent evolution.

Producing Interoperable Queries for Relational and Object-Oriented Databases - Chang,Y. H; Raschid, Louiqa (Journal of Intelligent Information Systems, 2000)

Receiver based management of low bandwidth access links - Spring, Neil; Chesire,M.; Berryman,M.; Sahasranaman,V.; Anderson,T.; Bershad,B. (IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2000)
In this paper, we describe a receiver-based congestion control policy that leverages TCP flow control mechanisms to prioritize mixed traffic loads across access links. We manage queueing at the access link to: (1) improve the response time of interactive network applications; (2) reduce congestion-related packet losses; while (3) maintaining high throughput for bulk-transfer applications. Our policy controls queue length by manipulating receive socket buffer sizes. We have implemented this solution in a dynamically loadable Linux kernel module, and tested it over low-bandwidth links. Our approach yields a 7-fold improvement in packet latency over an unmodified system while maintaining 94% link utilization. In the common case, congestion-related packet losses at the access link can be eliminated. Finally, by prioritizing short flows, we show that our system reduces the time to download a complex Web page during a large background transfer by a factor of two
Keywords: Bandwidth; buffer storage; bulk-transfer applications; complex Web page; congestion control policy; Delay; dynamically loadable Linux kernel module; information resources; interactive network; Internet; Kernel; link utilization; Linux; low-bandwidth access links; mixed traffic load; packet latency; queue length; queueing theory; receive socket buffer sizes; receiver-based management; response time; short flow prioritizing; Size control; Sockets; subscriber loops; TCP flow control; telecommunication congestion control; telecommunication network management; Telecommunication traffic; Testing; Throughput; Transport protocols; Unix; Web pages

Rotation, scale, and translation resilient public watermarking for images - Lin,C.Y.; Wu,M.; Bloom,J.A.; Cox,I.J.; Miller,M.L.; Lui,Y.M. (PROC SPIE INT SOC OPT ENG, 2000)
Many electronic watermarks for still images and video content are sensitive to geometric distortions. For example,simple rotation, scaling, and/or translation (RST) of an image can prevent detection of a public watermark. In this paper, we propose a watermarking algorithm that is robust to RST distortions. The watermark is embedded into a 1-dimensional signal obtained by first taking the Fourier transform of the image, resampling the Fourier magnitudes into log-polar coordinates, and then summing a function of those magnitudes along the log-radius axis. If the image is rotated, the resulting signal is cyclically shifted. If it is scaled, the signal is multiplied by some value. And if the image is translated, the signal is unaffected. We can therefore compensate for rotation with a simple search, and for scaling by using the correlation coefficient for the detection metric. False positive results on a database of 10,000 images are reported. Robustness results on a database of 2,000 images are described. It is shown that the watermark is robust to rotation, scale and translation. In addition, the algorithm shows resistance to cropping.

Safe and Flexible Dynamic Linking of Native Code - Crary,Karl; Hicks, Michael W.; Weirich,Stephanie (Technical Reports (CIS), 2000)
We present the design and implementation of a framework for flexible and safe dynamic linking of native code. Our approach extends Typed Assembly Language with a primitive for loading and typechecking code, which is flexible enough to support a variety of linking strategies, but simple enough that it does not significantly expand the trusted computing base. Using this primitive, along with the ability to compute with types, we show that we can program many existing dynamic linking approaches. As a concrete demonstration, we have used our framework to implement dynamic linking for a type-safe dialect of C, closely modeled after the standard linking facility for Unix C programs. Aside from the unavoidable cost of verification, our implementation performs comparably with the standard, untyped approach.

A semantic theory for heterogeneous system design - Cleaveland, Rance; L\üttgen,G. (FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science, 2000)

Subgrid-scale models for compressible large-eddy simulations - Martin, M.P; Piomelli,U.; Candler,G. V (Theoretical and Computational Fluid Dynamics, 2000)

The temporal correlation hypothesis for self-organizing feature maps - Chen,Y.; Reggia, James A. (International Journal of Systems Science, 2000)

Toward the large-eddy simulation over a hypersonic elliptical cross-section cone - Martin, M.P; Weirs,G.; Candler,G. V; Piomelli,U.; Johnson,H.; Nompelis,I. (AIAA Paper No. 00-2311, 2000)

Using Feature Hierarchies in Bayesian Network Learning - desJardins, Marie; Getoor,Lise; Koller,Daphne (Abstraction, Reformulation, and Approximation, 2000)
In recent years, researchers in statistics and the UAI community have developed an impressive body of theory and algorithmic machinery for learning Bayesian networks from data. Learned Bayesian networks can be used for pattern discovery, prediction, diagnosis, and density estimation tasks. Early pioneering work in this area includes [ 5 , 9 , 10 , 13 ]. The algorithm that has emerged as the current most popular approach is a simple greedy hill-climbing algorithm that searches the space of candidate structures, guided by a network scoring function (either Bayesian or Minimum Description Length (MDL)-based). The search begins with an initial candidate network (typically the empty network, which has no edges), and then considers making small local changes such as adding, deleting, or reversing an edge in the network.

Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem - Caprara,Alberto; Italiano,Giuseppe; Mohan,G.; Panconesi,Alessandro; Srinivasan, Aravind (Approximation Algorithms for Combinatorial Optimization, 2000)
Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed Wavelength-Division Multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st -path which arc-intersects the smallest possible number of such paths. In this paper we prove the computational hardness oft his problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover.

A web-based process/material advisory system - Chen,Y. S.; Gupta,S.K.; Feng,S. (2000)
This paper describes a web-based process/material advisorysystem that can be used during conceptual design. Given a set of design requirements for a part during conceptual design stage, our system produces process sequences that can meet the design requirements. Quite often during conceptual design stage, design requirements are not precisely defined. Therefore, we allow users to describe design requirements in terms of parameter ranges. Parameter ranges are used to capture uncertainties in design requirements. Our system accounts for uncertainties in design requirements in generating and evaluating process/material combinations. Our system uses a two step algorithm. During the first step, we generate a material/process option tree. This tree represents various process/material options that can be used to meet the given set of design requirements. During the second step, we evaluate various alternative process/material options using a depth first branch and bound algorithm to identify and recommend the least expensive process/material combination to the designer. Our system can be accessed on the World Wide Web using a standard browser. Our system allows designs to consider a wide variety of process/material options during the conceptual design stage and allows them to find the most cost-effective combination. By selecting the process/material combination during the early design stages, designers can ensure that the detailed design is compatible with all of the process constraints for the selected process.

1D, 2D, 3D - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Alternate geometry - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Applications and implications - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Bifocal lens - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Building dependable distributed applications using AQUA - Ren,J.; Michel Cukier; Rubel,P.; Sanders,W. H.; Bakken,D. E.; Karr,D. A. (1999)
Building dependable distributed systems using ad hoc methods is a challenging task. Without proper support, an application programmer must face the daunting requirement of having to provide fault tolerance at the application level, in addition to dealing with the complexities of the distributed application itself. This approach requires a deep knowledge of fault tolerance on the part of the application designer, and has a high implementation cost. What is needed is a systematic approach to providing dependability to distributed applications. Proteus, part of the AQuA architecture, fills this need and provides facilities to make a standard distributed CORBA application dependable, with minimal changes to an application. Furthermore, it permits applications to specify, either directly or via the Quality Objects (QuO) infrastructure, the level of dependability they expect of a remote object, and will attempt to configure the system to achieve the requested dependability level. Our previous papers have focused on the architecture and implementation of Proteus. This paper describes how to construct dependable applications using the AQuA architecture, by describing the interface that a programmer is presented with and the graphical monitoring facilities that it provides
Keywords: ad hoc methods; application programmer; AQuA; complexities; computational complexity; dependable distributed applications; distributed CORBA application; distributed object management; Fault tolerance; fault tolerant computing; proteus

Building dependable distributed objects with the AQuA architecture - Michel Cukier; Ren,J.; Rubel,P.; Bakken,D. E.; Karr,D. A. (1999)

Content-Based Access to Multimedia Information: From Technology Trends to Sate of the Art - Perry,B.; Chang,S-K.; Dinsmore,J.; David Doermann; Rosenfeld, A.; Stevens,S. (Kluwer, 1999)

Coverage estimation methods for stratified fault-injection - Michel Cukier; Powell,D.; Ariat,J. (Computers, IEEE Transactions on, 1999)
This paper addresses the problem of estimating fault tolerance coverage through statistical processing of observations collected in fault-injection experiments. In an earlier paper, venous estimators based on simple sampling in the complete fault/activity input space and stratified sampling in a partitioned space were studied; frequentist confidence limits were derived based on a normal approximation. In this paper, the validity of this approximation is analyzed. The theory of confidence regions is introduced to estimate coverage without approximation when stratification is used. Three statistics are considered for defining confidence regions. It is shown that one-a vectorial statistic-is often more conservative than the other two. However, only the vectorial statistic is computationally tractable. We then consider Bayesian estimation methods for stratified sampling. Two methods are presented to obtain an approximation of the posterior distribution of the coverage by calculating its moments. The moments are then used to identify the type of the distribution in the Pearson distribution system, to estimate its parameters, and to obtain the coverage confidence limit. Three hypothetical example systems are used to compare the validity and the conservatism of the frequentist and Bayesian estimations
Keywords: Bayes methods; Bayesian estimations; confidence regions; coverage estimation methods; fault tolerance coverage; fault tolerant computing; frequentist confidence limits; parameter estimation; parameters estimation; Pearson distribution system; statistical processing; stratified fault-injection; stratified sampling; vectorial statistic

Departments-Book Preview-Readings in Information Visualization: Using Vision to Think - Card,S.K.; Mackinlay,J.; Shneiderman, Ben (Interactions, 1999)

Dynamic queries - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

On the evolution of reactive components: A process-algebraic approach - M\üller-Olm,M.; Steffen,B.; Cleaveland, Rance (Lecture notes in computer science, 1999)

Fault injection based on a partial view of the global state of a distributed system - Michel Cukier; Chandra,R.; Henke,D.; Pistole,J.; Sanders,W. H. (1999)
This paper describes the basis for and preliminary implementation of a new fault injector, called Loki, developed specifically for distributed systems. Loki addresses issues related to injecting correlated faults in distributed systems. In Loki, fault injection is performed based on a partial view of the global state of an application. In particular, facilities are provided to pass user-specified state information between nodes to provide a partial view of the global state in order to try to inject complex faults successfully. A post-runtime analysis, using an off-line clock synchronization and a bounding technique, is used to place events and injections on a single global time-line and determine whether the intended faults were properly injected. Finally, observations containing successful fault injections are used to estimate specified dependability measures. In addition to describing the details of our new approach, we present experimental results obtained from a preliminary implementation in order to illustrate Loki's ability to inject complex faults predictably
Keywords: bounding technique; clock synchronization; distributed programming; distributed software systems; fault injection; Loki; post-runtime analysis; program testing; program verification; software reliability; Synchronisation

Fisheye views - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Focus+ context - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Genes and other samples of DNA sequence data for phylogenetic inference - Cummings, Michael P.; Otto,S. P; Wakeley,J. (The Biological Bulletin, 1999)

Impact of Cl− and Na+ ions on simulated structure and dynamics of βARK1 PH domain - Pfeiffer,Stefania; Fushman, David; Cowburn,David (Proteins: Structure, Function, and Bioinformatics, 1999)
A nonzero net charge of proteins at pH 7 is usually compensated by the addition of charge-balancing counter ions during molecular dynamics simulation, which reduces electrostatic interactions. For highly charged proteins, like the βARK1 PH domain used here, it seems reasonable to also add explicit salt ions. To assess the impact of explicit salt ions, two molecular dynamics simulations of solvated βARK1 PH domain have been carried out with different numbers of Cl− and Na+ ions, based on the Cornell et al. force field and the Ewald summation, which was used in the treatment of long-range electrostatic interactions. Initial positions of ions were obtained from the AMBER CION program. Increasing the number of ions alters the average structure in loop regions, as well as the fluctuation amplitudes of dihedral angles. We found unnaturally strong interactions between side chains in the absence of salt ions. The presence of salt ions reduces these electrostatic interactions. The time needed for the equilibration of the ionic environment around the protein, after initial placement of ions close to oppositely charged side chains, is in the nanosecond time range, which can be shortened by using a higher ionic strength. Our results also suggest selecting those methods that do not place the ions initially close to the protein surface. Proteins 1999;35:206–217. © 1999 Wiley-Liss, Inc.
Keywords: counter ions; electrostatic interaction; equilibration; GRK2 PH domain; hydrogen bonds; ionic solvent; ionic strength; molecular dynamics simulation; Proteins

Information workspaces - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Infosphere, workspace, tools, objects - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Infrastructure for building parallel database systems for multi-dimensional data - Chang,C.; Ferreira,R.; Sussman, Alan; Saltz, J. (IPPS, 1999)

Interaction - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Interactive analysis - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Internet and Infosphere - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Latent Semantic Indexing via a Semi-Discrete Matrix Decomposition - Kolda,Tamara G.; O'Leary, Dianne P. (The Mathematics of Information Coding, Extraction and DistributionThe Mathematics of Information Coding, Extraction and Distribution, 1999)
With the electronic storage of documents comes the possibility of building search engines that can automatically choose documents relevant to a given set of topics. In information retrieval, we wish to match queries with relevant documents. Documents can be represented by the terms that appear within them, but literal matching of terms does not necessarily retrieve all relevant documents. There are a number of information retrieval systems based on inexact matches. Latent Semantic Indexing represents documents by approximations and tends to cluster documents on similar topics even if their term profiles are somewhat different. This approximate representation is usually accomplished using a low-rank singular value decomposition (SVD) approximation. In this paper, we use an alternate decomposition, the semi-discrete decomposition (SDD). For equal query times, the SDD does as well as the SVD and uses less than one-tenth the storage for the MEDLINE test set.

Local model checking and protocol analysis - Du,X.; Smolka,S. A; Cleaveland, Rance (International Journal on Software Tools for Technology Transfer (STTT), 1999)

Multiple dimensions> 3 - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

Network Programming Using PLAN - Hicks, Michael W.; Kakkar,Pankaj; Moore,Jonathan; Gunter,Carl; Nettles,Scott (Internet Programming LanguagesInternet Programming Languages, 1999)
We present here a methodology for programming active networks in the environment defined by our new language PLAN (Packet Language for Active Networks). This environment presumes a two-level architecture consisting of: 1. active packets carrying PLAN code; and 2. downloadable, node-resident services written in more general-purpose languages. We present several examples which illustrate how these two features can be combined to implement various network functions.

Object-relational queries into multidimensional databases with the active data repository - Ferreira,R.; Kurc, T.; Beynon, M.; Chang,C.; Sussman, Alan; Saltz,J. H (Parallel Processing Letters, 1999)

Overview+ detail - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Physical data - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

A practical approach to implementing real-time semantics - Bhat,G.; Cleaveland, Rance; L\üttgen,G. (Annals of Software Engineering, 1999)

A Priori Test of SGS Models in Compressible Turbulence - Martin, M.P; Piomelli,U.; Candler,G. V; Center,Army High Performance Computing Research; Minnesota,University of (Army High Performance Computing Research Center, 1999)

Proteus: a flexible infrastructure to implement adaptive fault tolerance in AQuA - Sabnis,C.; Michel Cukier; Ren,J.; Rubel,P.; Sanders,W. H.; Bakken,D. E.; Karr,D. (1999)
Building dependable distributed systems from commercial off-the-shelf components is of growing practical importance. For both cost and production reasons, there is interest in approaches and architectures that facilitate building such systems. The AQuA architecture is one such approach; its goal is to provide adaptive fault tolerance to CORBA applications by replicating objects, providing a high-level method for applications to specify their desired dependability, and providing a dependability manager that attempts to reconfigure a system at runtime so that dependability requests are satisfied. This paper describes how dependability is provided in AQuA. In particular it describes Proteus, the part of AQuA that dynamically manages replicated distributed objects to make them dependable. Given a dependability request, Proteus chooses a fault tolerance approach and reconfigures the system to try to meet the request. The infrastructure of Proteus is described in this paper, along with its use in implementing active replication and a simple dependability policy
Keywords: adaptive fault tolerance; AQuA; commercial off-the-shelf components; CORBA applications; cost; dependable distributed systems; distributed object management; object replication; proteus; reconfigurable architectures; Runtime; Software architecture; software fault tolerance

Querying Very Large Multi-dimensional Datasets in ADR - Chialin,T. K; Kurc, T.; Chang,C.; Ferreira,R.; Sussman, Alan; Saltz, J. (In Proceedings of SC99: High Performance Networking and Computing, 1999)

Readings in Information Visualization: Using Vision to Think - Card,Stuart K.; Mackinlay,Jock D.; Shneiderman, Ben (Morgan Kaufmann, 1999)
This groundbreaking book defines the emerging field of information visualization and offers the first-ever collection of the classic papers of the discipline, with introductions and analytical discussions of each topic and paper. The authors' intention is to present papers that focus on the use of visualization to discover relationships, using interactive graphics to amplify thought. This book is intended for research professionals in academia and industry; new graduate students and professors who want to begin work in this burgeoning field; professionals involved in financial data analysis, statistics, and information design; scientific data managers; and professionals involved in medical, bioinformatics, and other areas.* Full-color reproduction throughout* Author power team - an exciting and timely collaboration between the field's pioneering, most-respected names* The only book on Information Visualization with the depth necessary for use as a text or as a reference for the information professional* Text includes the classic source papers as well as a collection of cutting edge work
Keywords: Computer Graphics; Computers / Computer Engineering; Computers / Computer Graphics; Computers / Computer Graphics / General; Computers / Computer Science; Computers / General; Computers / Information Technology; Computers / Information Theory; Computers / Intelligence (AI) & Semantics; Computers / Social Aspects / Human-Computer Interaction; IMAGE PROCESSING; Information display systems; Information Visualization; Psychology / General; Visualization

Reports on the AAAI Fall Symposia - De Giacomo,Giuseppe; desJardins, Marie; Canamero,Dolores; Wasson,Glenn; Littman,Michael; Allwein,Gerard; Marriott,Kim; Meyer,Bernd; Webb,Barbara; Consi,Tom (AI Magazine, 1999)
The Association for the Advancement of Artificial Intelligence (AAAI) held its 1998 Fall Symposium Series on 23 to 25 October at the Omni Rosen Hotel in Orlando, Florida. This article contains summaries of seven of the symposia that were conducted: (1) Cognitive Robotics; (2) Distributed, Continual Planning; (3) Emotional and Intelligent: The Tangled Knot of Cognition; (4) Integrated Planning for Autonomous Agent Architectures; (5) Planning with Partially Observable Markov Decision Processes; (6) Reasoning with Visual and Diagrammatic Representations; and (7) Robotics and Biology: Developing Connections.

The RNA World - Woodson,Sarah A.; Mount, Stephen M. (Cold Spring Harbor Laboratory Press, 1999)

A rotation, scale and translation resilient public watermark - Wu,M.; Miller,M.L.; Bloom,J.A.; Cox,I.J. (Acoustics, Speech, and Signal Processing, 1999. Proceedings., 1999 IEEE International Conference on, 1999)
Summary form only given. Watermarking algorithms that are robust to the common geometric transformations of rotation, scale and translation (RST) have been reported for cases in which the original unwatermarked content is available at the detector so as to allow the transformations to be inverted. However, for public watermarks the problem is significantly more difficult since there is no original content to register with. Two classes of solution have been proposed. The first embeds a registration pattern into the content while the second seeks to apply detection methods that are invariant to these geometric transformations. This paper describes a public watermarking method which is invariant (or bares a simple relation) to the common geometric transforms of rotation, scale, and translation. It is based on the Fourier-Mellin transform which has previously been suggested. We extend this work, using a variation based on the Radon transform. The watermark is inserted into a projection of the image. The properties of this projection are such that RST transforms produce simple or no effects on the projection waveform. When a watermark is inserted into a projection, the signal must eventually be back projected to the original image dimensions. This is a one to many mapping that allows for considerable flexibility in the watermark insertion process. We highlight some theoretical and practical issues that affect the implementation of an RST invariant watermark. Finally, we describe preliminary experimental results
Keywords: algorithms; Fourier; coding; coding; image; data; transform; dimensions; projection; Fourier-Mellin; image; invariant; methods; detector; experimental; of; pattern; rotation; projection; mapping; original; public; registration; security; resilient; results; geometric; transform; detection; transform; RST; transformations; image; transforms; image; transforms; Radon; watermark; RST; watermark; scale; watermark; translation; watermark; watermarking; waveform; registration

Solution Structure of the Proapoptotic Molecule BID: A Structural Basis for Apoptotic Agonists and Antagonists - McDonnell,James M; Fushman, David; Milliman,Curt L.; Korsmeyer,Stanley J.; Cowburn,David (Cell, 1999)
Members of the BCL2 family of proteins are key regulators of programmed cell death, acting either as apoptotic agonists or antagonists. Here we describe the solution structure of BID, presenting the structure of a proapoptotic BCL2 family member. An analysis of sequence/structure of BCL2 family members allows us to define a structural superfamily, which has implications for general mechanisms for regulating proapoptotic activity. It appears two criteria must be met for proapoptotic function within the BCL2 family: targeting of molecules to intracellular membranes, and exposure of the BH3 death domain. BID’s activity is regulated by a Caspase 8–mediated cleavage event, exposing the BH3 domain and significantly changing the surface charge and hydrophobicity, resulting in a change of cellular localization.

Statecharts via process algebra - Liittgen,G.; Cleaveland, Rance (CONCUR'99: concurrency theory: 10th International Conference, Eindhoven, the Netherlands, August 24-27, 1999: proceedings, 1999)

Subgrid-scale model for the temperature fluctuations in reacting hypersonic turbulent flows - Martin, M.P; Candler,G. V (Physics of Fluids, 1999)

Text in 1D - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Text in 2D - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Text in 3D - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Text in 3D+ time - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

A Theory of Efficiency for Markovian Processes - Bernardo,M.; Cleaveland, Rance (University of Bologna, 1999)

Using vision to think - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization: using vision to think, 1999)

Visually enhanced objects - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 1999)

3D motion and shape representations in visual servo control - Fermüller, Cornelia; Cheong, L. F; Aloimonos, J. (The International Journal of Robotics Research, 1998)

Approximation algorithms for multiple-tool miling - Arya,Sunil; Cheng,Siu-Wing; Mount, Dave (Proceedings of the fourteenth annual symposium on Computational geometry, 1998)

AQuA: an adaptive architecture that provides dependable distributed objects - Cukier, Michel; Ren,J.; Sabnis,C.; Henke,D.; Pistole,J.; Sanders,W. H.; Bakken,D. E.; Berman,M.E.; Karr,D. A.; Schantz,R.E. (Seventeenth IEEE Symposium on Reliable Distributed Systems, 1998)
Dependable distributed systems are difficult to build. This is particularly true if they have dependability requirements that change during the execution of an application, and are built with commercial off-the-shelf hardware. In that case, fault tolerance must be achieved using middleware software, and mechanisms must be provided to communicate the dependability requirements of a distributed application to the system and to adapt the system's configuration to try to achieve the desired dependability. The AQuA architecture allows distributed applications to request a desired level of availability using the Quality Objects (QuO) framework and includes a dependability manager that attempts to meet requested availability levels by configuring the system in response to outside requests and changes in system resources due to faults. The AQuA architecture uses the QuO runtime to process and invoke availability requests, the Proteus dependability manager to configure the system in response to faults and availability requests, and the Ensemble protocol stack to provide group communication services. Furthermore, a CORBA interface is provided to application objects using the AQuA gateway. The gateway provides a mechanism to translate between process-level communication, as supported by Ensemble, and IIOP messages, understood by Object Request Brokers. Both active and passive replication are supported, and the replication type to use is chosen based on the performance and dependability requirements of particular distributed applications
Keywords: adaptive architecture; AQuA; availability requests; client-server systems; commercial off-the-shelf hardware; CORBA; dependability manager; dependability requirements; dependable distributed objects; distributed object management; Ensemble protocol stack; Fault tolerance; group communication services; middleware software; Object Request Brokers; process-level communication; proteus; Quality Objects; replication; software fault tolerance; Software quality

Cellular automata models of self-replicating systems - Reggia, James A.; Chou,H. H.; Lohn,J. D (Advances in Computers, 1998)

The design and evaluation of a high-performance earth science database - Shock,Carter T.; Chang,Chialin; Moon,Bongki; Acharya,Anurag; Davis, Larry S.; Saltz,Joel; Sussman, Alan (Parallel Computing, 1998)
Earth scientists have encountered two major obstacles in their attempts to use remotely sensed imagery to analyze the earth's land cover dynamics. First, the volume of data involved is very large and second, significant preprocessing is needed before the data can be used. This is particularly so for studies that analyze global trends using data sets that cover multiple years. In this paper, we present the design of an earth science database as well as our early experiences with it. The primary design goal of this database is to facilitate efficient access to and preprocessing of large volumes of satellite data. Our initial design assumed that the main bottleneck in the system would be retrieving data from the disks. However, experimental results show that precise identification of all the data values corresponding to a query can take a significant amount of time. The problem is even more pronounced in designing the system to attempt to minimize time spent performing I/O. We therefore discuss a major redesign of the system that includes a reworking of the indexing scheme and a reorganization of the data on disks. Experimental results show that the redesigned system performs significantly better than the original system, providing interactive response times for local queries.
Keywords: Communication; High-performance I/O; load balancing; scalability; Scientific databases

The Design of a Telepathology Workstation: Exploring Remote Images - Carr,David; Plaisant, Catherine; Hasegawa,Hiroaki (Technical Reports of the Computer Science Department, 1998)
Dynamic telepathology uses a tele-operated microscope to allowpathologists to view samples 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 recomendations for further automation to support the pathology process and increase the usefulness of the system. Copyright, 1994, by David Carr, Catherine Plaisant, and Hiroaki Hasegawa All rights reserved (Also cross-referenced as CAR-TR-708)
Keywords: Technical Report

Designing a real-time telepathology workstation to mitigate communication delays - Carr,David; Plaisant, Catherine; Hasegawa,Hiroaki (Interacting with Computers, 1998)
Dynamic telepathology uses a teleoperated microscope to allow pathologists to view samples 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 the iterative redesign of the user interface. We redesigned the interface, conducted experiments to evaluate the improvements, and then redesigned the user interface based on the results.Our work shows that predictive displays and local maps improve user control of the microscope and increase user comfort with the system. It also indicates that some degree of automation is necessary to support the navigation process and increase the overall usefulness of the system. Therefore, we also make recommendations for further automation to support the telepathology process and increase the usefulness of the system. While performed on a specific device using a dedicated communications system, the same problems would be encountered in other environments. For example, Internet-based systems that enable remote control or require browsing of large images will need to compensate for time delays and can benefit from our experience with the telepathology application.
Keywords: Iterative design; Predictive displays; Remote control; Supervisory control; Telepathology; Time delays

Determining the similarity of deformable shapes - Basri,Ronen; Costa,Luiz; Geiger,Davi; Jacobs, David W. (Vision Research, 1998)
Determining the similarity of two shapes is a significant task in both machine and human vision systems that must recognize or classify objects. The exact properties of human shape similarity judgements are not well understood yet, and this task is particularly difficult in domains where the shapes are not related by rigid transformations. In this paper we identify a number of possibly desirable properties of a shape similarity method, and determine the extent to which these properties can be captured by approaches that compare local properties of the contours of the shapes, through elastic matching. Special attention is devoted to objects that possess articulations, i.e. articulated parts. Elastic matching evaluates the similarity of two shapes as the sum of local deformations needed to change one shape into another. We show that similarities of part structure can be captured by such an approach, without the explicit computation of part structure. This may be of importance, since although parts appear to play a significant role in visual recognition, it is difficult to stably determine part structure. We also show novel results about how one can evaluate smooth and polyhedral shapes with the same method. Finally, we describe shape similarity effects that cannot be handled by current approaches.

Digital dynamic telepathology–the Virtual Microscope. - Afework,A.; Beynon,M. D; Bustamante,F.; Cho,S.; Demarzo,A.; Ferreira,R.; Miller,R.; Silberman,M.; Saltz, J.; Sussman, Alan; others (Proceedings of the AMIA Symposium, 1998)

Double quaternions for motion interpolation - Ge,Q. J; Varshney, Amitabh; Menon,J. P; Chang,C. F (Proceedings of the ASME Design Engineering Technical Conference, 1998)
This paper describes the concept of double quaternions, anextension of quaternions, and shows how they can be used for ef- fective three-dimensional motion interpolation. Motion interpo- lation using double quaternions has several advantages over the method of interpolating rotation and translation independently and then combining the results. First, double quaternions pro- vide a conceptual framework that allows one to handle rotational and translational components in a unified manner. Second, re- sults obtained by using double quaternions are coordinate frame invariant. Third, double quaternions allow a natural way to trade- off robustness against accuracy. Fourth, double quaternions, be- ing a straightforward extension of quaternions, can be integrated into several existing systems that currently use quaternions with translational components, with a only small coding effort.

Dynamics of bubbles in conditions of gas hydrate formation - Gumerov, Nail A.; Chahine,G. L (8th International Offshore and Polar Engineering Conference, Montreal, Canada, 1998)

Effects of Errors in the Viewing Geometry on Shape Estimation - LoongFah Cheong; Fermüller, Cornelia; Aloimonos, J. (Computer Vision and Image Understanding, 1998)
A sequence of images acquired by a moving sensor contains information about the three-dimensional motion of the sensor and the shape of the imaged scene. Interesting research during the past few years has attempted to characterize the errors that arise in computing 3D motion (egomotion estimation) as well as the errors that result in the estimation of the scene's structure (structure from motion). Previous research is characterized by the use of optic flow or correspondence of features in the analysis as well as by the employment of particular algorithms and models of the scene in recovering expressions for the resulting errors. This paper presents a geometric framework that characterizes the relationship between 3D motion and shape in the presence of errors. We examine how the three-dimensional space recovered by a moving monocular observer, whose 3D motion is estimated with some error, is distorted. We characterize the space of distortions by its level sets, that is, we characterize the systematic distortion via a family of iso-distortion surfaces, which describes the locus over which the depths of points in the scene in view are distorted by the same multiplicative factor. The framework introduced in this way has a number of applications: Since the visible surfaces have positive depth (visibility constraint), by analyzing the geometry of the regions where the distortion factor is negative, that is, where the visibility constraint is violated, we make explicit situations which are likely to give rise to ambiguities in motion estimation, independent of the algorithm used. We provide a uniqueness analysis for 3D motion analysis from normal flow. We study the constraints on egomotion, object motion, and depth for an independently moving object to be detectable by a moving observer, and we offer a quantitative account of the precision needed in an inertial sensor for accurate estimation of 3D motion.

Effects of Errors in the Viewing Geometry on Shape Estimation* 1,* 2 - Cheong, L. F; Fermüller, Cornelia; Aloimonos, J. (Computer Vision and Image Understanding, 1998)

Evaluation of EuroWordNet-and LCS-based lexical resources for machine translation - Dorr, Bonnie J; Marti,A.; Castellon,I. (Proceedings from First International Conference on Language Resources & Evaluation, 1998)
We evaluate two types of lexical resources with respect to their applicability to interlingual machine translation: (1) a EuroWordNet-based database of bilingual links between Spanish and English words; and (2) a repository of semantically classified verbs with their corresponding Lexical Conceptual Structure (LCS) representations. We examine the utility of these two resources for the task of lexical selection in machine translation. Our approach uses a coarse-grained graph-matching scheme that selects target-language words based on their LCS representation. The final selection of target-language terms is based on a finer-grained linking into the EuroWordNet-based repository.

Extension of Spherical Harmonic Method to RF Transient Regime - Lin,C. K.; Goldsman,N.; Chang,C. H.; Mayergoyz, Issak D; Aronowitz,S.; Dong,J.; Belova,N. (Simulation of semiconductor processes and devices 1998: SISPAD 98, 1998)
The space and time dependent electron Boltzmann transport equation (BTE)is solved sclf-consistently with the Poisson and transient hole current-continuity equation. A transient Spherical Harmonic expansion method is used to solve the BTE. By this method we can efficiently solve the BTE in the RF regime to observe how the complete distribution function responds to a rapid transient. Calculations on a BJT, which give the time dependent distribution function over a large energy range 0-3eV, throughout the device, as well as average quantities, require only 40 minutes CPU time on an Alpha workstation.

Frequentist and Bayesian Coverage Estimations for Stratified Fault-Injection - Michel Cukier; Arlat,J.; Powell,D. (DEPENDABLE COMPUTING AND FAULT TOLERANT SYSTEMS, 1998)
This paper addresses the problem of estimating the coverage of fault tolerancethrough statistical processing of observations collected in fault-injection experiments. In an earlier paper, we have studied various frequentist estimation methods based on simple sampling in the whole fault/activity input space and stratified sampling in a partitioned space. In this paper, Bayesian estimation methods are introduced for stratified sampling. Two methods are presented to obtain an approximation of the posterior distribution of the coverage by calculating its moments. The moments are then used to identify the type of the distribution in the Pearson distribution system, to estimate its parameters and to obtain the coverage confidence limit. Two hypothetical example systems are used to compare the validity and the conservatism of the Bayesian and frequentist estimations. It is shown that one Bayesian estimation method is valid for both examples and that its estimations are much less conservative than the frequentist ones. However, the Bayesian estimations for stratified sampling are still conservative compared to estimations for simple sampling.

Genetic nomenclature for Trypanosoma and Leishmania. - Clayton,C.; Adams,M.; Almeida,R.; Baltz,T.; Barrett,M.; Bastien,P.; Belli,S.; Beverley,S.; Biteau,N.; Blackwell,J.; others (Molecular and biochemical parasitology, 1998)

Genetic nomenclature for Trypanosoma and Leishmania. - Clayton, C; Adams, M; Almeida, R; Baltz, T; Barrett, M; Bastien, P; Belli, S; Beverley, S; Biteau, N; Blackwell, J; Blaineau, C; Boshart, M; et al. (Mol Biochem Parasitol, 1998)
Keywords: Animals; Leishmania; Terminology as Topic; Trypanosoma

Infinite Probabilistic and Nonprobabilistic Testing⋆ - Kumar,K. N; Cleaveland, Rance; Smolka,S. A (Foundations of software technology and theoretical computer science: 18th Conference, Chennai, India, December 17-19, 1998: proceedings, 1998)

Low-bandwidth routing and electrical power networks - Cook,Doug; Faber,Vance; Marathe,Madhav; Srinivasan, Aravind; Sussmann,Yoram (Automata, Languages and ProgrammingAutomata, Languages and Programming, 1998)
Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-disjoint-paths problem (MDP) is to connect as many of the given pairs as possible using pairwise edge-disjoint paths in G . We study a relative of this problem: we have a network with fixed link capacities that may have to service large demands when necessary. In particular, individual demands are allowed to exceed capacities, and thus flows for some request pairs necessarily have to be split into different flow-paths. This is the framework for computational problems arising from: (i) electrical power networks due to the proposed deregulation of the electric utility industry in the USA, and (ii) applications such as real-time Internet services (e.g., telephone, fax, video). We show that these problems come in a few variants, some efficiently solvable and many NP -hard; we also present approximation algorithms for many of the NP -hard variants presented. Some of our approximation algorithms benefit from certain improved tail estimates that we derive; the latter also yield improved approximations for a family of packing integer programs.

Nucleotide sequence diversity at the alcohol dehydrogenase 1 locus in wild barley (ıt Hordeum vulgare ssp. ıt spontaneum): an evaluation of the background selection hypothesis - Cummings, Michael P.; Clegg,M. T (Proc Natl Acad Sci USA, 1998)
The background selection hypothesis predicts a reduction in nucleotide site diversity and an excess of rare variants, owing to linkage associations with deleterious alleles. This effect is expected to be amplified in species that are predominantly self-fertilizing. To examine the predictions of the background selection hypothesis in self-fertilizing species, we sequenced 1,362 bp of adh1, a gene for alcohol dehydrogenase (Adh; alcohol:NAD+ oxidoreductase, EC 1.1.1.1), in a sample of 45 accessions of wild barley, Hordeum vulgare ssp. spontaneum, drawn from throughout the species range. The region sequenced included 786 bp of exon sequence (part of exon 4, all of exons 5-9, and part of exon 10) and 576 bp of intron sequence (all of introns 4-9). There were 19 sites polymorphic for nucleotide substitutions, 8 in introns, and 11 in exons. Of the 11 nucleotide substitutions in codons, 4 were synonymous and 7 were nonsynonymous, occurring uniquely in the sample. There was no evidence of recombination in the region studied, and the estimated effective population size (Ne) based on synonymous sites was approximately 1.8-4.2 x 10(5). Several tests reveal that the pattern of nonsynonymous substitutions departs significantly from neutral expectations. However, the data do not appear to be consistent with recovery from a population bottleneck, recent population expansion, selective sweep, or strong positive selection. Though several features of the data are consistent with background selection, the distributions of polymorphic synonymous and intron sites are not perturbed toward a significant excess of rare alleles as would be predicted by background selection.

Phylogenetic relationships of platyhelminthes based on 18S ribosomal gene sequences - Campos,A.; Cummings, Michael P.; Reyes,J. L; Laclette,J. P (Mol Phylogenet Evol, 1998)
Nucleotide sequences of 18S ribosomal RNA from 71 species of Platyhelminthes, the flatworms, were analyzed using maximum likelihood, and the resulting phylogenetic trees were compared with previous phylogenetic hypotheses. Analyses including 15 outgroup species belonging to eight other phyla show that Platyhelminthes are monophyletic with the exception of a sequence putatively from Acoela sp., Lecithoepitheliata, Polycladida, Tricladida, Trematoda (Aspidobothrii + Digenea), Monogenea, and Cestoda (Gyrocotylidea + Amphilinidea + Eucestoda) are monophyletic groups. Catenulids form the sister group to the rest of platyhelminths, whereas a complex clade formed by Acoela, Tricladida, "Dalyellioida", and perhaps "Typhloplanoida" is sister to Neodermata. "Typhloplanoida" does not appear to be monophyletic; Fecampiida does not appear to belong within "Dalyellioida," nor Kalyptorhynchia within "Typhloplanoida." Trematoda is the sister group to the rest of Neodermata, and Monogenea is sister group to Cestoda. Within Trematoda, Aspidobothrii is the sister group of Digenea and Heronimidae is the most basal family in Digenea. Our trees support the hypothesis that parasitism evolved at least twice in Platyhelminthes, once in the ancestor to Neodermata and again in the ancestor of Fecampiida, independently to the ancestor of putatively parasitic "Dalyellioida."

Pigment composition of putatively achlorophyllous angiosperms - Cummings, Michael P.; Welschmeyer,N. A (Plant Syst Evol, 1998)
Chlorophyll and carotenoid pigment composition was determined for ten species of putatively achlorophyllous angiosperms using high-performance liquid chromatography. Four families were represented: Lennoaceae (Pholisma arenarium); Monotropaceae (Allotropa virgata, Monotropa uniflora, Pterospora andromedea, Sarcodes sanguinea); Orobanchaceae (Epifagus virginiana, Orobanche cooperi, O. uniflora); Orchidaceae (Cephalanthera austinae, Corallorhiza maculata). Chlorophyll a was detected in all tars, but chlorophyll b was only detected in Corallorhiza maculata. The relative amount of chlorophyll and chlorophyll-related pigments in these plants is greatly reduced compared to fully autotrophic angiosperms.
Keywords: Angiospermae; Lennoaceae; Monotropaceae; Orchidaceae; Lennoaceae; Monotropaceae; Orobanchaceae; Orchidaceae; chlorophyll; carotenoid; pigment; high-performance liquid chromatography; Orobanchaceae

Probabilistic resource failure in real-time process algebra - Philippou,A.; Cleaveland, Rance; Lee,I.; Smolka,S.; Sokolsky,O. (CONCUR'98 Concurrency Theory, 1998)

Problem solving during artificial selection of self-replicating loops* 1 - Chou,H. H.; Reggia, James A. (Physica D: Nonlinear Phenomena, 1998)

Scalable Data Parallel Algorithms for Texture Synthesis and Compression using Gibbs Random Fields - Bader,David A.; JaJa, Joseph F.; Chellapa, Rama (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
This paper introduces scalable data parallel algorithms for image processing. Focusing on Gibbs and Markov Random Field model representation for textures, we present parallel algorithms for texture synthesis, compression, and maximum likelihood parameter estimation, currently implemented on Thinking Machines CM-2 and CM-5. Use of fine-grained, data parallel processing techniques yields real-time algorithms for texture synthesis and compression that are substantially faster than the previously known sequential implementations. Although current implementations are on Connection Machines, the methodology presented here enables machine independent scalable algorithms for a number of problems in image processing and analysis. (Also cross-referenced as UMIACS-TR-93-80.)
Keywords: Technical Report

Scheduling Aperiodic and Sporadic Tasks in Hard Real-Time Systems - Choi,Seonho; Agrawala, Ashok K. (Technical Reports from UMIACS, UMIACS-TR-97-44, 1998)
The stringent timing constraints as well as the functional correctnessare essential requirements of hard real-time systems. In such systems, scheduling plays a very important role in satisfying these constraints. The priority based scheduling schemes have been used commonly due to the simplicity of the scheduling algorithm. However, in the presence of task interdependencies and complex timing constraints, such scheduling schemes may not be appropriate due to the lack of an efficient mechanism to schedule them and to carry out the schedulability analysis. In contrast, the time based scheduling scheme may be used to schedule a set of tasks with greater degree of schedulability achieved at a cost of higher complexity of off-line scheduling. One of the drawbacks of currently available scheduling schemes, however, is known to be their inflexibility in dynamic environments where dynamic processes exist, such as aperiodic and sporadic processes. We develop and analyze scheduling schemes which efficiently provide the flexibility required in real-time systems for scheduling processes arriving dynamically. This enables static hard periodic processes and dynamic processes(aperiodic or sporadic) to be jointly scheduled. (Also cross-referenced as UMIACS-TR-97-44)
Keywords: Technical Report

Self-replicating structures: evolution, emergence, and computation - Reggia, James A.; Lohn,J. D; Chou,H. H. (Artificial Life, 1998)

Solution structure and dynamics of the bioactive retroviral M domain from rous sarcoma virus - McDonnell,James M; Fushman, David; Cahill,Sean M.; Zhou,Wenjun; Wolven,Amy; Wilson,Carol B; Nelle,Timothy D; Resh,Marilyn D; Wills,John; Cowburn,David (Journal of Molecular Biology, 1998)
A biologically active construct of the retroviral M domain from the avian Rous sarcoma virus is defined and its solution structure described. This M domain is fully active in budding and infectivity without myristylation. In spite of a sequence homology level that suggests no relationship among M domains and the family of matrix proteins in mammalian retroviruses, the conserved structural elements of a central core allow an M domain sequence motif to be described for all retroviruses. The surface of the M domain has a highly clustered positive patch comprised of sequentially distant residues. An analysis of the backbone dynamics, incorporating rotational anisotropy, is used to estimate the thermodynamics of proposed domain oligomerization.
Keywords: heteronuclear NMR spectroscopy; protein dynamics; RSV matrix protein; sequence homology; three-dimensional structure

The Solution Structure and Dynamics of the Pleckstrin Homology Domain of G Protein-coupled Receptor Kinase 2 (β-Adrenergic Receptor Kinase 1) A BINDING PARTNER OF Gβγ SUBUNITS - Fushman, David; Najmabadi-Haske,Taraneh; Cahill,Sean; Zheng,Jie; LeVine,Harry; Cowburn,David (Journal of Biological ChemistryJ. Biol. Chem., 1998)
The solution structure of an extended pleckstrin homology (PH) domain from the β-adrenergic receptor kinase is obtained by high resolution NMR. The structure establishes that the β-adrenergic receptor kinase extended PH domain has the same fold and topology as other PH domains, and there are several unique features, most notably an extended C-terminal α-helix that behaves as a molten helix, and a surface charge polarity that is extensively modified by positive residues in the extended α-helix and the C terminus. These observations complement biochemical evidence that the C-terminal portion of this PH domain participates in protein-protein interactions with Gβγ subunits. This suggests that the C-terminal segment of the PH domain may function to mediate protein-protein interactions with the targets of PH domains.

Sorting out searching: a user-interface framework for text searches - Shneiderman, Ben; Byrd,Donald; Croft,W. Bruce (Communications of the ACM, 1998)

T2 - Chang,Chialin; Acharya,Anurag; Sussman, Alan; Saltz,Joel (ACM SIGMOD Record, 1998)

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)

Utility elicitation as a classification problem - Chajewska,Urszula; Getoor, Lise; Norman,Joseph; Shahar,Yuval (Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, 1998)
We investigate the application of classification techniques to utility elicitation. In a decision problem, two sets of parameters must generally be elicited: the probabilities and the utilities. While the prior and conditional probabilities in the model do not change from user to user, the utility models do. Thus it is necessary to elicit a utility model separately for each new user. Elicitation is long and tedious, particularly if the outcome space is large and not decomposable. There are two common approaches to utility function elicitation. The first is to base the determination of the user's utility function solely on elicitation of qualitative preferences. The second makes assumptions about the form and decomposability of the utility function. Here we take a different approach: we attempt to identify the new user's utility function based on classification relative to a database of previously collected utility functions. We do this by identifying clusters of utility functions that minimize an appropriate distance measure. Having identified the clusters, we develop a classification scheme that requires many fewer and simpler assessments than full utility elicitation and is more robust than utility elicitation based solely on preferences. We have tested our algorithm on a small database of utility functions in a prenatal diagnosis domain and the results are quite promising.

Walkthroughs of complex environments using image-based simplification - Darsa,L.; Costa,B.; Varshney, Amitabh (Computers & Graphics, 1998)
We present an image-based technique to accelerate the navigation in complex static environments. We perform an image-space simplification of each sample of the scene taken at a particular viewpoint and dynamically combine these simplified samples to produce images for arbitrary viewpoints. Since the scene is converted into a bounded complexity representation in the image space, with the base images rendered beforehand, the rendering speed is relatively insensitive to the complexity of the scene. The proposed method correctly simulates the kinetic depth effect (parallax), occlusion, and can resolve the missing visibility information. This paper describes a suitable representation for the samples, a specific technique for simplifying them, and different morphing methods for combining the sample information to reconstruct the scene. We use hardware texture mapping to implement the image-space warping and hardware affine transformations to compute the view-dependent warping function.
Keywords: image-based rendering, image morphing, virtual walkthroughs, visibility, image compositing

Is the Web really different from everything else? - Shneiderman, Ben; Nielsen,Jakob; Butler,Scott; Levi,Michael; Conrad,Frederick (CHI 98 conference summary on Human factors in computing systems, 1998)
Keywords: design; user experience; World Wide Web

An algebraic theory of multiple clocks - Cleaveland, Rance; L\üttgen,G.; Mendler,M. (CONCUR'97: Concurrency Theory, 1997)

Bringing treasures to the surface: iterative design for the Library of Congress National Digital Library Program - Plaisant, Catherine; Marchionini,Gary; Bruns,Tom; Komlodi,Anita; Campbell,Laura (Proceedings of the SIGCHI conference on Human factors in computing systems, 1997)
Keywords: browse; design process; digital libraries; dynamic query; java; preview; search; web design

Challenges in sending large radiology images over military communications channels - Cleary,K.R.; Levine,B.A.; Norton,G.S.; Mundur,P.V. (Proceedings of SPIE, 1997)

Clarifying search: A user-interface framework for text searches - Shneiderman, Ben; Byrd,D.; Croft, W.B. (D-lib magazine, 1997)
Current user interfaces for textual database searching leave much to be desired: individually, they are often confusing, and as a group, they are seriously inconsistent. We propose a four- phase framework for user-interface design: the framework provides common structure and terminology for searching while preserving the distinct features of individual collections and search mechanisms. Users will benefit from faster learning, increased comprehension, and better control, leading to more effective searches and higher satisfaction.

A computational model of acute focal cortical lesions - Goodall,S.; Reggia, James A.; Chen,Y.; Ruppin,E.; Whitney,C. (Stroke, 1997)

Data models, visual representations, metaphors: how to solve the puzzle? (panel) - Catarci,T.; Costabile,M. F.; Cruz,I. F.; Ioannidis,Y.; Shneiderman, Ben (Proceedings of the third IFIP WG2.6 working conference on Visual database systems 3 (VDB-3), 1997)
Keywords: data model; metaphor; visual representation

Dynamic priorities for modeling real-time - Bhat,G.; Cleaveland, Rance; L\üttgen,G. (Proc. of the Formal Description Techniques and Protocol Specification, Testing and Verification (FORTE X/PSTV XVII’97), 1997)

Effective redundant constraints for online scheduling - Getoor, Lise; Ottosson,G.; Fromherz,M.; Carlson,B. (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL IN℡LIGENCE, 1997)
The use of heuristics as a means to improve constraint solverperformance has been researched widely. However, most work has been on problem-independent heuristics (e.g., vari- able and value ordering), and has focused on offline prob- lems (e.g., one-shot constraint satisfaction). In this paper, we present an online scheduling problem for which we are developing a real-time scheduling algorithm. While we can and do use generic heuristics in the scheduler, here we fo- cus on the use of domain-specific redundant constraints to ef- fectively approximate optimal offline solutions. We present a taxonomy of redundant domain constraints, and examine their impact on the effectiveness of the scheduler. We also describe several techniques for generating redundant con- straints, which can be applied to a large class of job shop scheduling problems.

Emergence of self-replicating structures in cellular automata space - Reggia, James A.; Chou,H. H. (Physica D, 1997)

Enabling virtual reality for large-scale mechanical CAD datasets - Varshney, Amitabh; El-Sana,J.; Evans,F.; Darsa,L.; Costa,B.; Skiena,S. (Proceedings of ASME Design Engineering Technical Conferences, Sept, 1997)
Reconciling scene realism with interactivity has emerged asone of the most important areas in making virtual reality fea- sible for large-scale mechanical CAD datasets consisting of sev- eral millions of primitives. This paper surveys our research and related work for achieving interactivity without sacrificing real- ism in virtual reality walkthroughs and flythroughs of polygonal CAD datasets. We outline our recent work on efficient genera- tion of triangle strips from polygonal models that takes advan- tage of compression of connectivity information. This results in substantial savings in rendering, transmission, and storage. We outline our work on genus-reducing simplifications as well as real-time view-dependent simplifications that allow on-the-fly selection amongst multiple levels of detail, based upon lighting and viewing parameters. Our method allows multiple levels of detail to coexist on the same object at different regions and to merge seamlessly without any cracks or shading artifacts. We also present an overview of our work on hardware-assisted image- based rendering that allows interactive exploration of computer- generated scenes.

The evolution of plant nuclear genes - Clegg,M. T; Cummings, Michael P.; Durbin,M. L (Proc Natl Acad Sci USA, 1997)
We analyze the evolutionary dynamics of three of the best-studied plant nuclear multigene families. The data analyzed derive from the genes that encode the small subunit of ribulose-1,5-bisphosphate carboxylase (rbcS), the gene family that encodes the enzyme chalcone synthase (Chs), and the gene family that encodes alcohol dehydrogenases (Adh). In addition, we consider the limited evolutionary data available on plant transposable elements. New Chs and rbcS genes appear to be recruited at about 10 times the rate estimated for Adh genes, and this is correlated with a much smaller average gene family size for Adh genes. In addition, duplication and divergence in function appears to be relatively common for Chs genes in flowering plant evolution. Analyses of synonymous nucleotide substitution rates for Adh genes in monocots reject a linear relationship with clock time. Replacement substitution rates vary with time in a complex fashion, which suggests that adaptive evolution has played an important role in driving divergence following gene duplication events. Molecular population genetic studies of Adh and Chs genes reveal high levels of molecular diversity within species. These studies also reveal that inter- and intralocus recombination are important forces in the generation allelic novelties. Moreover, illegitimate recombination events appear to be an important factor in transposable element loss in plants. When we consider the recruitment and loss of new gene copies, the generation of allelic diversity within plant species, and ectopic exchange among transposable elements, we conclude that recombination is a pervasive force at all levels of plant evolution.

The geometry of visual space distortion - Fermüller, Cornelia; LoongFah Cheong; Aloimonos, J. (Algebraic Frames for the Perception-Action CycleAlgebraic Frames for the Perception-Action Cycle, 1997)
The encounter of perception and action happens at the intermediate representations of space-time. In many of the computational models employed in the past, it has been assumed that a metric representation of physical space can be derived by visual means. Psychophysical experiments, as well as computational considerations, can convince us that the perception of space and shape has a much more complicated nature, and that only a distorted version of actual, physical space can be computed. This paper develops a computational geometric model that explains why such distortion might take place. The basic idea is that, both in stereo and motion, we perceive the world from multiple views. Given the rigid transformation between the views and the properties of the image correspondence, the depth of the scene can be obtained. Even a slight error in the rigid transformation parameters causes distortion of the computed depth of the scene. The unified framework introduced here describes this distortion in computational terms. We characterize the space of distortions by its level sets, that is, we characterize the systematic distortion via a family of iso-distortion surfaces which describes the locus over which depths are distorted by some multiplicative factor. Clearly, functions of the distorted space exhibiting some sort of invariance, produce desirable representations for biological and artificial systems [13]. Given that humans' estimation of egomotion or estimation of the extrinsic parameters of the stereo apparatus is likely to be imprecise, the framework is used to explain a number of psychophysical experiments on the perception of depth from motion or stereo.

The main-chain dynamics of the dynamin pleckstrin homology (PH) domain in solution: analysis of 15N relaxation with monomer/dimer equilibration - Fushman, David; Cahill,Sean; Cowburn,David (Journal of Molecular Biology, 1997)
The backbone dynamics of the pleckstrin homology (PH) domain from dynamin were studied by 15N NMR relaxation (R1 and R2) and steady state heteronuclear 15N {1H} nuclear Overhauser effect measurements at 500 and 600 MHz, at protein concentrations of 1.7 mM and 300 μM, and by molecular dynamics (MD) simulations. The analysis was performed using the model-free approach. The method was extended in order to account for observed partial (equilibrium) dimerization of the protein at NMR concentrations. A model is developed that takes into account both rapid monomer-dimer exchange and anisotropy of the over-all rotation of the dimer. The data show complex dynamics of the dynamin PH domain. Internal motions in elements of the secondary structure are restricted, as inferred from the high value of the order parameter (S2 ∼ 0.9) and from the local correlation time <100 ps. Of the four extended loop regions that are disordered in the NMR-derived solution structure of the protein, loops β1/β2 and β5/β6 are involved in a large-amplitude (S2 down to 0.2 to 0.3) subnanosecond to nanosecond time-scale motion. Reorientation of the loops β3/β4 and β6/β7, in contrast, is restricted, characterized by the values of order parameter S2 ∼ 0.9 more typical of the protein core. These loops, however, are involved in much slower processes of motion resulting in a conformational exchange on a microsecond to submillisecond time scale. The motions of the terminal regions (residues 1 to 10, 122 to 125) are practically unrestricted (S2 down to 0.05, characteristic times in nanosecond time scale), suggesting that these parts of the sequence do not participate in the protein fold. The analysis shows a larger sensitivity of the 15N relaxation data to protein microdynamic parameters (S2, τloc) when protein molecular mass (τc) increases. The use of negative values of the steady state 15N{1H} NOEs as an indicator of the residues not belonging to the folded structure is suggested. The amplitudes of local motion observed in the MD simulation are in a good agreement with the NMR data for the amide NH groups located in the protein core.
Keywords: dynamin; monomer/dimer equilibration; NMR relaxation; pleckstrin homology domain; protein dynamics

Multiscale Document Page Segmentation Using Soft Decision Integration - Etemad,K.; David Doermann; Chellapa, Rama (IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997)

Navigating static environments using image-space simplification and morphing - Darsa,Lucia; Costa Silva,Bruno; Varshney, Amitabh (Proceedings of the 1997 symposium on Interactive 3D graphics, 1997)

Perturbation analysis for the QR decomposition - Chang,X. C.; Paige,C. C.; Stewart, G.W. (SIAM Journal on Matrix Analysis and Applications, 1997)

Probabilistic verification of a synchronous round-based consensus protocol - Duggal,H.S.; Michel Cukier; Sanders,W. H. (1997)
Consensus protocols are used in a variety of reliable distributed systems, including both safety-critical and business-critical applications. The correctness of a consensus protocol is usually shown, by making assumptions about the environment in which it executes, and then proving properties about the protocol. But proofs about a protocol's behavior are only as good as the assumptions which were made to obtain them, and violation of these assumptions can lead to unpredicted and serious consequences. We present a new approach for the probabilistic verification of synchronous round based consensus protocols. In doing so, we make stochastic assumptions about the environment in which a protocol operates, and derive probabilities of proper and non proper behavior. We thus can account for the violation of assumptions made in traditional proof techniques. To obtain the desired probabilities, the approach enumerates possible states that can be reached during an execution of the protocol, and computes the probability of achieving the desired properties for a given fault and network environment. We illustrate the use of this approach via the evaluation of a simple consensus protocol operating under a realistic environment which includes performance, omission, and crash failures
Keywords: business-critical applications; consensus protocol correctness; crash failures; formal verification; network environment; probabilistic verification; probabilities; probability; program verification; proper behavior; protocol behavior; Protocols; realistic environment; reliable distributed systems; safety-critical applications; simple consensus protocol; software reliability; stochastic assumptions; synchronous round based consensus protocol; synchronous round based consensus protocols; traditional proof techniques

Regulation of Cable Television - Agrawala, Ashok K.; CILINGIROGLU,A.; Lee,S. (The Froehlich/Kent Encyclopedia of Telecommunications: Volume 15-Radio Astronomy to Submarine Cable SystemsThe Froehlich/Kent Encyclopedia of Telecommunications: Volume 15-Radio Astronomy to Submarine Cable Systems, 1997)

Satellite DNA repeat sequence variation is low in three species of burying beetles in the genus ıt Nicrophorus (Coleoptera: Silphidae) - King,L. M; Cummings, Michael P. (Mol Biol Evol, 1997)
Three satellite DNA families were identified in three species of burying beetles, Nicrophorus orbicollis, N. marginatus, and N. americanus. Southern hybridization and nucleotide sequence analysis of individual randomly cloned repeats shows that these satellite DNA families are highly abundant in the genome, are composed of unique repeats, and are species-specific. The repeats do not have identifiable core elements or substructures that are similar in all three families, and most interspecific sequence similarity is confined to homopolymeric runs of A and T. Satellite DNA from N. marginatus and N. americanus show single-base-pair indels among repeats, but single-nucleotide substitutions characterize most of the repeat variability. Although the repeat units are of similar lengths (342, 350, and 354 bp) and A + T composition (65%, 71%, and 71%, respectively), the average nucleotide divergence among sequenced repeats is very low (0.18%, 1.22%, and 0.71%, respectively). Transition/transversion ratios from the consensus sequence are 0.20, 0.69, and 0.70, respectively.

Scheduling in a high performance remote-sensing data server - Chang,C.; Sussman, Alan; Saltz, J. (Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing. SIAM, 1997)

Spanish EuroWordNet and LCS-Based Interlingual MT - Dorr, Bonnie J; Marti,M. Antonia; Castellon,Irene (IN PROCEEDINGS OF THE MT SUMMIT WORKSHOP ON INTERLINGUAS IN MT, 1997)
We present a machine translation framework in which the interlingua -- Lexical Conceptual Structure (LCS) -- is coupled with a definitional component that includes bilingual (EuroWordNet) links between words in the source and target languages. While the links between individual words are language-specific, the LCS is designed to be a language-independent, compositional representation. We take the view that the two types of information -- shallower, transfer-like knowledge as well as deeper, compositional knowledge -- can be reconciled in interlingual machine translation, the former for overcoming the intractability of LCS-based lexical selection, and the latter for relating the underlying semantics of two words cross-linguistically. We describe the acquisition process for these two information types and present results of hand-verification of the acquired lexicon. Finally, we demonstrate the utility of the two information types in interlingual MT.

Symbolic Compression and Processing of Document Images - Kia,Omid; David Doermann; Rosenfeld,Azriel; Chellapa, Rama (University of Maryland, College Park, 1997)
In this paper we describe a compression and representation scheme which exploits the component-level redundancy found within a document image. The approach identifies patterns which appear repeatedly, represents similar patterns with a single prototype, stores the location of pattern instances and codes the residuals between the prototypes and the pattern instances. Using a novel encoding scheme, we provide a representation which facilitates scalable lossy compression and progressive transmission, and supports document image analysis in the compressed domain. We motivate the approach, provide details of the encoding procedures, report compression results and describe a class of document image understanding tasks which operate on the compressed representation.

Titan: a High-Performance Remote-sensing Database - Bongki,C. C; Chang,C.; Moon,B.; Acharya, A.; Shock,C.; Sussman, Alan; Saltz, J. (In Proceedings of the 1997 International Conference on Data Engineering, 1997)

Toward motion picture grammars - Bolle,Ruud; Aloimonos, J.; Fermüller, Cornelia (Computer Vision — ACCV'98Computer Vision — ACCV'98, 1997)
We are interested in processing video data for the purpose of solving a variety of problems in video search, analysis, indexing, browsing and compression. Instead of concentrating on a particular problem, in this paper we present a framework for developing video applications. Our basic thesis is that video data can be represented at a higher level of abstraction as a string generated by a grammar, termed motion picture grammar. The rules of that grammar relate different spatiotemporal representations of the video content and, in particular, representations of action.

Using WordNet to Posit Hierarchical Structure in Levin's Verb Classes - Olsen,M.B.; Dorr, Bonnie J; Clark,D.J. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1997)
In this paper we report on experiments using WordNet synset tags to evaluate the seman-tic properties of the verb classes cataloged by Levin 1993. This paper represents ongoing research begun at the University of Pennsylvania (Rosenzweig et al. 1997, Palmer et al. 1997) and the University of Maryland (Dorr and Jones 1996b, 1996d, 1996e). Using WordNet sense tags to constrain the intersection of Levin classes, we avoid spurious class intersections introduced by homonymy and polysemy (run a bath, run a mile). By adding class intersections based on a single shared sense-tagged word, we minimize the impact of the non-exhaustiveness of Levin's database (Dorr and Olsen 1996, Dorr to appear). By examining the syntactic properties of the intersective classes, we provide a clearer picture of the relationship between WordNet/EuroWordNet and the LCS interlingua for machine translation and other NLP applications.

The vegetation canopy lidar mission - Dubayah, R.; Blair,J. B.; Bufton,J. L.; Clark,D. B.; JaJa, Joseph F.; Knox,R.; Luthcke,S. B.; Prince,S.; Weishampel,J. (Proceedings of Land Satellite Information in the Next Decade, II: Sources and Applications. Bethesda (MD): American Society of Photogrammetry and Remote Sensing, 1997)
The Vegetation Canopy Lidar (VCL) is the first selected mission of NASA’s new EarthSystem Science Pathfinder program. The principal goal of VCL is the characterization of the three-dimensional structure of the earth; in particular, canopy vertical and horizontal structure and land surface topography. Its primary science objectives are: landcover characterization for terrestrial ecosystem modeling, monitoring and prediction; landcover characterization for climate modeling and prediction; and, production of a global reference data set of topographic spot heights and transects. VCL will provide unique data sets for understanding important environ- mental issues including climatic change and variability, biotic erosion and sustainable landuse, and will dramatically improve our estimation of global biomass and carbon stocks, fractional forest cover, forest extent and condition. It will also provide canopy data critical for biodiversity, natural hazard, and climate studies. Scheduled for launch in early 2000, VCL is an active lidar remote sensing system consisting of a five-beam instrument with 25 m contiguous along track resolution. The five beams are in a circular configuration 8 km across and each beam traces a separate ground track spaced 2 km apart, eventually producing 2 km coverage between 65° N and S. VCL’s core measurement objectives are: (1) canopy top heights; (2) vertical distribution of intercepted surfaces (e.g. leaves and branches); and, (3) ground surface topographic elevations. These measurements are used to derive a variety of science data products including canopy heights, canopy vertical distribution, and ground elevations gridded monthly at 1° resolution and every 6 months at 2 km resolution, as well as a 2 km fractional forest cover product.

Visual space distortion - Fermüller, Cornelia; LoongFah Cheong; Aloimonos, J. (Biological Cybernetics, 1997)
We are surrounded by surfaces that we perceive by visual means. Understanding the basic principles behind this perceptual process is a central theme in visual psychology, psychophysics, and computational vision. In many of the computational models employed in the past, it has been assumed that a metric representation of physical space can be derived by visual means. Psychophysical experiments, as well as computational considerations, can convince us that the perception of space and shape has a much more complicated nature, and that only a distorted version of actual, physical space can be computed. This paper develops a computational geometric model that explains why such distortion might take place. The basic idea is that, both in stereo and motion, we perceive the world from multiple views. Given the rigid transformation between the views and the properties of the image correspondence, the depth of the scene can be obtained. Even a slight error in the rigid transformation parameters causes distortion of the computed depth of the scene. The unified framework introduced here describes this distortion in computational terms. We characterize the space of distortions by its level sets, that is, we characterize the systematic distortion via a family of iso-distortion surfaces which describes the locus over which depths are distorted by some multiplicative factor. Given that humans' estimation of egomotion or estimation of the extrinsic parameters of the stereo apparatus is likely to be imprecise, the framework is used to explain a number of psychophysical experiments on the perception of depth from motion or stereo.

An algebraic theory of process efficiency - Natarajan,V.; Cleaveland, Rance (, Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings, 1996)
This paper presents a testing-based semantic theory for reasoning about the efficiency of concurrent systems as measured in terms of the amount of their internal activity. The semantic preorders are given an algebraic characterization, and their optimality is established by means of a full abstractness result. They are also shown to subsume existing bisimulation-based efficiency preorders. An example is provided to illustrate the utility of this approach
Keywords: algebraic characterization; algebraic specification; algebraic theory; bisimulation-based efficiency preorders; Calculus; calculus of communicating systems; Carbon capture and storage; Computer science; concurrent systems; formal logic; formal specification; full abstractness result; internal activity; optimality; process efficiency; reasoning; semantic preorders; System testing; testing-based semantic theory

Alignment of coexisting cortical maps in a motor control model - Chen,Y.; Reggia, James A. (Neural computation, 1996)

Compressed-domain document retrieval and analysis - Kia,Omid E; David Doermann; Chellapa, Rama (SPIE Conference of Multimedia Storage and Archiving Systems, 1996)
In this paper, we first describe a structural compression technique which has been designed to facilitate document text image storage, retrieval, and processing. This technique provides an efficient representation of textural images and lends itself to lossy compression, progressive transmission, direct access to sub-regions of the document and document processing in the compressed domain. We describe a data structure which can be used to efficiently store the compressed information, provide algorithms for creating and manipulating it, and present results of document processing on images compressed form the University of Washington database.

The Concurrency Factory: A development environment for concurrent systems - Cleaveland, Rance; Lewis,P.; Smolka,S.; Sokolsky,O. (Computer Aided Verification, 1996)

Directions of motion fields are hardly ever ambiguous - Brodsky, Tomas; Fermüller, Cornelia; Aloimonos, J. (Computer Vision — ECCV '96Computer Vision — ECCV '96, 1996)
Recent literature [7, 10, 11, 9, 13, 17] provides a number of results regarding uniqueness aspects of motion fields and exact image displacements due to 3-D rigid motion. Here instead of the full motion field we consider only the direction of the motion field due to a rigid motion and ask what can we say about the three-dimensional motion information contained in it. This paper provides a geometric analysis of this question based solely on the fact that the depth of the surfaces in view is positive (i.e. that the surface in view is in front of the camera). With this analysis we thus offer a theoretical foundation for image constraints employing only the sign of flow in various directions and provide a solid basis for their utilization in addressing 3D dynamic vision problems.

DNA sequence variation in the ribosomal internal transcribed spacer region of freshwater ıt Cladophora species (Chlorophyta) - Marks,J. C; Cummings, Michael P. (J Phycol, 1996)
Freshwater species of Cladophora (Chlorophyta) are globally distributed and occupy an unusually wide range of ecological habitats. Delineating species is difficult because most easily observed morphological traits are highly variable and because sexual reproduction has not been clearly documented. Synthesizing ecological data on freshwater Cladophora species is problematic because it is unclear whether freshwater Cladophora species comprise many genetically distinct species or a few ecologically and morphologically variable and / or plastic species. We determined nucleotide sequences of the internal transcribed spacer (ITS) region of the nuclear ribosomal cistron of freshwater Cladophora species from a wide range of habitats and geographic locations. We compared these sequences to those derived from culture collections of C. fracta and C. glomerata, the two most commonly reported freshwater Cladophora species. Cladophora fracta and C. glomerata had very similar ITS sequences (95.3%). All other sequences were identical to those from the C. fracta or C. glomerata culture collections with the exception of one California sample that was similar to both C. fracta (95.6%) and C. glomerata (92.4%). ITS genotypes did not correlate with morphology or geography. This analysis shows that common freshwater Cladophora species comprise very few (possibly one) ecologically and morphologically variable species.
Keywords: algae; Chlorophyta; Cladophora; diversity; freshwater; genetic; internal; spacer; transcribed

Effect of Chemical Reactions on Decaying Isotropic Turbulence - Martin, M.P; Candler,G. V (APS Meeting Abstracts, 1996)

Effect of chemical reactions on the decay of isotropic homogeneous turbulence - Aguirre,M; Candler,G. V; Martin, M.P (AIAA Fluid Dynamics Conference, 1996)
Direct numerical simulations, (DNS), are usedto simulate the decay of an isotopic, turbulent, chemically-reacting flow at high temperatures. The independent parameters that govern the physical pro- cess are introduced. The different effects from each of the parameters in the flow are explained by using the results from the DNS. It is found that there is a feedback mechanism between the chemical reactions and the turbulent motion. This feedback is positive for exothermic reactions and negative for endother- mic reactions.

Effects of varying parameters on properties of self-organizing feature maps - Cho,S.; Jang,M.; Reggia, James A. (Neural Processing Letters, 1996)

Efficient distribution analysis via graph contraction - Sheffler,T.; Schreiber,R.; Pugh, William; Gilbert,J.; Chatterjee,S. (Languages and Compilers for Parallel Computing, 1996)

Efficient local model-checking for fragments of the modal $μ$-calculus - Bhat,G.; Cleaveland, Rance (Tools and Algorithms for the Construction and Analysis of Systems, 1996)

Efficient model checking via the equational μ-calculus - Bhat,G.; Cleaveland, Rance (, Eleventh Annual IEEE Symposium on Logic in Computer Science, 1996. LICS '96. Proceedings, 1996)
This paper studies the use of an equational variant of the modal μ-calculus as a unified framework for efficient temporal logic model checking. In particular we show how an expressive temporal logic, CTL*, may be efficiently translated into the μ-calculus. Using this translation, one may then employ μ-calculus model-checking techniques, including on-the-fly procedures, BDD-based algorithms and compositional model-checking approaches, to determine if systems satisfy formulas in CTL*
Keywords: Automata; BDD-based algorithms; Boolean functions; Calculus; compositional model-checking approaches; computational complexity; Computer science; CTL*; Data structures; Encoding; equational variant; equational μ-calculus; Equations; expressive temporal logic; Logic; Maintenance; modal μ-calculus; Model checking; on-the-fly procedures; Surges; temporal logic; temporal logic model checking; unified framework

Estimation of time-dependent coverage - Arlat,D. P. M. C. J.; Crouzet,Y. (LAAS-CNRS: Laboratory for analysis and architecture of systems, 1996)
It is well-known that the dependability that can be achieved by a fault-tolerant systemis particularly sensitive to both the asymptotic value of coverage and to the time distribution of coverage. However, most previous work on coverage evaluation by statistical processing of the results of fault-injection experiments has only been concerned with estimating asymptotic coverage. In this paper, we tackle the problem of estimating the parameters of models that also account for coverage latency. After discussing some data sets resulting from fault-injection experiments on practical systems, we propose a series of coverage latency models that might be considered to account for the observed phenomena in a system dependability evaluation. We consider both exponential and non-exponential models, and assess their pertinence by means of a sensitivity study. We confirm previous results that latency can have an extremely important effect on the achievable dependability. We also show that the shape of the latency distribution has only a minor impact in the practical case of systems with high asymptotic coverage. A simple action model based on an exponential latency distribution is therefore proposed. We show how worst-case confidence limits can be obtained for the parameters of this action model and study the effects of data truncation that are unavoidable in any practical measurements of latency. We conclude by a critical assessment of the proposed estimation technique and a demonstration of its application to practical data sets.

Evolutionary biology of parasitic platyhelminths: The role of molecular phylogenetics - Blair,D; Campos,A.; Cummings, Michael P.; Laclette,J. P (Parasitol Today, 1996)
As our appreciation of the diversity within the flatworms has grown, so too has our curiosity about the ways in which these varied creatures are related to one another. In particular, the parasitic groups (trematodes, cestodes and monogeneans have been the focus of enquiry. Until recently, morphology, anatomy and life histories have provided the raw data for building hypotheses on relationships. Now, ultrastructural evidence, and most recently, molecular data from nucleic acid sequences, have been brought to bear on the topic. Here, David Blair, Andrés Campos, Michael Cummings and Juan Pedro Laclette discuss the ways in which molecular data, in particular, are helping us recognize the various lineages of flatworms.

A high performance image database system for remotely sensed imagery - Shock,C.; Chang,C.; Davis, Larry S.; Goward,S.; Saltz, J.; Sussman, Alan (Euro-Par'96 Parallel Processing, 1996)

Identification of the Binding Site for Acidic Phospholipids on the PH Domain of Dynamin: Implications for Stimulation of GTPase Activity - Zheng,Jie; Cahill,Sean M.; Lemmon,Mark A.; Fushman, David; Schlessinger,Joseph; Cowburn,David (Journal of Molecular Biology, 1996)
It has recently been suggested that pleckstrin homology (PH) domains bind specifically to phospholipids, with phosphatidylinositol-4,5-bisphosphate (PtdIns(4,5)P2) being most strongly bound. This observation suggests that PH domains may be responsible for membrane association of proteins in which they occur. Further, this membrane association may be regulated by enzymes that modify lipid head groups to which PH domains may bind. We have studied the binding of phospholipids to the PH domain of human dynamin, a 100 kDa GTPase that is involved in the initial stages of endocytosis. We describe a rapid method for screening PH domain/ligand interactions that gives precise binding constants. We confirm that PtdIns(4,5)P2can bind to dynamin PH domain, although not in an aggregated state. Using NMR spectroscopy, we have mapped a specific site on the surface of dynamin PH domain of which binding of gIns(1,4,5)P3(the head-group skeleton of PtdIns(4,5)P2) occurs. The relative affinity of acidic phospholipids for dynamin PH domain correlates with their ability to activate the GTPase of dynamin. We propose, therefore, that the interaction of these phospholipids with dynamin is likely to occurviathe PH domain. Given the fact that PH domains are often found in pro- teins associated with GTPase activity, or in guanine nucleotide exchange factors, we suggest that one role of PH domains may be to couple phosphatidylinositol signalling to GTP hydrolysis.
Keywords: Fluorescence; ligand binding; NMR; PH domain; phospholipid

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)

Interaction between 3D Shape and Motion: Theory and Applications - Fermüller, Cornelia; Aloimonos, J.; Cheong,L. (Computer Vision Laboratory, University of Maryland, 1996)
Research during the past few years has attempted to characterize the errors that arise in computing 3D motion (egomotion estimation) and in a scene's structure (structure from motion) from a sequence of images acquired by a moving sensor. This paper presents a new geometric framework that characterizes how the three-dimensional space recovered by a moving monocular observer, whose 3D motion is estimated with some error, is distorted. We characterize the space of distortions by its level sets, that is, by a family of iso-distortion surfaces, each of which describes the locus over which the depths of points in the scene are distorted by the same multiplicative factor. By analyzing the geometry of the regions where the distortion factor is negative, that is, where the visibility constraint is violated, we make explicit situations which are likely to give rise to ambiguities in motion estimation. We also apply our approach to a uniqueness analysis for 3D motion analysis from normal flow; we study the constraints on egomotion, object motion and depth for an independently moving object to be detectable by a moving observer; and we offer a quantitative account of the precision needed in an inertial sensor for accurate estimation of 3D motion.

Modeling and verifying distributed systems using priorities: A case study - Cleaveland, Rance; Natarajan,V.; Sims,S.; Luettgen,G. (Software - Concepts and Tools, 1996)

The NCSU concurrency workbench - Cleaveland, Rance; Sims,S. (Computer Aided Verification, 1996)

Predictability of real-time systems: a process-algebraic approach - Natarajan,V.; Cleaveland, Rance (Real-Time Systems Symposium, IEEE International, 1996)
This paper presents a testing-based semantic preorder that relates real-time systems given in the process description language TPL on the basis of the predictability of their timing behavior. This predictability is measured in terms of the amount of variability present in processes' "activity-completion times". The semantic preorder is shown to coincide with an already existing, well-investigated implementation relation for TPL-the must-preorder. The optimality of our relation is also established by means of a full abstraction result. An example is provided to illustrate the utility of this work.
Keywords: process algebra; real time systems predictability; process algebra; testing-based semantic preorder; process description language; tpl; timing behavior; variability; activity-completion times; semantic preorder; must-preorder; optimality

Priorities for modeling and verifying distributed systems - Cleaveland, Rance; L\üttgen,G.; Natarajan,V.; Sims,S. (Tools and Algorithms for the Construction and Analysis of Systems, 1996)

A process algebra with distributed priorities - Cleaveland, Rance; L\üttgen,G.; Natarajan,V. (CONCUR'96: Concurrency Theory, 1996)

Semantic theories and system design - Cleaveland, Rance (ACM Computing Surveys (CSUR), 1996)

Simplification envelopes - Cohen,Jonathan; Varshney, Amitabh; Manocha,Dinesh; Turk,Greg; Weber,Hans; Agarwal,Pankaj; Brooks,Frederick; Wright,William (Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 1996)
Keywords: geometric modeling; hierarchical approximation; levels-of-detail generation; model simplification; offsets; shape approximation

Spatiotemporal representations for visual navigation - LoongFah Cheong; Fermüller, Cornelia; Aloimonos, J. (Computer Vision — ECCV '96Computer Vision — ECCV '96, 1996)
The study of visual navigation problems requires the integration of visual processes with motor control. Most essential in approaching this integration is the study of appropriate spatio-temporal representations which the system computes from the imagery and which serve as interfaces to all motor activities. Since representations resulting from exact quantitative reconstruction have turned out to be very hard to obtain, we argue here for the necessity of representations which can be computed easily, reliably and in real time and which recover only the information about the 3D world which is really needed in order to solve the navigational problems at hand. In this paper we introduce a number of such representations capturing aspects of 3D motion and scene structure which are used for the solution of navigational problems implemented in visual servo systems. In particular, the following three problems are addressed: (a) to change the robot's direction of motion towards a fixed direction, (b) to pursue a moving target while keeping a certain distance from the target, and (c) to follow a wall-like perimeter. The importance of the introduced representations lies in the following: – They can be extracted using minimal visual information, in particular the sign of flow measurements or the the first order spatiotemporal derivatives of the image intensity function. In that sense they are direct representations needing no intermediate level of computation such as correspondence. – They are global in the sense that they represent how three-dimensional information is globally encoded in them. Thus, they are robust representations since local errors do not affect them. – Usually, from sequences of images, three-dimensional quantities such as motion and shape are computed and used as input to control processes. The representations discussed here are given directly as input to the control procedures, thus resulting in a real time solution.

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

Verification of an active control system using temporal process algebra - Elseaidy,W. M; Baugh,J. W.; Cleaveland, Rance (Engineering with computers, 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)

3D motion representations in visual servo control - Fermüller, Cornelia; LoongFah Cheong; Aloimonos, J. (Proceedings of International Symposium on Computer Vision, 1995, 1995)
A new approach to visual servoing and vision-guided robotics is introduced. This approach uses visual information for autonomous behavior. It amounts to using robust, global spatiotemporal representations easily extracted from the dynamic imagery. Specifically, the geometrical patterns of normal flows are used as the input to the servo mechanism. It is shown that the positions of these patterns are related to the three dimensional motion parameters. By locating the positions of these patterns, we can solve a variety of navigational problems with little computational effort
Keywords: 3D motion representations; autonomous behavior; CAMERAS; computational effort; Computer vision; dynamic imagery; global spatiotemporal representations; image representation; Mobile robots; motion control; Navigation; navigational problems; Optical computing; Robot kinematics; Robot sensing systems; robot vision; Robot vision systems; Robotics and automation; servomechanisms; Servosystems; Spatiotemporal phenomena; vision-guided robotics; visual information; visual servo control; visual servoing

Divergence and fair testing - Natarajan,V.; Cleaveland, Rance (Automata, Languages and Programming, 1995)

Efficient on-the-fly model checking for CTL - Bhat,G.; Cleaveland, Rance; Grumberg,O. (, Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. LICS '95. Proceedings, 1995)
This paper gives an on-the-fly algorithm for determining whether a finite-state system satisfies a formula in the temporal logic CTL. The time complexity of our algorithm matches that of the best existing “global algorithm” for model checking in this logic, and it performs as well as the best known global algorithms for the sublogics CTL and LTL. In contrast with these approaches, however, our routine constructs the state space of the system under consideration in a need-driven fashion and will therefore perform better in practice
Keywords: Algorithm design and analysis; Automata; computational complexity; Computer science; CTL; Encoding; finite automata; finite-state system; global algorithm; Logic; LTL; on-the-fly model checking; Performance analysis; Safety; State-space methods; sublogic; temporal logic; time complexity

Evaluating Spatial and Textual Style of Displays - Shneiderman, Ben; Chimera,Richard; Jog,Ninog; Stimart,Ren; White,David (Institute for Systems Research Technical Reports, 1995)
The next generation of Graphic User Interfaces (GUIs) will offer rapid access to perceptually-rich, information abundant, and cognitively consistent interfaces. These new GUIs will be subjected to usability tests and expert reviews, plus new analysis methods and novel metrics to help guide designers. We have developed and tested first generation concordance tools to help developers to review terminology, capitalization, and abbreviation. We have also developed a dialog box summary table to help developers spot patterns and identify possible inconsistencies in layout, color fonts, font size, font style, and ordering of widgets. In this study we also explored the use of metrics such as widget counts, balance, alignment, density, and aspect ratios to provide further clues about where redesigns might be appropriate. Preliminary experience with several commercial projects is encouraging.
Keywords: human-computer interaction, Systems Integration Methodology

A front-end generator for verification tools - Cleaveland, Rance; Madelaine,E.; Sims,S. (Tools and Algorithms for the Construction and Analysis of Systems, 1995)

Generating diagnostic information for behavioral preorders - Celikkan,U.; Cleaveland, Rance (Distributed computing, 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.

Human-Computer Interaction Laboratory 1995 Video Reports - Plaisant, Catherine; Morrison,S.; Skokowski,C.; Reesch,J.; Shneiderman, Ben; Laboratory,University of Maryland at College Park. Human/Computer Interaction; Channel,F. (University of Maryland at College Park, Human/Computer Interaction Laboratory, 1995)

Image-browser taxonomy and guidelines for designers - Plaisant, Catherine; Carr,D.; Shneiderman, Ben (IEEE Software, 1995)
In many applications users must browse large images. Most designers merely use two one-dimensional scroll bars or ad hoc designs for two-dimensional scroll bars. However, the complexity of two-dimensional browsing suggests that more careful analysis, design, and evaluation might lead to significant improvements. Our exploration of existing 2D browsers has led us to identify many features and a wide variety of tasks performed with the browsers. We introduce an informal specification technique to describe 2D browsers and a task taxonomy, suggest design features and guidelines, and assess existing strategies. We focus on the tools to explore a selected image and so do not cover techniques to browse a series of images or to browse large-image databases
Keywords: analysis; Computer Graphics; design; designer guidelines; Equations; Europe; Evaluation; Formal specifications; Graphical user interfaces; Guidelines; IMAGE PROCESSING; image-browser taxonomy; informal specification technique; Laboratories; large image browsing; Layout; Road transportation; selected image exploration; SHAPE; Software design; task taxonomy; Taxonomy; tools; two-dimensional browsing; user interface management systems; visual databases

Interoperable query processing from object to relational schemas based on a parameterized canonical representation - Raschid, Louiqa; Chang,Y. (Int. J. Cooperative Inf. Syst., 1995)

Iso-distortion contours and egomotion estimation - LoongFah Cheong; Aloimonos, J. (Proceedings of International Symposium on Computer Vision, 1995, 1995)
This paper introduces the framework of iso-distortion contour to deal with the problem of depth distortion due to erroneous motion estimates, and various related aspects such as the effectiveness of the visibility constraint. The framework can also be used to inquire the uniqueness aspect of normal flow. Future work will examine the implications of the iso-distortion contours for the problem of multiple frame integration
Keywords: Automation; Computer vision; Degradation; depth distortion; Educational institutions; egomotion estimation; Equations; erroneous motion estimates; Error analysis; HUMANS; Image sequences; iso-distortion contours; Laboratories; Layout; Motion estimation; Robustness; visibility constraint

Land cover dynamics investigation using parallel computers - Liang, S.; Davis, Larry S.; Townshend,J.; Chellapa, Rama; DeFries, R.; Dubayah, R.; Goward,S.; JaJa, Joseph F.; Krishnamachar, S.; Roussopoulos, Nick; Saltz, J.; Samet, Hanan; et al. (Geoscience and Remote Sensing Symposium, 1995. IGARSS '95. 'Quantitative Remote Sensing for Science and Applications', International, 1995)
A comprehensive and highly interdisciplinary research program is being carried out to investigate global land cover dynamics in heterogeneous parallel computing environments. Some of the problems are addressed including atmospheric correction, mixture modeling, image classifications by Markovian random fields and by segmentation, global image/map databases, object oriented parallel programming and parallel/IO. During the initial two years project, significant progress has been made in all of these areas
Keywords: geographic information system; geophysical measurement technique; geophysics computing; image classification; image map database; image segmentation; land cover dynamics; land surface; mixture modeling; object oriented programming; optical imaging; para; GIS; IR imaging; Markovian random fields; atmospheric correction

Optimality in abstractions of model checking - Cleaveland, Rance; Iyer,P.; Yankelevich,D. (Static Analysis, 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

Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems - Chari,Suresh; Rohatgi,Pankaj; Srinivasan, Aravind (SIAM Journal on Computing, 1995)
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the $RNC$ algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105–113] and in several other applications. Given a set $S$ and an unknown family $\mathcal{F} \subseteq 2^{S}$ with $|\mathcal{F}| ≤ Z$, we present a scheme for assigning polynomially bounded weights to the elements of $S$ using only $O(\log Z + \log |S|)$ random bits, such that the minimum weight set in $\mathcal{F}$ is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use $O(S \log S)$ bits, independent of $Z$. We also provide a matching lower bound for the randomness complexity of this problem. The new weight assignment scheme yields a randomness-efficient $RNC^{2}$ algorithm for perfect matching which uses $O(\log Z + \log n)$ random bits, where $Z$ is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpinski [Proc. IEEE Symposium on Foundations of computer Science, 1987, pp. 166–172], who presentan $NC^{3}$ algorithm when $Z$ is polynomial and improves the running time in this case. The worst-case randomness complexity of our algorithm is $O(n \log (m/n))$ random bits improving on the previous bound of $O(m \log n)$. Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as $RNC$ algorithms for variants of matching and basic problems on linear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few $P$ to yield new proofs of the results Few $P \subseteq \oplus P$ and Few $P \subseteq C_{=} P$.

Sampling properties of DNA sequence data in phylogenetic analysis - Cummings, Michael P.; Otto,S. P; Wakeley,J. (Mol Biol Evol, 1995)
We inferred phylogenetic trees from individual genes and random samples of nucleotides from the mitochondrial genomes of 10 vertebrates and compared the results to those obtained by analyzing the whole genomes. Individual genes are poor samples in that they infrequently lead to the whole-genome tree. A large number of nucleotide sites is needed to exactly determine the whole-genome tree. A relatively small number of sites, however, often results in a tree close to the whole-genome tree. We found that blocks of contiguous sites were less likely to lead to the whole-genome tree than samples composed of sites drawn individually from throughout the genome. Samples of contiguous sites are not representative of the entire genome, a condition that violates a basic assumption of the bootstrap method as it is applied in phylogenetic studies.

Scalable data parallel algorithms for texture synthesis using Gibbs random fields - Bader, D.A.; JaJa, Joseph F.; Chellapa, Rama (Image Processing, IEEE Transactions on, 1995)
This article introduces scalable data parallel algorithms for image processing. Focusing on Gibbs and Markov random field model representation for textures, we present parallel algorithms for texture synthesis, compression, and maximum likelihood parameter estimation, currently implemented on Thinking Machines CM-2 and CM-5. The use of fine-grained, data parallel processing techniques yields real-time algorithms for texture synthesis and compression that are substantially faster than the previously known sequential implementations. Although current implementations are on Connection Machines, the methodology presented enables machine-independent scalable algorithms for a number of problems in image processing and analysis
Keywords: algorithms; maximum; algorithms; parallel; algorithms; scalable; algorithms; texture; analysis; image; CM-2; Thinking; CM-5; fine-grained; compression; image; compression; texture; Connection; data; estimation; model; estimation; parallel; field; Thinking; fields; Markov; likelihood; machine; Machines; Gibbs; machines; random; Parallel; parameter; processes; processes; data; processing; image; processing; machine-independent; random; representation; real-time; scalable; synthesis; Markov; texture; maximum

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)

An Atlas of Drosophila Genes: Sequences and Molecular Features - Maroni,G.; Mount, Stephen M.; Cavener,DR; Cavener,BA; Sharp,PM; Lloyd,AT; Schaeffer,SW (Journal of Heredity, 1994)

On the detection of robust curves - Cole,R.; Vishkin, Uzi (CVGIP: Graphical Models and Image Processing, 1994)

Document page decomposition by integration of distributed soft decisions - Etemad,K.; David Doermann; Chellapa, Rama (International Conference on Neural Networks, 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

An exploratory evaluation of three interfaces for browsing large hierarchical tables of contents - Chimera,Richard; Shneiderman, Ben (ACM Trans. Inf. Syst., 1994)
Three different interfaces were used to browse a large (1296 items) table of contents. A fully expanded stable interface, expand/contract interface, and multipane interface were studied in a between-groups experiment with 41 novice participants. Nine timed fact retrieval tasks were performed; each task is analyzed and discussed separately. We found that both the expand/contract and multipane interfaces produced significantly faster times than the stable interface for many tasks using this large hierarchy; other advantages of the expand/contract and multipane interfaces over the stable interface are discussed. The animation characteristics of the expand/contract interface appear to play a major role. Refinements to the multipane and expand/contract interfaces are suggested. A predictive model for measuring navigation effort of each interface is presented.
Keywords: Browsing; hierarchies; table of contents; User interfaces

An extended cellular space method for simulating autocatalytic oligonucleotides - Chou,H. H.; Reggia, James A.; Navarro-Gonzalez,R.; Wu,J. (Computers & chemistry, 1994)

Finding structurally consistent motion correspondences - Jacobs, David W.; Chennubhotla,C. (Pattern Recognition, 1994. Vol. 1 - Conference A: Computer Vision Image Processing., Proceedings of the 12th IAPR International Conference on, 1994)
Much work on deriving scene structure and motion from features assumes as input a set of tracked image features that share a common 3D motion. Producing this input requires segmenting independent motions, and detecting image features that do not correspond to 3D features, originating instead, for example in occlusion boundaries or specularities. We derive a linear program that tells when a set of tracked points might have come from 3D points that share a single motion, assuming affine motion and bounded error. We can also use linear programming to place conservative bounds on the structure of the scene that corresponds to tracked points. We implement and test this algorithm on real images
Keywords: 3D; boundaries; common; consistent; correspondences; estimation; features; image; independent; linear; MOTION; motion; occlusion; programming; scene; segmentation; specularities; structurally; structure; tracked

Fully abstract characterizations of testing preorders for probabilistic processes - Yuen,S.; Cleaveland, Rance; Dayar,Z.; Smolka,S. (CONCUR'94: Concurrency Theory, 1994)

High performance computing for land cover dynamics - Parulekar,R.; Davis, Larry S.; Chellapa, Rama; Saltz, J.; Sussman, Alan; Townshend,J. (Pattern Recognition, 1994. Vol. 3-Conference C: Signal Processing, Proceedings of the 12th IAPR International Conference on, 1994)

Image Browsers: Taxonomy, Guidelines, and Informal Specifications - Plaisant, Catherine; Carr,David A; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1994)
Image browsing is necessary in numerous applications. Designers have merely used two one-dimensional scroll bars or they have made ad hoc designs for a two-dimensional scroll bar. However, the complexity of two-dimensional browsing suggests that more careful analysis, design, and evaluation might lead to significant improvements. We present a task taxonomy for image browsing, suggest design features and guidelines, assess existing strategies, and introduce an informal specification
Keywords: Graphics; Systems Integration; use interface

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)

Map formation in proprioceptive cortex. - Cho,S.; Reggia, James A. (International journal of neural systems, 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)

Modeling brain adaptation to focal damage. - Goodall,S.; Reggia, James A.; Cho,S. (Proceedings of the Annual Symposium on Computer Application in Medical Care, 1994)

An operational framework for value-passing processes - Cleaveland, Rance; Yankelevich,Daniel (Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1994)
This paper develops a semantic framework for concurrent languages with value passing. An operation analogous to substitution in the &lgr;-calculus is given, and a semantics is given for a value-passing version of Milner's Calculus of Communicating Systems (CCS). An operational equivalence is then defined and shown to coincide with Milner's (early) bisimulation equivalence. We also show how semantics maybe given for languages with asynchronous communication primitives. In contrast with existing approaches to value passing, this semantics does not reduce data exchange to pure synchronization over (potentially infinite) families of ports indexed by data, and it avoids variable renamings that are not local to processes engaged in communication.

Page Segmentation Using Decision Integration and Wavelet Packet Basis - Etemad,K.; David Doermann; Chellapa, Rama (ICPR, 1994)

On a parallel-algorithms method for string matching problems (overview) - Sahinalp,Suleyman; Vishkin, Uzi (Algorithms and ComplexityAlgorithms and Complexity, 1994)
Keywords: Computer; Science

Query transformation techniques for interoperable query processing in cooperative information systems - Raschid, Louiqa; Chang,Y.; Dorr, Bonnie J (Proceedings of the Second International Conference on Cooperative Information Systems (CoopIS94), May, 1994)

Segmenting independently moving, noisy points - Jacobs, David W.; Chennubhotla,C. (Motion of Non-Rigid and Articulated Objects, 1994., Proceedings of the 1994 IEEE Workshop on, 1994)
There has been much work on using point features tracked through a video sequence to determine structure and motion. In many situations, to use this work, we must first isolate subsets of points that share a common motion. This is hard because we must distinguish between independent motions and apparent deviations from a single motion due to noise. We propose several methods of searching for point-sets with consistent 3D motions. We analyze the potential sensitivity of each method for detecting independent motions, and experiment with each method on a real image sequence
Keywords: 3D; common; consistent; estimation; features; image; independently; linear; MOTION; motion; moving; noisy; point; points; programming; real; segmentation; sequence; sequences; video