An efficient k-means clustering algorithm: analysis and implementation - Kanungo,T.; Mount, Dave; Netanyahu,N. S; Piatko,C. D; Silverman,R.; Wu,A. Y (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002)
In k-means clustering, we are given a set of n data points in d-dimensional space Rd and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation
Keywords: algorithm; color; algorithm; image; algorithm; kd-tree; mean; analysis; filtering; clustering; clustering; compression; data; distance; covariance; Lloyd; matrices; filtering; quantization; data; segmentation; k-means; squared; structure; data-sensitive; theory; pattern

Evolution in Action: Using Active Networking to Evolve Network Support for Mobility - Seong-Kyu,Song; Shannon,Stephen; Hicks, Michael W.; Nettles,Scott (Active NetworksActive Networks, 2002)
A key early objective of Active Networking (AN) was to support on-the-fly network evolution. Although AN has been used relatively extensively to build application-customized protocols and even whole networking systems, demonstrations of evolution have been limited. This paper examines three AN mechanisms and how they enable evolution: active packets and plug-in extensions, well-known to the AN community, and update extensions, which are novel to AN. We devote our presentation to a series of demonstrations of how each type of evolution can be applied to the problem of adding support for mobility to a network. This represents the most large-scale demonstration of AN evolution to date. These demonstrations show what previous AN research has not: that AN technology can, in fact, support very significant changes to the network, even while the network is operational.

Experimental Construction of Very Large Scale DNA Databases with Associative Search - Reif,J. H; LaBean,T. H; Pirrung,M.; Rana,V. S; Guo,B.; Kingsford, Carl; Wickham,G. S (DNA computing: 7th International Workshop on DNA-Based Computers, DNA 7, Tampa, FL, USA, June 10-13, 2001: revised papers, 2002)

An experimental evaluation of linear and kernel-based methods for face recognition - Gupta, H.; Agrawala, Ashok K.; Pruthi, T.; Shekhar, C.; Chellapa, Rama (Applications of Computer Vision, 2002. (WACV 2002). Proceedings. Sixth IEEE Workshop on, 2002)
In this paper we present the results of a comparative study of linear and kernel-based methods for face recognition. The methods used for dimensionality reduction are Principal Component Analysis (PCA), Kernel Principal Component Analysis (KPCA), Linear Discriminant Analysis (LDA) and Kernel Discriminant Analysis (KDA). The methods used for classification are Nearest Neighbor (NN) and Support Vector Machine (SVM). In addition, these classification methods are applied on raw images to gauge the performance of these dimensionality reduction techniques. All experiments have been performed on images from UMIST Face Database.
Keywords: analysis; classification; component; discriminant; Face; image; Kernel; linear; Machine; nearest; neighbor; principal; recognition; Support; vector

Extracting articulation models from CAD models of parts with curved surfaces - Sinha,R.; Gupta,S.K.; Paredis,C. J. J.; Khosla,P. K. (TRANSACTIONS-AMERICAN SOCIETY OF MECHANICAL ENGINEERS JOURNAL OF MECHANICAL DESIGN, 2002)
Degrees of freedom in an assembly are realized by creating mating features that permit relativemotion between parts. In complex assemblies, interactions between individual degrees of freedom may result in a behavior different from the intended behavior. In addition, current methods perform assembly reasoning by approximating curved surfaces as piecewise linear surfaces. Therefore, it is important to be able to: reason about assemblies using exact representations of curved surfaces; verify global motion behavior of parts in the assembly; and create motion simulations of the assembly by examination of the geometry. In this paper, we present a linear algebraic constraint method to automatically construct the space of allowed instantaneous motions of an assembly from the geometry of its constituent parts. Our work builds on previous work on linear contact mechanics and on our previous work on curved surface contact mechanics. We enumerate the conditions under which general curved surfaces can be represented using a finite number of constraints linear in the instantaneous velocities. We compose such constraints to build a space of allowed instantaneous velocities for the assembly. The space is then described as a set-theoretic sum of contact-preserving and contact-breaking motion sub-spaces. Analysis of each subspace provides feedback to the designer, which we demonstrate through the use of an example assembly – a 4-part arm. Finally, the results of the analysis of a 4-bar linkage are compared to those from mechanism theory.

Fulfilling the promise of marine biotechnology - Rita R Colwell (Marine biotechnology in the twenty-first century: problems, promise, and productsMarine biotechnology in the twenty-first century: problems, promise, and products, 2002)

Generating 3D Models of MEMS Devices by Process Emulation - Bellam,S.; Gupta, Satyandra K.; Priyadarshi,A. K. (Institute for Systems Research, University of Maryland, College Park, 2002)
MEMS designers often use numerical simulation for detecting errors in the mask layout. Numerical simulation involves generating 3D models of MEMS device from the mask layout and process description. The generated models can be meshed and simulated over different domains. This report describes an efficient algorithm that can generate 3D geometric models of MEMS devices. Specifically, the algorithm emulates the manufacturing of a single functional polysilicon layer MEMS devices using the MUMPSprocess.
Keywords: Next-Generation Product Realization Systems

Genome sequence and comparative analysis of the model rodent malaria parasite Plasmodium yoelii yoelii - Carlton,Jane M.; Angiuoli,Samuel V; Suh,Bernard B.; Kooij,Taco W.; Pertea,Mihaela; Silva,Joana C.; Ermolaeva,Maria D.; Allen,Jonathan E; Jeremy D Selengut; Koo,Hean L.; Peterson,Jeremy D.; Pop, Mihai; et al. (Nature, 2002)
Species of malaria parasite that infect rodents have long been used as models for malaria disease research. Here we report the whole-genome shotgun sequence of one species, Plasmodium yoelii yoelii, and comparative studies with the genome of the human malaria parasite Plasmodium falciparum clone 3D7. A synteny map of 2,212 P. y. yoelii contiguous DNA sequences (contigs) aligned to 14 P. falciparum chromosomes reveals marked conservation of gene synteny within the body of each chromosome. Of about 5,300 P. falciparum genes, more than 3,300 P. y. yoelii orthologues of predominantly metabolic function were identified. Over 800 copies of a variant antigen gene located in subtelomeric regions were found. This is the first genome sequence of a model eukaryotic parasite, and it provides insight into the use of such systems in the modelling of Plasmodium biology and disease.

Genome Sequence Assembly: Algorithms and Issues - Pop, Mihai; Salzberg,Steven L.; Shumway,Martin (Computer, 2002)
Ultimately, genome sequencing seeks to provide an organism's complete DNA sequence. Automation of DNA sequencing allowed scientists to decode entire genomes and gave birth to genomics, the analytic and comparative study of genomes. Although genomes can include billions of nucleotides, the chemical reactions researchers use to decode the DNA are accurate for only about 600 to 700 nucleotides at a time.The DNA reads that sequencing produces must then be assembled into a complete picture of the genome. Errors and certain DNA characteristics complicate assembly. Resolving these problemsentails an additional and costly finishing phase that involves extensive human intervention. Assembly programs can dramatically reduce this cost by taking into account additional informationobtained during finishing. Algorithms that can assemble millions of DNA fragments into gene sequences underlie the current revolution in biotechnology, helping researchers build the growingdatabase of complete genomes.

A history-based test prioritization technique for regression testing in resource constrained environments - Kim,Jung-Min; Porter, Adam (Proceedings of the 24th international conference on Software engineering - ICSE '02, 2002)

Improved Word-Level Alignment: Injecting Knowledge about MT Divergences - Dorr, Bonnie J; Pearl,Lisa; Hwa,Rebecca; Habash,Nizar (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
Word-level alignments of bilingual text (bitexts) are not an integral part of statistical machine translation models, but also useful for lexical acquisition, treebank construction. and part-of-speech tagging. The frequent occurrence of divergences, structural differences between languages, presents a great challenge to the alignment task. We resolve some of the most prevalent divergence cases by using syntactic parse information to transform the sentence structure of one language to bear a closer resemblance to that of the other language. In this paper, we show that common divergence types can be found in multiple language pairs (in particular, we focus on English-Spanish and English-Arabic) and systematically identified. We describe our techniques for modifying English parse trees to form resulting sentences that share more similarity with the sentences in the other languages; finally, we present an empirical analysis comparing the complexities of performing word-level alignments with an without divergence handling. Our results suggest that divergence-handling can improve word-level alignment.
Keywords: *LEXICOGRAPHY; *MACHINE TRANSLATION; *STATISTICAL ANALYSIS; *WORDS(LANGUAGE); ACQUISITION; ALIGNMENT; EXPERIMENTAL DATA; LANGUAGE; linguistics; MATHEMATICAL MODELS; STATISTICS AND PROBABILITY; TREES

In vitro adhesion to human cells by viable but nonculturable Enterococcus faecalis - Pruzzo,C.; Tarsi,R.; Lleò,M. M.; Signoretto,C.; Zampini,M.; Rita R Colwell; Canepari,P. (Current microbiology, 2002)
The ability of viable but nonculturable (VBNC) Enterococcus faecalis to adhere to Caco-2 and Girardi heart cultured cells and to urinary tract epithelial cells (ECs) was studied. Enterococci were harvested during the vegetative growth phase (early exponential and stationary), in the VBNC state, and after recovery of the ability to divide. VBNC bacteria maintained their adherence capability but the efficiency of attachment was reduced by about 50 to 70%, depending on the target cell employed. The decrease was transient, since enterococci that regained their culturability showed adherence values similar to those observed for actively growing cells. Analysis of the invasive properties of E. faecalis revealed that the VBNC state caused a decrease in the number of bacteria that entered the cultured HEK cells as a result of the reduction in the number of adhering bacteria. These results highlight the importance of studies of the VBNC phenomenon, with respect to both microbial survival in the environment and the impact on human health.

Interacting with identification technology: can it make us more secure? - Scholtz,Jean; Johnson,Jeff; Shneiderman, Ben; Hope-Tindall,Peter; Gosling,Marcus; Phillips,Jonathon; Wexelblat,Alan (CHI '02 extended abstracts on Human factors in computing systems, 2002)
Keywords: Biometrics; civil liberties; face recognition; national id card; privacy; Security

Interactive information visualization of a million items - Fekete,J.-D.; Plaisant, Catherine (Information Visualization, 2002. INFOVIS 2002. IEEE Symposium on, 2002)
Existing information visualization techniques are usually limited to the display of a few thousand items. This article describes new interactive techniques capable of handling a million items (effectively visible and manageable on screen). We evaluate the use of hardware-based techniques available with newer graphics cards, as well as new animation techniques and non-standard graphical features such as stereovision and overlap count. These techniques have been applied to two popular information visualizations: treemaps and scatter plot diagrams; but are generic enough to be applied to other 2D representations as well.
Keywords: animation; animation; cards; Computer; count; data; diagrams; Graphics; hardware-based; information; interactive; interpolation; overlap; plot; scatter; stereovision; systems; techniques; treemaps; visualisation; visualization

Lessons learned from 25 years of process improvement: the rise and fall of the NASA software engineering laboratory - Basili, Victor R.; McGarry,Frank E.; Pajerski,Rose; Zelkowitz, Marvin V (Proceedings of the 24th International Conference on Software Engineering, 2002)
For 25 years the NASA/GSFC Software Engineering Laboratory (SEL) has been a major resource in software process improvement activities. But due to a changing climate at NASA, agency reorganization, and budget cuts, the SEL has lost much of its impact. In this paper we describe the history of the SEL and give some lessons learned on what we did right, what we did wrong, and what others can learn from our experiences. We briefly describe the research that was conducted by the SEL, describe how we evolved our understanding of software process improvement, and provide a set of lessons learned and hypotheses that should enable future groups to learn from and improve on our quarter century of experiences.

A local search approximation algorithm for k-means clustering - Kanungo,Tapas; Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine D.; Silverman,Ruth; Wu,Angela Y. (Proceedings of the eighteenth annual symposium on Computational geometry, 2002)
In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in ÓC;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+&egr;)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-&egr;). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.
Keywords: Approximation algorithms; clustering; computational geometry; k-means; local search

Metareasoning for More Effective Human-Computer Dialogue - Perlis, Don; Anderson,Mike (University of Maryland, College Park, 2002)
The research project explores specific meta-dialogue behaviors in terms of both how a system could be made to perform them, and to what extent they can increase overall system performance. We focus on two types of meta-dialogue capabilities: ability to detect and recover from anomalous dialogue patterns in simple exchanges, and on-line extensions or changes to working vocabulary. Our main method involves detailed representation of the dialogue context, separating domain, language, and dialogue specific aspects, and significant amounts of meta-reasoning about the system's processing of these representations. An existing logical inference system, ALMA/CARNE, developed as part of a pilot study, is being used in an implementation phase of this work. We are also engaged in a study of existing dialogue corpora to investigate the range and frequency of meta-dialogue expressions in different task domains.
Keywords: *LEARNING MACHINES; COMPUTER LOGIC; COMPUTER PROGRAMMING AND SOFTWARE; CYBERNETICS; MAN COMPUTER INTERFACE; METAREASONING; NATURAL LANGUAGE.; PROCESSING

Method and apparatus for learning probabilistic relational models having attribute and link uncertainty and for performing selectivity estimation using probabilistic relational models - Koller,Daphne; Getoor, Lise; Pfeffer,Avi; Friedman,Nir; Taskar,Ben (2002)
The invention comprises a method and apparatus for learning probabilistic models (PRM's) with attribute uncertainty. A PRM with attribute uncertainty defines a probability distribution over instantiations of a database. A learned PRM is useful for discovering interesting patterns and dependencies in the data. Unlike many existing techniques, the process is data-driven rather than hypothesis driven. This makes the technique particularly well-suited for exploratory data analysis. In addition, the invention comprises a method and apparatus for handling link uncertainty in PRM's. Link uncertainty is uncertainty over which entities are related in our domain. The invention comprises of two mechanisms for modeling link uncertainty: reference uncertainty and existence uncertainty. The invention includes learning algorithms for each form of link uncertainty. The third component of the invention is a technique for performing database selectivity estimation using probabilistic relational...

Modeling the Effects of Greenbelts at the Urban-Rural Fringe - Brown,D.G.; Page,S.E.; Riolo,R; Rand, William (Proceedings of IEMSS 2002, 2002)
We present and evaluate an agent based model (ABM) of land use change at the rural-urban fringe,comparing its performance to a mathematical model of the same process. Our simplified model was developed in Swarm using agents with heterogeneous preferences and a landscape with heterogeneous properties. The context of this work is a larger project that includes surveys of the preferences of residents and data on historical patterns of development. Our broader goal is to use the model to evaluate the ecological effects of alternative policies and designs. We begin by evaluating the influence of a greenbelt, which is located next to a developing area and in which no development is permitted. We present results of a mathematical model that illustrates the necessary trade-off between greenbelt placement and greenbelt width on its effectiveness at delaying develop- ment beyond. Experiments run with the ABM are validated by the mathematical model and illustrate analyses that can be performed by extending to two-dimensions, variable agent preferences, and multiple, and ultimately realistic, patterns of landscape variability.

Navigation patterns and usability of zoomable user interfaces with and without an overview - Hornbaek,K.; Bederson, Benjamin B.; Plaisant, Catherine (ACM Transactions on Computer-Human Interaction (TOCHI), 2002)

Non-manifold decomposition in arbitrary dimensions - De Floriani, Leila; Mesmoudi,M.; Morando,F.; Puppo,E. (Discrete Geometry for Computer Imagery, 2002)
In this paper we consider the problem of decomposing a nonmanifold n-dimensional object described by an abstract simplicial complex into an assembly of ‘more-regular’ components. Manifolds, which would be natural candidates for components, cannot be used to this aim in high dimensions because they are not decidable sets. Therefore, we define d-quasi-manifolds, a decidable superset of the class of combinatorial d-manifolds that coincides with d-manifolds in dimension less or equal than two. We first introduce the notion of d-quasi-manifold complexes, then we sketch an algorithm to decompose an arbitrary complex into an assembly of quasi-manifold components abutting at non-manifold joints. This result provides a rigorous starting point for our future work, which includes designing efficient data structures for non-manifold modeling, as well as defining a notion of measure of shape complexity of such models.

Performance evaluation of object detection algorithms - Mariano,V.Y.; Min,Junghye; Park,Jin-Hyeong; Kasturi,R.; Mihalcik,D.; Huiping Li; David Doermann; Drayer,T. (Pattern Recognition, 2002. Proceedings. 16th International Conference on, 2002)
The continuous development of object detection algorithms is ushering in the need for evaluation tools to quantify algorithm performance. In this paper a set of seven metrics are proposed for quantifying different aspects of a detection algorithm's performance. The strengths and weaknesses of these metrics are described. They are implemented in the Video Performance Evaluation Resource (ViPER) system and will be used to evaluate algorithms for detecting text, faces, moving people and vehicles. Results for running two previous text-detection algorithms on a common data set are presented.
Keywords: algorithms; common; data; DETECTION; detection; Evaluation; evaluation; image; object; performance; recognition; resource; set; system; text-detection; video

A photo history of SIGCHI: evolution of design from personal to public - Shneiderman, Ben; Kang,Hyunmo; Kules,Bill; Plaisant, Catherine; Rose,Anne; Rucheir,Richesh (interactions, 2002)
For 20 years I have been photographing personalities and events in the emerging discipline of human--computer interaction. Until now, only a few of these photos were published in newsletters or were shown to visitors who sought them out. Now this photo history is going from a personal record to a public archive. This archive should be interesting for professional members of this community who want to reminisce, as well as for historians and journalists who want to understand what happened. Students and Web surfers may also want to look at the people who created better interfaces and more satisfying user experiences.

Phylogenetic analysis based on 18S ribosomal RNA gene sequences supports the existence of class Polyacanthocephala (Acanthocephala) - García-Varela,M; Cummings, Michael P.; Pérez-Ponce de León,G.; Gardner,S. L; Laclette,J. P (Mol Phylogenet Evol, 2002)
Members of phylum Acanthocephala are parasites of vertebrates and arthropods and are distributed worldwide. The phylum has traditionally been divided into three classes, Archiacanthocephala, Palaeacanthocephala, and Eoacanthocephala; a fourth class, Polyacanthocephala, has been recently proposed. However, erection of this new class, based on morphological characters, has been controversial. We sequenced the near complete 18S rRNA gene of Polyacanthorhynchus caballeroi (Polyacanthocephala) and Rhadinorhynchus sp. (Palaeacanthocephala); these sequences were aligned with another 21 sequences of acanthocephalans representing the three widely recognized classes of the phylum and with 16 sequences from outgroup taxa. Phylogenetic relationships inferred by maximum-likelihood and maximum-parsimony analyses showed Archiacanthocephala as the most basal group within the phylum, whereas classes Polyacanthocephala + Eoacanthocephala formed a monophyletic clade, with Palaeacanthocephala as its sister group. These results are consistent with the view of Polyacanthocephala representing an independent class within Acanthocephala.

Presentation planning for distributed VoD systems - Hwang,Eenjun; Prabhakaran,B.; V.S. Subrahmanian (Knowledge and Data Engineering, IEEE Transactions on, 2002)
A distributed video-on-demand (VoD) system is one where a collection of video data is located at dispersed sites across a computer network. In a single site environment, a local video server retrieves video data from its local storage device. However, in distributed VoD systems, when a customer requests a movie from the local server, the server may need to interact with other servers located across the network. In this paper, we present different types of presentation plans that a local server can construct in order to satisfy a customer request. Informally speaking, a presentation plan is a temporally synchronized sequence of steps that the local server must perform in order to present the requested movie to the customer. This involves obtaining commitments from other video servers, obtaining commitments from the network service provider, as well as making commitments of local resources, while keeping within the limitations of available bandwidth, available buffer, and customer data consumption rates. Furthermore, in order to evaluate the quality of a presentation plan, we introduce two measures of optimality for presentation plans: minimizing wait time for a customer and minimizing access bandwidth which, informally speaking, specifies how much network/disk bandwidth is used. We develop algorithms to compute three different optimal presentation plans that work at a block level, or at a segment level, or with a hybrid mix of the two, and compare their performance through simulation experiments. We have also mathematically proven effects of increased buffer or bandwidth and data replications for presentation plans which had previously been verified experimentally in the literature.
Keywords: Computer; computing; databases; demand; distributed; local; multimedia; network; on; optimal; plan; plans; presentation; presentation; server; servers; video; video-on-demand; VoD

Probabilistic validation of intrusion tolerance - Sanders,W. H.; Michel Cukier; Webber,F.; Pal,P.; Watro,R. (2002)

Quantifying the cost of providing intrusion tolerance in group communication systems - Ramasamy,H. V.; Pandey,P.; Lyons,J.; Michel Cukier; Sanders,W. H. (2002)
Group communication systems that provide consistent group membership and reliable, ordered multicast properties in the presence of faults resulting from malicious intrusions have not been analyzed extensively to quantify the cost of tolerating these intrusions. This paper attempts to quantify this cost by presenting results from an experimental evaluation of three new intrusion-tolerant microprotocols that have been added to an existing crash-fault-tolerant group communication system. The results are analyzed to identify the parts that contribute the most overhead during provision of intrusion tolerance at the group communication system level.
Keywords: consistent group membership; crash-fault-tolerant group communication system; cryptography; finite state machines; groupware; intrusion-tolerant microprotocols; malicious intrusions; multicast communication; reliable ordered multicast properties; security of data; Transport protocols

Quasi-invariants for human action representation and recognition - Parameswaran, V.; Chellapa, Rama (Pattern Recognition, 2002. Proceedings. 16th International Conference on, 2002)
Although human action recognition has been the subject of much research in the past, the issue of viewpoint invariance has received scarce attention. In this paper, we present an approach to detect human action with a high tolerance to viewpoint change. Canonical body poses are modeled in a view invariant manner to enable detection from a general viewpoint. While there exist no invariants for 3D to 2D projection, there exists a wealth of techniques in 2D invariance that can be used to advantage in 3D to 2D projection. We employ 2D invariants to recognize canonical poses of the human body leading to an effective way to represent and recognize human action which we evaluate theoretically and experimentally on 2D projections of publicly available human motion capture data.
Keywords: 2D; action; analysis; body; canonical; change; human; image; invariance; MOTION; poses; quasi-invariants; recognition; representation; tolerance; viewpoint

RECOMB '02: Proceedings of the sixth annual international conference on Computational biology - Myers,Gene; Hannenhalli, Sridhar; Sankoff,David; Istrail,Sorin; Pevzner,Pavel; Waterman,Michael (ACM, 2002)
The papers in this volume were presented at the Sixth Annual International Conference on Computational Biology RECOMB 2002, held in Washington, D.C. on April 18-21, 2002. The RECOMB series was started in 1997 by Sorin Istrail, Pavel Pevzner and Michael Waterman. RECOMB '99 took place in Lyon, France, RECOMB 2000 was held in Tokyo, Japan, and RECOMB 2001 was held in Montreal, Quebec, Canada.This year's call for papers gave rise to 118 submissions, out of which the program committee selected 35 papers to be presented at the conference and included in the proceedings. Each submission was refereed by at least three members of the program committee. After the completion of the referees' reports, an extensive web-based discussion took place.RECOMB 2002 had 8 invited speakers: Ruben Abagyan (The Scripps Research Institute), Ali H. Brivanlou (Rockefeller University), Evan Eichler (Case Western Reserve University), Harold "Skip" Garner (University of Texas Southwestern Medical Center at Dallas), David Ho (Rockefeller University), Gerry Rubin (Howard Hughes Medical Institute), J. Craig Venter (Celera) and Marc Vidal (Dana-Farber Cancer Institute). The Stanislaw Ulam Memorial Lecture was given by J. Craig Venter. The Distinguished Biology Lecture was given by David Ho. The Distinguished New Technologies Lecture was given by Harold Garner.Complete final versions of many of the papers presented in the conference will appear in a special issue of the Journal of Computational Biology, which is closely affiliated with the conference.

SpaceTree: Design evolution of a node link tree browser - Plaisant, Catherine; Grosjean,J.; Bederson, Benjamin B. (Proc. InfoVis, 2002)

SpaceTree: supporting exploration in large node link tree, design evolution and empirical evaluation - Plaisant, Catherine; Grosjean,J.; Bederson, Benjamin B. (Information Visualization, 2002. INFOVIS 2002. IEEE Symposium on, 2002)
We present a novel tree browser that builds on the conventional node link tree diagrams. It adds dynamic rescaling of branches of the tree to best fit the available screen space, optimized camera movement, and the use of preview icons summarizing the topology of the branches that cannot be expanded. In addition, it includes integrated search and filter functions. This paper reflects on the evolution of the design and highlights the principles that emerged from it. A controlled experiment showed benefits for navigation to already previously visited nodes and estimation of overall tree topology.
Keywords: browser; camera; data; design; diagrams; dynamic; evolution; experiment; exploration; filter; functions; graphical; icons; integrated; interfaces; large; link; movement; node; novel; optimized; rescaling; search; SpaceTree; structures; topology; tree; user; visualisation; visualization

Structural Properties of Polyubiquitin Chains in Solution - Varadan,Ranjani; Walker,Olivier; Pickart,Cecile; Fushman, David (Journal of Molecular Biology, 2002)
Because polyubiquitin chain structure modulates Ub-mediated signaling, knowledge of the physiological conformations of chain signals should provide insights into specific recognition. Here, we characterized the solution conformations of K48-linked Ub2 and Ub4 using a combination of NMR techniques, including chemical shift mapping of the interdomain interface, domain orientation measurements on the basis of 15N relaxation and residual dipolar couplings, and the solvent accessibility studies. Our data indicate a switch in the conformation of Ub2, from open to closed, with increasing pH. The closed conformation features a well-defined interface that is related to, but distinguishable from, that observed in the Ub2 crystal structure. This interface is dynamic in solution, such that important hydrophobic residues (L8, I44, V70) that are sequestered at the interface in the closed conformation may be accessible for direct interactions with recognition factors. Our results suggest that the distal two units of Ub4, which is the minimum signal for efficient proteasomal degradation, may adopt the closed Ub2 conformation.
Keywords: chemical shift mapping; domain orientation measurements; polyubiquitin chains; spin relaxation; ubiquitin

Supporting access to large digital oral history archives - Gustman,Samuel; Soergel,Dagobert; Oard, Douglas; Byrne,William; Picheny,Michael; Ramabhadran,Bhuvana; Greenberg,Douglas (Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, 2002)
This paper describes our experience with the creation, indexing, and provision of access to a very large archive of videotaped oral histories - 116,000 hours of digitized interviews in 32 languages from 52,000 survivors, liberators, rescuers, and witnesses of the Nazi Holocaust. It goes on to identify a set of critical research issues that must be addressed if we are to provide full and detailed access to collections of this size: issues in user requirement studies, automatic speech recognition, automatic classification, segmentation, summarization, retrieval, and user interfaces. The paper ends by inviting others to discuss use of these materials in their own research.
Keywords: cataloging; oral history; research agenda

Symbol systems - Anderson,M. L; Perlis, Don (Encyclopedia of Cognitive Science, 2002)

Technologies for families - Plaisant, Catherine; Druin, Allison; Hutchinson,Hilary (CHI '02 extended abstracts on Human factors in computing systems, 2002)
In this workshop, we propose to bring together researchers from industry and academia to discuss the design of new technologies for families. We will focus on both design techniques and the technologies themselves. Through discussions and brainstorming we hope to discover new ideas, which can be disseminated more broadly.
Keywords: cooperative design; disappearing computer; family; Home; participatory design; probe; user interface

Time-situated agency: Active logic and intention formation - Anderson,M. L; Josyula,D. P; Okamoto,Y. A; Perlis, Don (in: Workshop on Cognitive Agents, 25th German Conference on Artificial Intelligence, 2002)

The use-mention distinction and its importance to HCI - Anderson,M. L; Okamoto,Y.; Josyula,D.; Perlis, Don (Proceedings of the Sixth Workshop on the Semantics and Pragmatics of Dialog, 2002)

Video analysis applications for pervasive environments - Karunanidhi,A.; David Doermann; Parekh,N.; Rautio,V. (1st International Conference on Mobile and Ubiquitous Multimedia, 2002)
Network capabilities are expanding at arate that will soon allow a much wider range of image and video content to be delivered to and transmitted from mobile wireless devices. Current pervasive applications provide image and video content primarily in high performance networks or by streaming video over low-bandwidth networks. For video to be truly integrated into ubiquitous applications, we must carefully consider the role of automated video analysis to move beyond simple content delivery. Compression and content adaptation have been significant areas of research for some time and deal with the problem of moving media to devices with limited network, software and hardware capabilities. In the near future, mobile wireless devices that have been primarily consumers of image and video will be able to produce such content as well. In this paper, we will review some of the significant issues associated with providing video capabilities in pervasive environments. We consider not only streaming video applications, but point-to- point video and video messaging capabilities as well. We will show how our previous work on content adaptation is being applied to these types of environments, show what role more general video analysis can play and describe a general architecture for video capture, storage, analysis and transmission.

A visual search tool for early elementary science students - Revelle,G.; Druin, Allison; Platner,M.; Bederson, Benjamin B.; Hourcade,J. P; Sherman,L. (Journal of Science Education and Technology, 2002)

Wavelength rerouting in optical networks, or the Venetian Routing problem - Caprara,Alberto; Italiano,Giuseppe F.; Mohan,G.; Panconesi,Alessandro; Srinivasan, Aravind (Journal of Algorithms, 2002)
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 the given paths. In this paper we prove the computational hardness of this 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.
Keywords: Approximation algorithms; Label Cover; Optical networks; Shortest paths; Wavelength rerouting; Wavelength-division multiplexing

What we have learned about fighting defects - Shull, F.; Basili, Victor R.; Boehm,B.; Brown,A. W; Costa,P.; Lindvall,M.; Port,D.; Rus,I.; Tesoriero,R.; Zelkowitz, Marvin V (Software Metrics, 2002. Proceedings. Eighth IEEE Symposium on, 2002)
The Center for Empirically Based Software Engineering helps improve software development by providing guidelines for selecting development techniques, recommending areas for further research, and supporting software engineering education. A central activity toward achieving this goal has been the running of "e- Workshops" that capture expert knowledge with a minimum of overhead effort to formulate heuristics on a particular topic. The resulting heuristics are a useful summary of the current state of knowledge in an area based on expert opinion. This paper discusses the results to date of a series of e-Workshops on software defect reduction. The original discussion items are presented along with an encapsulated summary of the expert discussion. The reformulated heuristics can be useful both to researchers (for pointing out gaps in the current state of the knowledge requiring further investigation) and to practitioners (for benchmarking or setting expectations about development practices).
Keywords: based; Center; Computer; defect; development; education; electronic; Empiric; engineering; engineering; eWorkshops; for; heuristics; reduction; Science; software; workshops

Approximating large convolutions in digital images - Mount, Dave; Kanungo,T.; Netanyahu,N. S; Piatko,C.; Silverman,R.; Wu,A. Y (Image Processing, IEEE Transactions on, 2001)
Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m times;n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image
Keywords: 2D; algorithm; binary; approximation; mathematical; convolution; convolution; binary; convolutions; Bresenham's; convolutions; convex; convolutions; geometric; images; discrete; kernel; convex; kernel; digital; line-drawing; morphology; morphology; approximation; object; image; polygonal; processing; large; processing; mathematical; theory; convolution; image; two-dimensional

Better Approximation Guarantees for Job-Shop Scheduling - Goldberg,Leslie Ann; Paterson,Mike; Srinivasan, Aravind; Sweedyk,Elizabeth (SIAM Journal on Discrete Mathematics, 2001)
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). We also present NC algorithms with improved approximation guarantees for some NP-hard special cases.

Core semantics of multithreaded Java - Manson,Jeremy; Pugh, William (Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - JGI '01, 2001)

Coverage criteria for GUI testing - Memon, Atif M.; Soffa,Mary Lou; Pollack,Martha E. (Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, 2001)
A widespread recognition of the usefulness of graphical user interfaces (GUIs) has established their importance as critical components of today's software. GUIs have characteristics different from traditional software, and conventional testing techniques do not directly apply to GUIs. This paper's focus is on coverage critieria for GUIs, important rules that provide an objective measure of test quality. We present new coverage criteria to help determine whether a GUI has been adequately tested. These coverage criteria use events and event sequences to specify a measure of test adequacy. Since the total number of permutations of event sequences in any non-trivial GUI is extremely large, the GUI's hierarchical structure is exploited to identify the important event sequences to be tested. A GUI is decomposed into GUI components, each of which is used as a basic unit of testing. A representation of a GUI component, called an event-flow graph, identifies the interaction of events within a component and intra-component criteria are used to evaluate the adequacy of tests on these events. The hierarchical relationship among components is represented by an integration tree, and inter-component coverage criteria are used to evaluate the adequacy of test sequences that cross components. Algorithms are given to construct event-flow graphs and an integration tree for a given GUI, and to evaluate the coverage of a given test suite with respect to the new coverage criteria. A case study illustrates the usefulness of the coverage report to guide further testing and an important correlation between event-based coverage of a GUI and statement coverage of its software's underlying code.
Keywords: component testing; event-based coverage; event-flow graph; GUI test coverage; GUI testing; integration tree

Designing an Interactive Message Board as a Technology Probe for Family Communication - Browne,Hilary; Bederson, Benjamin B.; Plaisant, Catherine; Druin, Allison (Technical Reports of the Computer Science Department, 2001)
In this paper, we describe the design issues and technical implementation of aninteractive Family Message Board. The Family Message Board enables members of a distributed family to communicate with one another both synchronously and asynchronously via simple, pen-based, digital notes. Each household running thi$ Java-based software can view, create, and manipulate notes in a zoomable space. The Family Message Board will be used as a technology probe to help us unders$ the communication needs of distributed families, and to help us design new devi$ to meet those needs.
Keywords: Technical Report

Efficient and Non-interactive Non-malleable Commitment - Di Crescenzo,Giovanni; Katz, Jonathan; Ostrovsky,Rafail; Smith,Adam (Advances in Cryptology — EUROCRYPT 2001Advances in Cryptology — EUROCRYPT 2001, 2001)
We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are non-interactive . Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding.
Keywords: Computer science

Efficient perspective-accurate silhouette computation and applications - Pop, Mihai; Duncan,Christian; Barequet,Gill; Goodrich,Michael; Huang,Wenjing; Kumar,Subodh (Proceedings of the seventeenth annual symposium on Computational geometry, 2001)
Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the changes in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach. million vertices on an SGI Onyx workstation.
Keywords: rendering; silhouette; simplification

An empirical study of regression test selection techniques - Graves,Todd L.; Harrold,Mary Jean; Kim,Jung-Min; Porter, Adam; Rothermel,Gregg (ACM Transactions on Software Engineering and MethodologyACM Trans. Softw. Eng. Methodol., 2001)

Enabling Commuters to Find the Best Route: An Interface for Analyzing Driving History Logs - Konishi,M.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the IFIP Conference on Human-Computer Interaction (Interact2001), 2001)
This paper describes a prototype interface design for an automobile driving history log. It allows drivers to choose the best route among several alternatives for their common trips. Recorded data includes time to complete the travel, fuel consumption, and number of stops.

Eyes from Eyes - Baker,Patrick; Pless,Robert; Fermüller, Cornelia; Aloimonos, J. (3D Structure from Images — SMILE 20003D Structure from Images — SMILE 2000, 2001)
We describe a family of new imaging systems, called Argus eyes, that consist of common video cameras arranged in some network. The system we built consists of six cameras arranged so that they sample different parts of the visual sphere. This system has the capability of very accurately estimating its own 3D motion and consequently estimating shape models from the individual videos. The reason is that inherent ambiguities of confusion between translation and rotation disappear in this case. We provide an algorithm and several experiments using real outdoor or indoor images demonstrating the superiority of the new sensor with regard to 3D motion estimation.

Handling uncertainty with active logic - Bhatia,M.; Chi,P.; Chong,W.; Josyula,D. P; Okamoto,Y.; Perlis, Don; Purang,K. (In Proceedings, AAAI Fall Symposium on Uncertainty in Computation, 2001)

Hierarchical GUI test case generation using automated planning - Memon, Atif M.; Pollack,M. E; Soffa,M. L (Software Engineering, IEEE Transactions on, 2001)
The widespread use of GUIs for interacting with software is leading to the construction of more and more complex GUIs. With the growing complexity come challenges in testing the correctness of a GUI and its underlying software. We present a new technique to automatically generate test cases for GUIs that exploits planning, a well-developed and used technique in artificial intelligence. Given a set of operators, an initial state, and a goal state, a planner produces a sequence of the operators that will transform the initial state to the goal state. Our test case generation technique enables efficient application of planning by first creating a hierarchical model of a GUI based on its structure. The GUI model consists of hierarchical planning operators representing the possible events in the GUI. The test designer defines the preconditions and effects of the hierarchical operators, which are input into a plan-generation system. The test designer also creates scenarios that represent typical initial and goal states for a GUI user. The planner then generates plans representing sequences of GUI interactions that a user might employ to reach the goal state from the initial state. We implemented our test case generation system, called Planning Assisted Tester for Graphical User Interface Systems (PATHS) and experimentally evaluated its practicality and effectiveness. We describe a prototype implementation of PATHS and report on the results of controlled experiments to generate test cases for Microsoft's WordPad
Keywords: Artificial intelligence; automated planning; automatic test case generation; Automatic testing; correctness testing; goal state; Graphical user interfaces; hierarchical GUI test case generation; initial state; Microsoft WordPad; operators; plan-generation system; planning (artificial intelligence); Planning Assisted Tester for Graphical User Interface Systems; program testing; software

Intelligent assembly modeling and simulation - Gupta,S.K.; Paredis,C. J. J.; Sinha,R. (Assembly Automation, 2001)
Because of the intense competition in the current global economy, a company must conceive, design, and manufacture new products quickly and inexpensively. The design cycle can be shortened through simulation. Rapid technical advances in many different areas of scientific computing provide the enabling technologies for creating a comprehensive simulation and visualization environment for assembly design and planning. An intelligent environment has been built in which simple simulation tools can be composed into complex simulations for detecting potential assembly problems. The goal in this research is to develop high fidelity assembly simulation and visualization tools that can detect assembly related problems without going through physical mock-ups. In addition, these tools can be used to create easy-to-visualize instructions for performing assembly and service operations.

Intrusion tolerance approaches in ITUA - Michel Cukier; Lyons,J.; Pandey,P.; Ramasamy,H. V.; Sanders,W. H.; Pal,P.; Webber,F.; Schantz,R.; Loyall,J.; Watro,R. (2001)

Leveraging open-source communities to improve the quality & performance of open-source software - Schmidt,D. C; Porter, Adam (Proceedings of the 1st Workshop on Open Source Software Engineering, 2001)

Mapping lexical entries in a verbs database to WordNet senses - Green,Rebecca; Pearl,Lisa; Dorr, Bonnie J; Resnik, Philip (Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, 2001)
This paper describes automatic techniques for mapping 9611 entries in a database of English verbs to WordNet senses. The verbs were initially grouped into 491 classes based on syntactic features. Mapping these verbs into WordNet senses provides a resource that supports disambiguation in multilingual applications such as machine translation and cross-language information retrieval. Our techniques make use of (1) a training set of 1791 disambiguated entries, representing 1442 verb entries from 167 classes; (2) word sense probabilities, from frequency counts in a tagged corpus; (3) semantic similarity of WordNet senses for verbs within the same class; (4) probabilistic correlations between WordNet data and attributes of the verb classes. The best results achieved 72% precision and 58% recall, versus a lower bound of 62% precision and 38% recall for assigning the most frequently occurring WordNet sense, and an upper bound of 87% precision and 75% recall for human judgment.

Mapping WorldNet Senses to a Lexical Database of Verbs - Green,Rebecca; Pearl,Lisa; Dorr, Bonnie J (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2001)
This paper describes automatic techniques for mapping 9611 semantically classified English verbs to WordNet senses. The verbs were initially grouped into 491 semantic classes based on syntactic categories; they were then mapped into WordNet senses according to three pieces of information: (1) prior probability of WordNet senses; (2) semantic similarity of WordNet senses for verbs within the same category; and (3) probabilistic correlations between WordNet relationship and verb frame data. Our techniques make use of a training set of 1791 disambiguated entries representing 1442 verbs occurring in 167 of the categories. The best results achieved .58 recall and .72 precision, versus a lower bound of .38 recall and .62 precision for assigning the most frequently occurring WordNet sense, and an upper bound of .75 recall and .87 precision for human judgment.
Keywords: *DATA BASES; *ENGLISH LANGUAGE; *LEXICAL DATABASES; *LEXICOGRAPHY; *MAPPING; *VERBS; *WORD MAPPING; *WORDNET; AMBIGUITY; correlation; FRAMES; Frequency; INFORMATION SCIENCE; JUDGEMENT(PSYCHOLOGY); linguistics; PRECISION; probability; RECALL; semantics; syntax; WORDS(LANGUAGE); WSD(WORD SENSE DISAMBIGUATION)

More efficient network class loading through bundling - Hovemeyer,D.; Pugh, William (Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium-Volume 1, 2001)

Personal secure booting - Itoi,N.; Arbaugh, William A.; Pollack,S.; Reeves,D. (Information Security and Privacy, 2001)

A spherical eye from multiple cameras (makes better models of the world) - Baker, P.; Fermüller, Cornelia; Aloimonos, J.; Pless, R. (Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001. CVPR 2001, 2001)
The paper describes an imaging system that has been designed specifically for the purpose of recovering egomotion and structure from video. The system consists of six cameras in a network arranged so that they sample different parts of the visual sphere. This geometric configuration has provable advantages compared to small field of view cameras for the estimation of the system's own motion and consequently the estimation of shape models from the individual cameras. The reason is that inherent ambiguities of confusion between translation and rotation disappear. We provide algorithms for the calibration of the system and 3D motion estimation. The calibration is based on a new geometric constraint that relates the images of lines parallel in space to the rotation between the cameras. The 3D motion estimation uses a constraint relating structure directly to image gradients.
Keywords: 3D motion estimation; Calibration; camera network; CAMERAS; Computer vision; egomotion recovery; geometric configuration; geometric constraint; image gradients; image sampling; imaging system; Laboratories; Layout; Motion estimation; multiple cameras; Pixel; Robot vision systems; SHAPE; shape models; Space technology; spherical eye; system calibration; video; video cameras; video signal processing; visual sphere sampling

Therapeutic play with a storytelling robot - Lathan,Corinna; Vice,Jack Maxwell; Tracey,Michael; Plaisant, Catherine; Druin, Allison; Edward,Kris; Montemayor,Jaime (CHI '01 extended abstracts on Human factors in computing systems, 2001)
We are developing a prototype storytelling robot for use with children in rehabilitation. Children can remotely control a furry robot by using a variety of body sensors adapted to their disability or rehabilitation goal. We believe this robot can motivate children and help them reach their therapy goals through therapeutic play, either by exercising muscles or joints (e.g. for physically challenged children) or by reflecting on the stories (e.g. for children with developmental disabilities). To develop this technology we use an innovative design methodology involving children as design partners.
Keywords: children; design process; rehabilitation; robot; therapeutic play; user interface

Understanding Manufacturing Systems with a Learning Historian for User-Directed Experimentation - Chipman,G.; Plaisant, Catherine; Gahagan,S.; Herrmann,J.W.; Hewitt,S.; Reaves,L. (Department of Computer Science, University of Maryland, College Park, 2001)
This paper describes a learning historian to improve user-directed experimentation withdiscrete event simulation models of manufacturing systems. In user-directed experimentation, an analyst conducts simulation runs to estimate system performance. Then the analyst modifies the simulation model to evaluate other possibilities. An important characteristic is the ad hoc nature of the experimentation, as the analyst forms and runs new trials based on the results from previous trials. Through user-directed experimentation designers compare alternatives and students learn the relationships between input parameters and performance measures. Recording and reviewing previous trials while using simulation models enhances their benefits, transforming trial-and-error into learning. The learning historian combines a graphical user interface, a discrete event simulation model, and dynamic data visualization. Usability studies indicate that the learning historian is a usable and useful tool because it allows users to concentrate more on understanding system behavior than on operating simulation software.

VEHICLE SPEED INFORMATION DISPLAYS FOR PUBLIC WEBSITES: A STUDY OF USER PREFERENCES - Plaisant, Catherine; Bhamidipati,P.; Tarnoff,P. (ITS 2001: Conference Proceedings, 2001)

Watermarking scheme for image authentication - M. Wu; Liu,Bede (2001)
A digital watermarking process whereby an invisible watermark inserted into a host image is utilized to determine whether or not the image has been altered and, if so, where in the image such alteration occurred. The watermarking method includes the steps of providing a look-up table containing a plurality of coefficients and corresponding values; transforming the image into a plurality of blocks, wherein each block contains coefficients matching coefficients in the look-up table; and embedding the watermark in the image by performing the following substeps for at least some of the blocks: First, a coefficient is selected for insertion of a marking value representative of a corresponding portion of the watermark. Next, the value of the selected coefficient to used to identify a corresponding value in the look-up table. Finally, the identified coefficient is left unchanged if the corresponding value is the same as the marking value, and is changed if the corresponding value is...

The analysis of a simple k-means clustering algorithm - Kanungo,Tapas; Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine; Silverman,Ruth; Wu,Angela Y. (Proceedings of the sixteenth annual symposium on Computational geometry, 2000)

Attacking the bottlenecks of backfilling schedulers - Zotkin,Dmitry N; Keleher,P. J; Perkovic,D. (Cluster Computing, 2000)

Automated test oracles for GUIs - Memon, Atif M.; Pollack,Martha E.; Soffa,Mary Lou (SIGSOFT Softw. Eng. Notes, 2000)
Graphical User Interfaces (GUIs) are critical components of today's software. Because GUIs have different characteristics than traditional software, conventional testing techniques do not apply to GUI software. In previous work, we presented an approach to generate GUI test cases, which take the form of sequences of actions. In this paper we develop a test oracle technique to determine if a GUI behaves as expected for a given test case. Our oracle uses a formal model of a GUI, expressed as sets of objects, object properties, and actions. Given the formal model and a test case, our oracle automatically derives the expected state for every action in the test case. We represent the actual state of an executing GUI in terms of objects and their properties derived from the GUI's execution. Using the actual state acquired from an execution monitor, our oracle automatically compares the expected and actual states after each action to verify the correctness of the GUI for the test case. We implemented the oracle as a component in our GUI testing system, called Planning Assisted Tester for grapHical user interface Systems (PATHS), which is based on AI planning. We experimentally evaluated the practicality and effectiveness of our oracle technique and report on the results of experiments to test and verify the behavior of our version of the Microsoft WordPad's GUI.
Keywords: automated oracles; GUI test oracles; GUI testing

A Case for Evolutionary Genomics and the Comprehensive Examination of Sequence Biodiversity - Pollock,David D; Eisen,Jonathan A.; Doggett,Norman A; Cummings, Michael P. (Molecular Biology and EvolutionMol Biol Evol, 2000)
Comparative analysis is one of the most powerful methods available for understanding the diverse and complex systems found in biology, but it is often limited by a lack of comprehensive taxonomic sampling. Despite the recent development of powerful genome technologies capable of producing sequence data in large quantities (witness the recently completed first draft of the human genome), there has been relatively little change in how evolutionary studies are conducted. The application of genomic methods to evolutionary biology is a challenge, in part because gene segments from different organisms are manipulated separately, requiring individual purification, cloning, and sequencing. We suggest that a feasible approach to collecting genome-scale data sets for evolutionary biology (i.e., evolutionary genomics) may consist of combination of DNA samples prior to cloning and sequencing, followed by computational reconstruction of the original sequences. This approach will allow the full benefit of automated protocols developed by genome projects to be realized; taxon sampling levels can easily increase to thousands for targeted genomes and genomic regions. Sequence diversity at this level will dramatically improve the quality and accuracy of phylogenetic inference, as well as the accuracy and resolution of comparative evolutionary studies. In particular, it will be possible to make accurate estimates of normal evolution in the context of constant structural and functional constraints (i.e., site-specific substitution probabilities), along with accurate estimates of changes in evolutionary patterns, including pairwise coevolution between sites, adaptive bursts, and changes in selective constraints. These estimates can then be used to understand and predict the effects of protein structure and function on sequence evolution and to predict unknown details of protein structure, function, and functional divergence. In order to demonstrate the practicality of these ideas and the potential benefit for functional genomic analysis, we describe a pilot project we are conducting to simultaneously sequence large numbers of vertebrate mitochondrial genomes.

Communication complexity of document exchange - Cormode,Graham; Paterson,Mike; Sahinalp,Süleyman Cenk; Vishkin, Uzi (Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000)

Contention resolution with constant expected delay - Goldberg,Leslie Ann; Mackenzie,Philip D.; Paterson,Mike; Srinivasan, Aravind (J. ACM, 2000)
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expected delay (time to get serviced) of every message is O(log n) when messages are generated according to a Bernoulli distribution with generation rate up to about 1/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1/e, and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1/e. (Each message constitutes a new user.)To achieve (a), we first show how to simulate (b) using n synchronized users, and then show how to build the synchronization into the protocol.
Keywords: contention resolution; Ethernet; Markov chains; multiple-access channel

Designing StoryRooms: interactive storytelling spaces for children - Alborzi,H.; Druin, Allison; Montemayor,J.; Platner,M.; Porteous,J.; Sherman,L.; Boltman,A.; Taxén,G.; Best,J.; Hammer,J.; others (Proceedings of the 3rd conference on Designing interactive systems: processes, practices, methods, and techniques, 2000)

Detecting independent motion: The statistics of temporal continuity - Pless, R.; Brodsky, T.; Aloimonos, J. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2000)

Empirical studies of software engineering: a roadmap - Perry,D. E.; Porter, Adam; Votta,L. G. (Proceedings of the conference on The future of Software engineering, 2000)

An empirical study of regression test application frequency - Kim,Jung-Min; Porter, Adam; Rothermel,Gregg (Proceedings of the 22nd international conference on Software engineering - ICSE '00, 2000)

Evaluation challenges for a Federation of heterogeneous information providers: the case of NASA's Earth Science Information Partnerships - Plaisant, Catherine; Komlodi,A.; Lindsay,F. (Enabling Technologies: Infrastructure for Collaborative Enterprises, 2000. (WET ICE 2000). Proeedings. IEEE 9th International Workshops on, 2000)
NASA's Earth Science Information Partnership Federation is an experiment funded to assess the ability of a group of widely heterogeneous earth science data or service providers to self organize and provide improved and affordable access to an expanding earth science user community. As it is self-organizing, the Federation is mandated to set in place an evaluation methodology and collect metrics reflecting the outcomes and benefits of the Federation. This paper describes the challenges of organizing such a federated partnership self-evaluation and discusses the issues encountered during the metrics definition phase of the early data collection. Our experience indicates that a large number of metrics will be needed to fully represent the activities and strengths of all partners, but because of the heterogeneity of the ESIPs the qualitative data (comments accompanying the metric data and success stories) becomes the most useful information. Other lessons learned included the absolute need for online browsing tools to accompany data collection tools. Finally, our experience confirms the effect of evaluation as an agent of change, the best example being the high level of collaboration among the ESIPs which can be in part attributed to the initial identification of collaboration as one of the important evaluation factors of the Federation
Keywords: Browsing; collection; heterogeneous; computing; groupware; data; online; Earth; Federation; data; information; NASA's; Partnership; Science; systems; geophysics; tools; geographic

Facilitating data exploration with query previews: A study of user performance and preference - Tanin,Egemen; Lotem,Amnon; Haddadin,Ihab; Shneiderman, Ben; Plaisant, Catherine; Slaughter,Laura (Behaviour & Information Technology, 2000)
Networked and local data exploration systems that use command languages, menus, or form fill-in interfaces rarely give users an indication of the distribution of data. This often leads users to waste time, posing queries that have zero-hit or mega-hit results. Query previews are a novel visual approach for browsing databases. Query previews supply users with data distribution information for selected attributes of the database, and give continuous feedback about the size of the result set as the query is being formed. Subsequent refinements might be necessary to narrow the search. As there is a risk that query previews are an additional step, leading to a more complex and slow search process, a within-subjects empirical study was ran with 12 subjects who used interfaces with and without query previews and with minimized network delays. Even with 12 subjects and minimized network delays statistically significant differences were found, showing that query previews could speed up performance 1.6 to 2.1 times and lead to higher user satisfaction.Networked and local data exploration systems that use command languages, menus, or form fill-in interfaces rarely give users an indication of the distribution of data. This often leads users to waste time, posing queries that have zero-hit or mega-hit results. Query previews are a novel visual approach for browsing databases. Query previews supply users with data distribution information for selected attributes of the database, and give continuous feedback about the size of the result set as the query is being formed. Subsequent refinements might be necessary to narrow the search. As there is a risk that query previews are an additional step, leading to a more complex and slow search process, a within-subjects empirical study was ran with 12 subjects who used interfaces with and without query previews and with minimized network delays. Even with 12 subjects and minimized network delays statistically significant differences were found, showing that query previews could speed up performance 1.6 to 2.1 times and lead to higher user satisfaction.

Fault tolerant K-center problems - Khuller, Samir; Pless,Robert; Sussmann,Yoram J. (Theoretical Computer Science, 2000)
The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve an approximation factor of 2 have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of α (α⩽K) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least α centers close to it. In the second version, each vertex that does not have a center placed on it is required to have at least α centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for any α. For the first version we give an algorithm that achieves an approximation factor of 3 for any α, and achieves an approximation factor of 2 for α<4. For the second version, we provide algorithms with approximation factors of 2 for any α. The best possible approximation factor for even the basic K-center problem is 2, assuming P≠NP. In addition, we give a polynomial time approximation algorithm for a generalization of the K-supplier problem where a subset of at most K supplier nodes must be selected as centers so that every demand node has at least α centers close to it. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P≠NP.
Keywords: Approximation algorithms; Facility location; Fault-tolerance; K-center

GP+ echo+ subsumption= improved problem solving - Punch,W.F.; Rand, William (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), 2000)
Real-time, adaptive control is a difficult problemthat can be addressed by EC architectures. We are interested in incorporating into an EC architecture some of the features that Holland’s Echo architecture presents. Echo has been used to model everything from cultures to financial markets. However, the typical application of Echo is a simulation to observe the dynamics of the modeled elements such as found in control problems. We show in this paper that some aspects of Echo can be incorporated into Genetic Programming to solve control problems. The paper discusses EAGP (Echo Augmented Genetic Programming), a modified GP architecture that uses aspects of Echo, and subsumption. We demonstrate the usefulness of EAGP on a robot navigation problem

The Java memory model is fatally flawed - Pugh, William (Concurrency - Practice and Experience, 2000)

Live multimedia adaptation through wireless hybrid networks - Koivisto,A.; Pietkainen,P.; Sauvola,J.; David Doermann (Multimedia and Expo, 2000. ICME 2000. 2000 IEEE International Conference on, 2000)
We present new techniques to intelligently adapt and combine multimedia presentations in real-time, mobile service environments. We present the techniques necessary to perform mobile multimedia processing for multiple video streams with ldquo;value-adding rdquo; information. The adaptation uses video analysis, content-recognition and automated annotation to provide scalable and interactive presentations over hybrid networks to mobile terminals. As a concrete case, we present a mobile surveillance service called Princess, which has several video sources and supports control information, terminal adaptation and end-to-end service
Keywords: adaptation; mobile; adaptation; value-adding; analysis; wireless; annotation; content-recognition; end-to-end; communication; multimedia; communication; real-time; hybrid; information; video; LAN; multimedia; networks; mobile; Princess; automated; processing; mobile; service; live; service; mobile; streams; real-time; Surveillance; system; terminal; systems; surveillance; wireless; terminals; multiple; video

On local search and placement of meters in networks - Khuller, Samir; Bhatia,Randeep; Pless,Robert (Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000)

A logic for characterizing multiple bounded agents - Grant,J.; Kraus,S.; Perlis, Don (Autonomous Agents and Multi-Agent Systems, 2000)

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.

Multi-camera networks: eyes from eyes - Fermüller, Cornelia; Aloimonos, J.; Baker, P.; Pless, R.; Neumann, J.; Stuart, B. (IEEE Workshop on Omnidirectional Vision, 2000. Proceedings, 2000)
Autonomous or semi-autonomous intelligent systems, in order to function appropriately, need to create models of their environment, i.e., models of space time. These are descriptions of objects and scenes and descriptions of changes of space over time, that is, events and actions. Despite the large amount of research on this problem, as a community we are still far from developing robust descriptions of a system's spatiotemporal environment using video input (image sequences). Undoubtedly, some progress has been made regarding the understanding of estimating the structure of visual space, but it has not led to solutions to specific applications. There is, however, an alternative approach which is in line with today's “zeitgeist.” The vision of artificial systems can be enhanced by providing them with new eyes. If conventional video cameras are put together in various configurations, new sensors can be constructed that have much more power and the way they “see” the world makes it much easier to solve problems of vision. This research is motivated by examining the wide variety of eye design in the biological world and obtaining inspiration for an ensemble of computational studies that relate how a system sees to what that system does (i.e. relating perception to action). This, coupled with the geometry of multiple views that has flourished in terms of theoretical results in the past few years, points to new ways of constructing powerful imaging devices which suit particular tasks in robotics, visualization, video processing, virtual reality and various computer vision applications, better than conventional cameras. This paper presents a number of new sensors that we built using common video cameras and shows their superiority with regard to developing models of space and motion
Keywords: Biosensors; CAMERAS; Computer vision; Eyes; Image sequences; intelligent systems; Layout; Machine vision; Robot vision systems; Robustness; Spatiotemporal phenomena; video cameras; Virtual reality

New Eyes for Shape and Motion Estimation - Baker,Patrick; Pless,Robert; Fermüller, Cornelia; Aloimonos, J. (Biologically Motivated Computer VisionBiologically Motivated Computer Vision, 2000)
Motivated by the full field of view of insect eyes and their fast and accurate estimation of egomotion, we constructed a system of cameras to take advantage of the full field of view (FOV) constraints that insects use. In this paper, we develop a new ego-motion algorithm for a rigidly mounted set of cameras undergoing arbitrary rigid motion. This egomotion algorithm combines the unambiguous components of the motion computed by each separate camera. We prove that the cyclotorsion is resistant to errors and show this empirically. We show how to calibrate the system with two novel algorithms, one using secondary cameras and one using self calibration. Given this system calibration, the new 3D motion algorithm first computes the rotation and then the 3D translation. We apply this algorithm to a camera system constructed with four rigidly mounted synchronized cameras pointing in various directions and present motion estimation results at www.cfar.umd.edu/ pbaker/argus.html.

The Ouchi illusion as an artifact of biased flow estimation - Fermüller, Cornelia; Pless,Robert; Aloimonos, J. (Vision Research, 2000)
A pattern by Ouchi has the surprising property that small motions can cause illusory relative motion between the inset and background regions. The effect can be attained with small retinal motions or a slight jiggling of the paper and is robust over large changes in the patterns, frequencies and boundary shapes. In this paper, we explain that the cause of the illusion lies in the statistical difficulty of integrating local one-dimensional motion signals into two-dimensional image velocity measurements. The estimation of image velocity generally is biased, and for the particular spatial gradient distributions of the Ouchi pattern the bias is highly pronounced, giving rise to a large difference in the velocity estimates in the two regions. The computational model introduced to describe the statistical estimation of image velocity also accounts for the findings of psychophysical studies with variations of the Ouchi pattern and for various findings on the perception of moving plaids. The insight gained from this computational study challenges the current models used to explain biological vision systems and to construct robotic vision systems. Considering the statistical difficulties in image velocity estimation in conjunction with the problem of discontinuity detection in motion fields suggests that theoretically the process of optical flow computations should not be carried out in isolation but in conjunction with the higher level processes of 3D motion estimation, segmentation and shape computation.
Keywords: Bias; MOTION; optical flow; Plaid; Statistics

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.

A planning-based approach to GUI testing - Memon, Atif M.; Pollack,M. E; Soffa,M. L (Proceedings of The 13th International Software/Internet Quality Week, 2000)

Previews and overviews in digital libraries: Designing surrogates to support visual information seeking - Greene,Stephan; Marchionini,Gary; Plaisant, Catherine; Shneiderman, Ben (Journal of the American Society for Information Science, 2000)
To aid designers of digital library interfaces, we present a framework for the design of information representations in terms of previews and overviews. Previews and overviews are graphic or textual representations of information abstracted from primary information objects. Previews act as surrogates for one or a few objects and overviews represent collections of objects. A design framework is elaborated in terms of the following three dimensions: (1) what information objects are available to users, (2) how information objects are related and displayed, and (3) how users can manipulate information objects. When utilized properly, previews and overviews allow users to rapidly discriminate objects of interest from those not of interest, and to more fully understand the scope and nature of digital libraries. This article presents a definition of previews and overviews in context, provides design guidelines, and describes four example applications.

Quantile approximation for robust statistical estimation and k-enclosing problems - Mount, Dave; Netanyahu,N. S; Piatko,C. D; Silverman,R.; Wu,A. Y (International Journal of Computational Geometry and Applications, 2000)
Given a set P of n points in Rd, a fundamental problem in computational geometryis concerned with finding the smallest shape of some type that encloses all the points of P. Well-known instances of this problem include finding the smallest enclosing box, minimum volume ball, and minimum volume annulus. In this paper we consider the following variant: Given a set of n points in Rd, find the smallest shape in question that contains at least k points or a certain quantile of the data. This type of problem is known as a k-enclosing problem. We present a simple algorithmic framework for computing quantile approximations for the minimum strip, ellipsoid, and annulus containing a given quantile of the points. The algorithms run in O(n log n) time.

Retrieval scheduling for collaborative multimedia presentations - Bai,Ping; Prabhakaran,B.; Srinivasan, Aravind (Multimedia Systems, 2000)
The single-system approach is no longer sufficient to handle the load on popular Internet servers, especially for those offering extensive multimedia content. Such services have to be replicated to enhance their availability, performance, and reliability. In a highly replicated and available environment, server selection is an important issue. In this paper, we propose an application-layer broker (ALB) for this purpose. ALB employs a content-based, client-centric approach to negotiate with the servers and to identify the best server for the requested objects. ALB aims to maximize client buffer utilization in order to efficiently handle dynamic user interactions such as skip, reverse presentation, go back in time. We also present details of a collaborative multimedia presentation platform that we have developed based on ALB.

Simulation based learning environments and the use of learning histories - Rose,A.; Salter,R.; Keswani,S.; Kositsyna,N.; Plaisant, Catherine; Rubloff,G.; Shneiderman, Ben (CHI '00 extended abstracts on Human factors in computing systems, 2000)
We have developed an application framework for constructing simulation-based learning environments using dynamic simulations and visualizations to represent realistic time-dependent behavior. The development environment is described and many examples are given. In particular we will focus on the learning historian which provides users and learners with a manipulatable recording of their actions which facilitates the exchange of annotated history records among peers and mentors.
Keywords: education; engineering; History; learning; simulation

Smart videoconferencing - Zotkin,Dmitry N; Duraiswami, Ramani; Philomin,V.; Davis, Larry S. (2000 IEEE International Conference on Multimedia and Expo, 2000. ICME 2000, 2000)
The combination of acoustical and video processing to achieve a smart audio and video feed from a set of N microphones and M cameras is a task that might conventionally be accomplished by camera persons and control room staff. However, in the context of videoconferencing, this process needs to be performed by control software. We discuss the use of a multi-camera multi-microphone set-up for unattended videoconferencing, and present details of a prototype implementation being developed
Keywords: acoustical processing; Automatic control; CAMERAS; computerised control; control software; Control systems; Intelligent sensors; Layout; Microphones; multi-camera multi-microphone set-up; multimedia systems; Protocols; prototype implementation; Prototypes; sensor fusion; smart videoconferencing; Switches; Teleconferencing; unattended videoconferencing; video processing

A storytelling robot for pediatric rehabilitation - Plaisant, Catherine; Druin, Allison; Lathan,Corinna; Dakhane,Kapil; Edwards,Kris; Vice,Jack Maxwell; Montemayor,Jaime (Proceedings of the fourth international ACM conference on Assistive technologies, 2000)
Keywords: children; design process; rehabilitation; robot; therapeutic play; user interface

Subgrid-scale models for compressible large-eddy simulations - Martin, M.P; Piomelli,U.; Candler,G. V (Theoretical and Computational Fluid Dynamics, 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)

Vehicle Speed Information Displays for Public Websites A Survey of User Preferences - Plaisant, Catherine; Bhamidipati,Phanikumar (Technical Reports from UMIACS, 2000)
The paper reports on a study comparing alternative presentations offreeway speed data on maps. The goal of the study was to inform the design of displays of real time speed data over the Internet to the general public. Subjects were presented with a series of displays and asked to rate their preferences. We looked at different choices of color (3 colors, 6 colors or a continuous range), and proposed line, sensor, and segment representations of the speed data. We also collected feedback on more complex displays such as comparison between current and "normal" speeds, and a chart of speed variation over a period of time at given locations. (Also cross-referenced as HCIL-TR-2000-23) (Also cross-referenced as UMIACS-TR-2000-73)
Keywords: Technical Report

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.

What does it take to refer - Perlis, Don (Journal of Consciousness Studies, 2000)

What does it take to refer? a reply to Bojadziev - Perlis, Don (Journal of Consciousness Studies, 2000)

Application-layer broker for scalable Internet services with resource reservation - Bai,Ping; Prabhakaran,B.; Srinivasan, Aravind (Proceedings of the seventh ACM international conference on Multimedia (Part 2), 1999)

Binary space parititions in plücker space - Mount, Dave; Pu,F. T (Algorithm Engineering and Experimentation, 1999)
One of the important potential applications of computational geometry is in the field of computer graphics. One challenging computational problem in computer graphics is that of rendering scenes with nearly photographic realism. A major distinction in lighting and shading models in computer graphics is between local illumination models and global illumination models. Local illumination models are available with most commercial graphics software. In such a model the color of a point on an object is modeled as a function of the local surface properties of the object and its relation to a typically small number of point light sources. The other objects of scene have no effect. In contrast, in global illumination models, the color of a point is determined by considering illumination both from direct light sources as well as indirect lighting from other surfaces in the environment. In some sense, there is no longer a distinction between objects and light sources, since every surface is a potential emitter of (indirect) light. Two physical-based methods dominate the field of global illumination. They are ray tracing [8] and radiosity [3].

Browsing hierarchical data with multi-level dynamic queries - Kumar,H. P; Plaisant, Catherine; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 1999)

Comparing causal-link and propositional planners: Tradeoffs between plan length and domain size - Memon, Atif M.; Pollack,M.; Soffa,M. L (Technical Report 99-06, University of Pittsburgh, Pittsburgh, 1999)
Recent studies have shown that propositional planners, which de-rive from Graphplan and SATPLAN, can generate significantly longer plans than causal-link planners. We present experimental evidence demonstrating that while this may be true, propositional planners also have important limitations relative to the causal-link planners: specifically, they can generate plans only for smaller domains, where the size of a domain is defined by the number of distinguishable objects it contains. Our experiments were conducted in the domain of code optimization, in which the states of the world represent states of the computer program code and the planning operators are the optimiza- tion operators. This domain is well-suited to studying the trade-offs between plan length and domain size, because it is straightforward to manipulate both these factors. On the basis of our experiments, we conclude that causal-link and propositional planners have complementary strengths.

Compressing Java class files - Pugh, William (ACM SIGPLAN Notices, 1999)

Computing nearest neighbors for moving points and applications to clustering - Kanungo,Tapas; Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine; Silverman,Ruth; Wu,Angela Y. (Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, 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

The design of history mechanisms and their use in collaborative educational simulations - Plaisant, Catherine; Rose,Anne; Rubloff,Gary; Salter,Richard; Shneiderman, Ben (Proceedings of the 1999 conference on Computer support for collaborative learning, 1999)
Reviewing past events has been useful in many domains. Videotapes and flight data recorders provide invaluable technological help to sports coaches or aviation engineers. Similarly, providing learners with a readable recording of their actions may help them monitor their behavior, reflect on their progress, and experiment with revisions of their experiences. It may also facilitate active collaboration among dispersed learning communities. Learning histories can help students and professionals make more effective use of digital library searching, word processing tasks, computer-assisted design tools, electronic performance support systems, and web navigation.This paper describes the design space and discusses the challenges of implementing learning histories. It presents guidelines for creating effective implementations, and the design tradeoffs between sparse and dense history records. The paper also presents a first implementation of learning histories for a simulation-based engineering learning environment called SimPLE (Simulated Processes in a Learning Environment) for the case of a semiconductor fabrication module, and reports on early user evaluation of learning histories implemented within SimPLE.
Keywords: hci; scaffolding; simulation

Designing PETS: a personal electronic teller of stories - Druin, Allison; Montemayor,Jamie; Hendler,Jim; McAlister,Britt; Boltman,Angela; Fiterman,Eric; Plaisant,Aurelie; Kruskal,Alex; Olsen,Hanne; Revett,Isabella; Schwenn,Thomas Plaisant; Sumida,Lauren; et al. (Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, 1999)
We have begun the development of a new robotic pet that cansupport children in the storytelling process. Children can build their own pet by snapping together the modular animal parts of the PETS robot. After their pet is built, children can tell stories using the My Pets software. These stories can then be acted out by their robotic pet. This video paper describes the motivation for this research and the design process of our intergenerational design team in building the first PETS prototypes. We will discuss our progress to date and our focus for the future.
Keywords: children; cooperative inquiry; design techniques; educational applications; intergenerational design team; PETS; ROBOTICS

Developing the next generation of Earth science data systems: the Global Land Cover Facility - Lindsay,F.E.; Townshend,J.R.G.; JaJa, Joseph F.; Humphries,J.; Plaisant, Catherine; Shneiderman, Ben (Geoscience and Remote Sensing Symposium, 1999. IGARSS '99 Proceedings. IEEE 1999 International, 1999)
A recent initiative by NASA has resulted in the formation of a federation of Earth science data partners. These Earth Science Information Partners (ESIPs) have been tasked with creating novel Earth science data products and services as well as distributing new and existing data sets to the Earth science community and the general public. The University of Maryland established its ESIP activities with the creation of the Global Land Cover Facility (GLCF). This joint effort of the Institute for Advanced Computer Studies (UMIACS) and the Department of Geography has developed an operational data archiving and distribution system aimed at advancing current land cover research efforts. The success of the GLCF is tied closely to assessing user needs as well. As the timely delivery of data products to the research community. This paper discusses the development and implementation of a web-based interface that allows users to query the authors' data holdings and perform user requested processing tasks on demand. The GLCF takes advantage of a scaleable, high performance computing architecture for the manipulation of very large remote sensing data sets and the rapid spatial indexing of multiple format data types. The user interface has been developed with the cooperation of the Human-Computer Interaction Laboratory (HCIL) and demonstrates advances in spatial and temporal querying tools as well as the ability to overlay multiple raster and vector data sets. Their work provides one perspective concerning how critical earth science data may be handled in the near future by a coalition of distributed data centers
Keywords: Computer architecture; data archiving; data distribution system; Data systems; Distributed computing; Earth science data products; Earth science data system; ESIP; geographic information system; geographic information systems; Geography; geophysical measurement technique; geophysical signal processing; geophysical techniques; Geoscience; GIS; GLCF; Global Land Cover Facility; High performance computing; Indexing; information service; Information services; Institute for Advanced Computer Studies; land cover; NASA; next generation; PACS; Remote sensing; terrain mapping; UMIACS; University of Maryland; User interfaces; web-based interface

Efficient perspective-accurate silhouette computation - Barequet,G.; Duncan,C. A; Goodrich,M. T; Kumar,S.; Pop, Mihai (Proceedings of the fifteenth annual symposium on Computational geometry, 1999)

The end of zero-hit queries: query previews for NASA’s Global Change Master Directory - Greene,Stephan; Tanin,Egemen; Plaisant, Catherine; Shneiderman, Ben; Olsen,Lola; Major,Gene; Johns,Steve (International Journal on Digital Libraries, 1999)
The Human-Computer Interaction Laboratory (HCIL) of the University of Maryland and NASA have collaborated over three years to refine and apply user interface research concepts developed at HCIL in order to improve the usability of NASA data services. The research focused on dynamic query user interfaces, visualization, and overview + preview designs. An operational prototype, using query previews, was implemented with NASA’s Global Change Master Directory (GCMD), a directory service for earth science datasets. Users can see the histogram of the data distribution over several attributes and choose among attribute values. A result bar shows the cardinality of the result set, thereby preventing users from submitting queries that would have zero hits. Our experience confirmed the importance of metadata accuracy and completeness. The query preview interfaces make visible the problems or gaps in the metadata that are undetectable with classic form fill-in interfaces. This could be seen as a problem, but we think that it will have a long-term beneficial effect on the quality of the metadata as data providers will be compelled to produce more complete and accurate metadata. The adaptation of the research prototype to the NASA data required revised data structures and algorithms.

Excentric labeling: dynamic neighborhood labeling for data visualization - Fekete,Jean-Daniel; Plaisant, Catherine (Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, 1999)
The widespread use of information visualization is hampered bythe lack of effective labeling techniques. An informal taxonomy of labeling methods is proposed. We then describe excentric labeling, a new dynamic technique to label a neighborhood of objects located around the cursor. This technique does not intrude into the existing interaction, it is not computationally intensive, and was easily applied to several visualization applications. A pilot study with eight subjects indicates a strong speed benefit over a zoom interface for tasks that involve the exploration of large numbers of objects. Observations and comments from users are presented.
Keywords: dynamic labeling; Evaluation; label; Visualization

Exposing Application Alternatives - Keleher, Peter J.; Hollingsworth, Jeffrey K; Perkovic, Dejan (Distributed Computing Systems, International Conference on, 1999)
We present the design of an interface to allow applications to export tuning alternatives to a higher-level system. By exposing different parameters that can be changed at runtime, applications can be made to adapt to changes in their execution environment due to other programs, or the addition or deletion of nodes, communication links etc. An integral part of this interface is that an application not only expose its options, but also the resource utilization of each option and the effect that the option will have on the application's performance. We discuss how these options can be evaluated to tune the overall performance of a collection of applications in the system. Finally, we show preliminary results from a database application that is automatically reconfigured by the system from query shipping to data shipping based on the number of active clients.
Keywords: computational grids; metacomputing; scheduling

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

Fixing the Java memory model - Pugh, William (Proceedings of the ACM 1999 conference on Java Grande, 1999)

Fkpurang, darsana, traum, cfa, perlisg@ cs. umd. edu - Edu,C. U; Purang,K.; Purushothaman,D.; Traum,D.; Andersen,C.; Perlis, Don (In Proceedings of the IJCAI’99 Workshop on Practical Reasoning and Rationality, 1999)

Human-centered computing, online communities, and virtual environments - Brown,J. R; van Dam,A.; Earnshaw,R.; Encarnacao,J.; Guedj,R.; Preece,J.; Shneiderman, Ben; Vince,J. (IEEE Computer Graphics and Applications, 1999)
This report summarizes results of the first EC/NSF joint Advanced Research Workshop, which identified key research challenges and opportunities in information technology. The group agreed that the first joint research workshop should concentrate on the themes of human-centered computing and VEs. Human-centered computing is perceived as an area of strategic importance because of the move towards greater decentralization and decomposition in the location and provision of computation. The area of VEs is one where increased collaboration should speed progress in solving some of the more intractable problems in building effective applications
Keywords: Books; Collaboration; Collaborative work; Conferences; EC/NSF joint Advanced Research Workshop; Feeds; Human computer interaction; human-centered computing; Internet; Joining materials; Laboratories; Online communities; Research initiatives; USA Councils; User interfaces; Virtual environment; virtual environments; Virtual reality

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

Independent motion: the importance of history - Pless, R.; Brodsky, T.; Aloimonos, J. (Computer Vision and Pattern Recognition, 1999. IEEE Computer Society Conference on., 1999)
We consider a problem central in aerial visual surveillance applications-detection and tracking of small, independently moving objects in long and noisy video sequences. We directly use spatiotemporal image intensity gradient measurements to compute an exact model of background motion. This allows the creation of accurate mosaics over many frames and the definition of a constraint violation function which acts as an indication of independent motion. A novel temporal integration method maintains confidence measures over long subsequences without computing the optic flow, requiring object models, or using a Kalman filler. The mosaic acts as a stable feature frame, allowing precise localization of the independently moving objects. We present a statistical analysis of the effects of image noise on the constraint violation measure and find a good match between the predicted probability distribution function and the measured sample frequencies in a test sequence
Keywords: aerial visual surveillance; background image; Fluid flow measurement; Frequency measurement; History; Motion detection; Motion estimation; Motion measurement; Noise measurement; Optical computing; Optical noise; spatiotemporal image intensity gradient measurements; Spatiotemporal phenomena; Surveillance; Video sequences

Interface and data architecture for query preview in networked information systems - Plaisant, Catherine; Shneiderman, Ben; Doan,Khoa; Bruns,Tom (ACM Trans. Inf. Syst., 1999)
There are numerous problems associated with formulating queries onnetworked information systems. These include increased data volume and complexity, accompanied by slow network access. This article proposes a new approach to a network query user interfaces that consists of two phases: query preview and query refinement. This new approach is based on the concepts of dynamic queries and query previews, which guides users in rapidly and dynamically eliminating undesired records, reducing the data volume to a manageable size, and refining queries locally before submission over a network. Examples of two applications are given: a Restaurant Finder and a prototype for NASA's Earth Observing Systems Data Information Systems (EOSDIS). Data architecture is discussed, and user feedback is presented.
Keywords: direct manipulation; dynamic query; EOSDIS; graphical user interface; query preview; query refinement; science data

Learning probabilistic relational models - Friedman,N.; Getoor, Lise; Koller,D.; Pfeffer,A. (International Joint Conference on Artificial Intelligence, 1999)
A large portion of real-world data is stored in com-mercial relational database systems. In contrast, most statistical learning methods work only with “flat” data representations. Thus, to apply these methods, we are forced to convert our data into a flat form, thereby losing much of the relational structure present in our database. This paper builds on the recent work on probabilistic relational mod- els (PRMs), and describes how to learn them from databases. PRMs allow the properties of an object to depend probabilistically both on other proper- ties of that object and on properties of related ob- jects. Although PRMs are significantly more ex- pressive than standard models, such as Bayesian networks, we show how to extend well-known sta- tistical methods for learning Bayesian networks to learn these models. We describe both parameter estimation and structure learning — the automatic induction of the dependency structure in a model. Moreover, we show how the learning procedure can exploit standard database retrieval techniques for efficient learning from large datasets. We present experimental results on both real and synthetic re- lational databases.

LifeLines: Visualizing Personal Histories - Kumar,H. P; Plaisant, Catherine; Shneiderman, Ben (Readings in Information Visualization: Using Vision to ThinkReadings in Information Visualization: Using Vision to Think, 1999)

Mixed initiative dialogue and intelligence via active logic - Andersen,C.; Traum,D.; Purang,K.; Purushothaman,D.; Perlis, Don (proceedings of the AAAI99 Workshop on Mixed-Initiative Intelligence, 1999)

Model-checking concurrent systems with unbounded integer variables: symbolic representations, approximations, and experimental results - Bultan,Tevfik; Gerber,Richard; Pugh, William (ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst., 1999)

Multilingual Information Discovery and AccesS (MIDAS): A Joint ACM DL'99/ ACM SIGIR'99 Workshop. - Oard, Douglas; Peters,Carol; Ruiz,Miguel; Frederking,Robert; Klavans,Judith; Sheridan,Paraic (D-Lib MagazineD-Lib Magazine, 1999)
Discusses a multidisciplinary workshop that addressed issues concerning internationally distributed information networks. Highlights include multilingual information access in media other than character-coded text; cross-language information retrieval and multilingual metadata; and evaluation of multilingual systems. (LRW)
Keywords: Distributed computing; Electronic Media

Page Segmentation and Zone Classification: The State of the Art - Okun,O.; David Doermann; Pietikainen,M. (University of Maryland, College Park, 1999)
Page segmentation and zone classification are key areas of research in document image processing, because they occupy an intermediate position between document preprocessing and higher-level document understanding such as logical page analysis and OCR. Such analysis of the page relies heavily on an appropriate document model and results in a representation of the physical structure of the document. The purpose of this review is to analyze progress made in page segmentation and zone classification and suggest what needs to be done to advance the field.

Pixel Data Access for End-User Programming and Graphical Macros - Potter,Richard; Shneiderman, Ben (Technical Reports from UMIACS, 1999)
Pixel Data Access is an interprocess communication technique that enablesusers of graphical user interfaces to automate certain tasks. By accessing the contents of the display buffer, users can search for pixel representations of interface elements, and then initiate actions such as mouse clicks and keyboard entries. While this technique has limitations it offers users of current systems some unusually powerful features that are especially appealing in the area of end-user programming. Also cross-referenced as UMIACS-TR-99-27
Keywords: Technical Report

Practical reasoning and plan execution with active logic - Purang,K.; Purushothaman,D.; Traum,D.; Andersen,C.; Perlis, Don (Proceedings of the IJCAI-99 Workshop on Practical Reasoning and Rationality, 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)

Refining query previews techniques for data with multivalued attributes: the case of NASA EOSDIS - Plaisant, Catherine; Venkatraman,M.; Ngamkajorwiwat,K.; Barth,R.; Harberts,B.; Feng,Wenlan (Research and Technology Advances in Digital Libraries, 1999. ADL '99. Proceedings. IEEE Forum on, 1999)
Query Previews allow users to rapidly gain an understanding of the content and scope of a digital data collection. These previews present overviews of abstracted metadata, enabling users to rapidly and dynamically avoid undesired data. We present our recent work on developing query previews for a variety of NASA EOSDIS situations. We focus on approaches that successfully address the challenge of multi-valued attribute data. Memory requirements and processing time associated with running these new solutions remain independent of the number of records in the dataset. We describe two techniques and their respective prototypes used to preview NASA Earth science data
Keywords: attribute; attributes; processing; collection; memory; computing; meta; data; data; abstracted; data; digital; data; multivalued; data; query; Earth; EOSDIS; NASA; libraries; geophysics; metadata; dataset; digital; NASA; previews; processing; requirements; multi-valued; Science; techniques; undesired; time; query

SIPR: A new framework for generating efficient code for sparse matrix computations - Pugh, William; Shpeisman,T. (Languages and Compilers for Parallel Computing, 1999)

Statistical biases in optic flow - Fermüller, Cornelia; Pless, R.; Aloimonos, J. (Computer Vision and Pattern Recognition, 1999. IEEE Computer Society Conference on., 1999)
The computation of optical flow from image derivatives is biased in regions of non uniform gradient distributions. A least-squares or total least squares approach to computing optic flow from image derivatives even in regions of consistent flow can lead to a systematic bias dependent upon the direction of the optic flow, the distribution of the gradient directions, and the distribution of the image noise. The bias a consistent underestimation of length and a directional error. Similar results hold for various methods of computing optical flow in the spatiotemporal frequency domain. The predicted bias in the optical flow is consistent with psychophysical evidence of human judgment of the velocity of moving plaids, and provides an explanation of the Ouchi illusion. Correction of the bias requires accurate estimates of the noise distribution; the failure of the human visual system to make these corrections illustrates both the difficulty of the task and the feasibility of using this distorted optic flow or undistorted normal flow in tasks requiring higher lever processing
Keywords: Distributed computing; Frequency domain analysis; HUMANS; image derivatives; Image motion analysis; Image sequences; Least squares methods; Motion estimation; Optical computing; Optical distortion; optical flow; Optical noise; Ouchi illusion; perception of motion; Psychology; Spatiotemporal phenomena; statistical analysis; systematic bias; total least squares

Temporal, geographical and categorical aggregations viewed through coordinated displays: a case study with highway incident data - Fredrikson,Anna; North,Chris; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 1999 workshop on new paradigms in information visualization and manipulation in conjunction with the eighth ACM internation conference on Information and knowledge management, 1999)
Information visualization displays can hold a limited number of data points, typically a few thousand, before they get crowded. One way to solve this problem with larger data sets is to create aggregates. Aggregations were used together with the Snap-Together Visualization system to coordinate the visual displays of aggregates and their content. If two displays each hold one thousand items then rapid access and visibility can be maintained for a million points. This paper presents examples based on a database of highway incident data.

Temporal visualization for legal case histories - Harris,C.; Allen,R.B.; Plaisant, Catherine; Shneiderman, Ben (PROCEEDINGS OF THE ANNUAL MEETING-AMERICAN SOCIETY FOR INFORMATION SCIENCE, 1999)
This paper discusses visualization of legal information using a tool for temporal information called LifeLines. The direct and indirect histories of cases can become very complex. We explored ways that LifeLines could aid in viewing the links between the original case and the direct and indirect histories. The Apple Computer, Inc. v. Microsoft Corporation and Hewlett Packard Company case is used to illustrate the prototype. For example, if users want to find out how the rulings or statutes changed throughout this case, they could retrieve this information within a single display. Using the timeline, users could also choose at which point in time they would like to begin viewing the case. LifeLines support various views of a case's history. For instance, users can view the trial history of a case, the references involved in a case, and citations made to a case. The paper describes improvements to LifeLines that could help in providing a more useful visualization of case history.

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals - Hannenhalli, Sridhar; Pevzner,Pavel A. (J. ACM, 1999)
Genomes frequently evolve by reversals &rgr;(i,j) that transform a gene order &pgr;1 … &pgr;i&pgr;i+1 … &pgr;j-1&pgr;j … &pgr;n into &pgr;1 … &pgr;i&pgr;j-1 … &pgr;i+1&pgr;j … &pgr;n. Reversal distance between permutations &pgr; and &sgr;is the minimum number of reversals to transform &pgr; into &Agr;. Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of Drosophilia. Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. We study sorting of signed permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA. The previously suggested approximation algorithms for sorting signed permutations by reversals compute the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a “hidden” parameter that allows one to compute the reversal distance between signed permutations in polynomial time.
Keywords: Computational Biology; Genetics

Using a goal-driven approach to generate test cases for GUIs - Memon, Atif M.; Pollack,M. E; Soffa,M. L (Software Engineering, 1999. Proceedings of the 1999 International Conference on, 1999)
The widespread use of GUIs for interacting with software is leading to the construction of more and more complex GUIs. With the growing complexity comes challenges in testing the correctness of a GUI and the underlying software. We present a new technique to automatically generate test cases for GUIs that exploits planning, a well developed and used technique in artificial intelligence. Given a set of operators, an initial state and a goal state, a planner produces a sequence of the operators that will change the initial state to the goal state. Our test case generation technique first analyzes a GUI and derives hierarchical planning operators from the actions in the GUI. The test designer determines the preconditions and effects of the hierarchical operators, which are then input into a planning system. With the knowledge of the GUI and the way in which the user will interact with the GUI, the test designer creates sets of initial and goal states. Given these initial and final states of the GUI, a hierarchical planner produces plans, or a set of test cases, that enable the goal state to be reached. Our technique has the additional benefit of putting verification commands into the test cases automatically. We implemented our technique by developing the GUI analyzer and extending a planner. We generated test cases for Microsoft's Word-Pad to demonstrate the viability and practicality of the approach.
Keywords: Artificial intelligence; automatic test case generation; goal state; goal-driven approach; Graphical user interfaces; GUIs; hierarchical planning operators; initial state; Microsoft Word-Pad; operators; planning (artificial intelligence); program testing; software; verification commands

3D spatial layouts using a-teams - Sachdev,S.; Paredis,C. J. J.; Gupta,S.K.; Talukdar,S. N. (1998)
Spatial layout is the problem of arranging a set of componentsin an enclosure such that a set of objectives and constraints is sat- isfied. The constraints may include non-interference of objects, accessibility requirements and connection cost limits. Spatial lay- out problems are found primarily in the domains of electrical en- gineering and mechanical engineering in the design of integrated circuits and mechanical or electromechanical artifacts. Traditional approaches include ad-hoc (or specialized) heuristics, Genetic Al- gorithms and Simulated Annealing. The A-Teams approach pro- vides a way of synergistically combining these approaches in a modular agent based fashion. A-Teams are also open to the addi- tion of new agents. Modifications in the task requirements trans- late to modifications in the agent mix. In this paper we describe how modular A-Team based optimization can be used to solve 3 dimensional spatial layout problems.

Approximating large convolutions in digital images - Kanungo,T.; Mount, Dave; Netanyahu,N. S; Piatko,C.; Silverman,R.; Wu,A. Y (PROCEEDINGS-SPIE THE INTERNATIONAL SOCIETY FOR OPTICAL ENGINEERING, 1998)
Computing discrete two-dimensional convolutions is an important problem in image processing. In mathematicalmorphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0{1 valued function. This operation can be quite costly, especially when large kernels are involved. In this paper, we present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some exibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satis es certain reasonable requirements. We say that such a convolution is valid. Given this exibility we show that it is possible to compute binary convolutions more e ciently than would normally be possible for large kernels. Our main result is an algorithm, which given an m n image and a k-sided convex polygonal kernel, computes a valid convolution in time O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's line-drawing algorithm and pre x-sums to update the convolution e ciently as the kernel is moved from one position to another across the image.

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

Bringing treasures to the surface: previews and overviews in a prototype for the Library of Congress National Digital Library - Plaisant, Catherine; Marchionini,Gary; Komlodi,Anita (CHI 98 conference summary on Human factors in computing systems, 1998)
Keywords: Browsing; digital libraries; metadata; multimedia; overviews; previews; World Wide Web

Capturing articulation in assemblies from component geometry - Sinha,R.; Paredis,C. J. J.; Gupta,S.K.; Khosla,P. K. (1998)
This paper presents a method to extract instantaneous artic-ulation from part geometry, based on surface mating constraints as well as constraints imposed by other incidental contacts. Many assemblies contain joints, each of which have degrees of freedom associated with them. These joints allow the relative positions of parts in the mechanism to change as the joints are articulated. Being able to represent these joints and their behav- ior is important from the designers perspective because it enables him or her to verify whether kinematic requirements have been met.Therefore, it is useful to be able to obtain such joint informa- tion directly from part geometry and contact physics. The method presented here handles all lower pairs of kine- matic joints. Surface mating contacts are classified into one of three types: planar, spherical and cylindrical. The contacts are represented by algebraic inequalities describing the translational and angular velocities at the contact. Non-penetration conditions are written for a finite set of points on the boundary of each contact face, and it is shown that the finite set of conditions is representative of the entire boundary and the region enclosed by the boundary. Simultaneous satisfaction of the non-penetration conditions at all the contact surfaces between a pair of bodies is represented by a 6-dimensional simplex, which can be solved using linear programming.

Comparing detection methods for software requirements inspections: A replication using professional subjects - Porter, Adam; Votta,L. (Empirical Software Engineering, 1998)

Computational Models for the Formation of Protocell Structures - Peng,L. E.Y; Reggia, James A. (Artificial Life, 1998)

Constraint-based array dependence analysis - Pugh, William; Wonnacott,David (ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst., 1998)

Conversational Adequacy: Mistakes are the Essence - Perlis, Don; Purang,Khemdut (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
We argue that meta-dialog and meta-reasoning, far from beingof only occasional use, are the very essence of conversation and communication between agents. We give four paradigm examples of massive use of meta-dialog where only limited base dialog may be present, and use these to bolster our claim of centrality for meta-dialog. We further illustrate this with related work in active logics. We argue moreover that there may be a core set of meta-dialog principles that is in some sense complete. If we are right, then implementing such a set would be of considerable interest. We give examples of existing computer programs that converse inadequately according to our guidelines. (Also cross-referenced as UMIACS-TR-96-41)
Keywords: Technical Report

Data object and label placement for information abundant visualizations - Li,Jia; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 1998 workshop on New paradigms in information visualization and manipulation, 1998)
Keywords: control panel; data object placement; Information Visualization; label placement; metrics; timelines; visual feedback

De-amortization of Algorithms - Rao Kosaraju,S.; Pop, Mihai (Computing and CombinatoricsComputing and Combinatorics, 1998)
De-amortization aims to convert algorithms with excellent overall speed, f ( n ) for performing n operations, into algorithms that take no more than O ( f ( n )/ n ) steps for each operation. The paper reviews several existing techniques for de-amortization of algorithms.

Defaults Denied - Miller,Michael; Perlis, Don; Purang,Khemdut (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
We take a tour of various themes in default reasoning, examining new ideasas well as those of Brachman, Delgrande, Poole, and Schlechta. An underlying issue is that of stating that a potential default principle is not appropriate. We see this arise most dramatically as a problem in an attempt to formalize what are often loosely called "prototypes", although it also arises in other formal approaches to default reasoning. Some formalisms in the literature provide solutions but not without costs. We propose a formalism that appears to avoid these costs; it can be seen as a step toward a population-based set-theoretic modification of these approaches, that may ultimately provide a closer tie to recent work on statistical (quantitative) foundations of (qualitative) defaults([1]). Our analysis in particular indicates the need to resolve a conflation between use and mention in many default formalisms. Our treatment proposes such a resolution, and also explores the use of sets toward a more population-based notion of default. (Also cross-referenced as UMIACS-TR-96-61)
Keywords: Technical Report

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

Designing to facilitate browsing: A look back at the Hyperties workstation browser - Shneiderman, Ben; Plaisant, Catherine; Botafogo,Rodrigo; Hopkins,Don; Weiland,William (Technical Reports of the Computer Science Department, University of Maryland, 1998)
Since browsing hypertext can present a formidable cognitivechallenge, user interface design plays a major role in determining acceptability. In the Unix workstation version of Hyperties, a research-oriented prototype, we focussed on design features that facilitate browsing. We first give a general overview of Hyperties and its markup language. Customizable documents can be generated by the conditional text feature that enables dynamic and selective display of text and graphics. In addition we present: - an innovative solution to link identification: pop-out graphical buttons of arbitrary shape. - application of pie menus to permit low cognitive load actions that reduce the distraction of common actions, such as page turning or window selection. - multiple window selection strategies that reduce clutter and housekeeping effort. We preferred piles-of-tiles, in which standard-sized windows were arranged in a consistent pattern on the display and actions could be done rapidly, allowing users to concentrate on the contents. (Also cross-referenced as CAR-TR-494)
Keywords: Technical Report

Distance learning: is it the end of education as most of us know it? - Laurillard,Diana; Preece,Jenny; Shneiderman, Ben; Neal,Lisa; Wærn,Yvonne (CHI 98 conference summary on Human factors in computing systems, 1998)
Keywords: distance learning; education; Internet; Web

Drawing of Two-Dimensional Irregular Meshes - Aggarwal,Alok; Rao Kosaraju,S.; Pop, Mihai (Graph DrawingGraph Drawing, 1998)
We present a method for transforming two-dimensional irregular meshes into square meshes with only a constant blow up in area. We also explore context invariant transformations of irregular meshes into square meshes and provide a lower bound for the transformation of down-staircases.

Exploring LifeLines to Visualize Patient Records - Plaisant, Catherine; Rose,Anne (Technical Reports of the Computer Science Department, 1998)
LifeLines provide a general visualization environment for personalhistories. We explored its use for medical patient records. A one screen overview of the record using timelines provides direct access to the data. Problems, hospitalization and medications can be represented as horizontal lines, while icons represent discrete events such as physician consultations (and progress notes) or tests. Line color and thickness can illustrate relationships or significance. Techniques are described to display large records. Rescaling tools and filters allow users to focus on part of the information, revealing more details. Computerized medical records pose tremendous problems to system developers. Infrastructure and privacy issues need to be resolved before physicians can even start using the records. Non-intrusive hardware is required for physicians to do their work (i.e. interview patients) away from their desk and cumbersome workstations. But all the efforts to solve those problems will only succeed if appropriate attention is also given to the user interface design [1][8]. Long lists to scroll, clumsy search, endless menus and lengthy dialogs will lead to user rejection. But techniques are being developed to summarize, filter and present large amount of information, leading us to believe that rapid access to needed data is possible with careful design. While more attention is now put on developing standards for gathering medical records we found that very little effort had been made to design appropriate visualization and navigation techniques to present and explore personal history records. An intuitive approach to visualizing histories is to use graphical time series. The consistent, linear time scale allows comparisons and relations between the quantities displayed. Data can be graphed on the timeline to show time series of quantitative data. Highly interactive interfaces turn the display into a meaningfully structured menu with direct access to the data needed to review a problem or conduct the diagnosis. Also cross-referenced as CAR-TR-819
Keywords: Technical Report

Facilitating Network Data Exploration with Query Previews: A Study of User Performance and Preference - Tanin,Egemen; Lotem,Amnon; Haddadin,Ihab; Shneiderman, Ben; Plaisant, Catherine; Slaughter,Laura (Technical Reports of the Computer Science Department, 1998)
Current network data exploration systems which use command languages (e.g.SQL) or form fill-in interfaces fail to give users an indication of the distribution of data items. This leads many users to waste time posing queries which have zero-hit or mega-hit result sets. Query previewing is a novel visual approach for browsing huge networked information warehouses. Query previews supply data distribution information about the database that is being searched and give continuous feedback about the size of the result set for the query as it is being formed. Our within-subjects empirical comparison studied 12 subjects using a form fill-in interface with and without query previews. We found statistically significant differences showing that query previews sped up performance 1.6 to 2.1 times and led to higher subjective satisfaction. (Also cross-referenced as UMIACS-98-14)
Keywords: Technical Report

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.

Incorporating String Search in a Hypertext System:User Interface and Signature File Design Issues - Faloutsos,Christos; Lee,Raymond; Plaisant, Catherine; Shneiderman, Ben (Technical Reports of the Computer Science Department, 1998)
Hypertext systems provide an appealing mechanism forinformally browsing databases by traversing selectable links. However, in many fact finding situations string search is an effective complement to browsing. This paper describes the application of the signature file method to achieve rapid and convenient string search in small personal computer hypertext environments. The method has been implemented in a prototype, as well as in a commercial product. Performance data for search times and storage space are presented from a commercial hypertext database. User interface issues are then discussed. Experience with the string search interface indicates that it was used sucessfully by novice users. (Also cross-referenced as CAR-TR-448)
Keywords: Technical Report

An information architecture to support the visualization of personal histories - Plaisant, Catherine; Shneiderman, Ben; Mushlin,Rich (Information Processing & Management, 1998)
This paper proposes an information architecture for personal history data and describes how the data model can be extended to a runtime model for a compact visualization using graphical timelines. Our information architecture was developed for juvenile justice and medical patient records, but is usable in other application domains such as personal resumes, financial histories, or customer support. Our model groups personal history events into aggregates that are contained in facets (e.g., doctor visits, hospitalizations, or lab tests). Crosslinks enable representation of arbitrary relationships across events and aggregates. Data attributes, such as severity, can be mapped by data administrators to visual attributes such as color and line thickness. End-users have powerful controls over the display contents, and they can modify the mapping to fit their tasks.
Keywords: Graphical user interfaces; Information Visualization; LifeLines; medical patient record; personal histories; temporal data; timelines

Information visualization advanced interface and Web design - Shneiderman, Ben; Plaisant, Catherine (CHI 98 conference summary on Human factors in computing systems, 1998)

Integrated design and rapid manufacturing over the Internet - Rajagopalan,S.; Pinilla,J. M.; Losleben,P.; Tian,Q.; Gupta,S.K. (1998)
An Internet-based infrastructure is being developed inorder to provide designers with access to multiple layered- manufacturing services. The design domain being addressed is that of small mechanisms or electro-mechanical assemblies that would be used in robots or other mechatronic devices. The approach presented relies on the formalization of the data exchange interface between designers and manufacturers. The primary operatives in this system are Design Clients, Manufacturing Services and Process Brokers. The Design Client allows designers to submit completed designs for algorithmic decomposition, or alternately, to compose a design from primitives and library components that have been primed with some process-related information. During this early phase, the Manufacturing Service consists of a highly automated machine that can be used to build ceramic parts, and the associated software components for design decomposition, process planning and machine control. In later phases, multiple service providers will be made accessible. The Process Broker implements a number of supporting services including process selection and optimal part orientation. Future broker services will include manufacturability analysis, directory services and accreditation etc. Currently, this interface is being built and evaluated internally at Stanford and CMU. It will be made available for use by other selected universities in the near future.

An intelligent environment for simulating mechanical assembly operations - Gupta,S.K.; Paredis,C. J. J.; Sinha,R.; Wang,C. H.; Brown,P. F. (1998)
Rapid technical advances in many different areas of scientificcomputing provide the enabling technologies for creating a com- prehensive simulation and visualization environment for assembly design and planning. We have built an intelligent environment in which simple simulations can be composed together to create com- plex simulations for detecting potential assembly problems. Our goal in this project is to develop high fidelity assembly simulation and visualization tools that can detect assembly related problems without going through physical mock-ups. In addition, these tools can be used to create easy-to-visualize instructions for performing assembly and service operations.

Interfaces and tools for the library of congress national digital library program - Marchionini,Gary; Plaisant, Catherine; Komlodi,Anita (Information Processing & Management, 1998)
This paper describes a collaborative effort to explore user needs in a digital library, develop interface prototypes for a digital library and suggest and prototype tools for digital librarians and users at the Library of Congress (LC). Interfaces were guided by an assessment of user needs and aimed to maximize interaction with primary resources and support both browsing and analytical search strategies. Tools to aid users and librarians in overviewing collections, previewing objects and gathering results were created and serve as the beginnings of a digital librarian toolkit. The design process and results are described and suggestions for future work are offered.

Life cycle of user interface techniques: The DJJ information system design Process - Rose,Anne; Ellis,Jason; Plaisant, Catherine; Greene,Stephan (Technical Reports of the Computer Science Department, 1998)
To take advantage of todays technology, many organizations are migrating fromtheir legacy systems. With help from the Human-Computer Interaction Laboratory (HCIL) and Cognetics Corporation, the Maryland Department of Juvenile Justice (DJJ) is currently undergoing an effort to redesign their information system to take advantage of graphical user interfaces. As a research lab, HCIL identifies interesting research problems and then prototypes solutions. As a project matures, the exploratory prototypes are adapted to suit the end product requirements. This case study describes the life cycle of three DJJ prototypes: (1) LifeLines, which uses time lines to display an overview of a youth in one screen, (2) the DJJ Navigator, which helps manage individual workloads by displaying different user views, and (3) the ProgramFinder, a tool for selecting the best program for a youth. (Also cross-referenced as CAR-TR-826)
Keywords: Technical Report

LifeLines: using visualization to enhance navigation and analysis of patient records - Plaisant, Catherine; Mushlin,R.; Snyder,A.; Li,J.; Heller,D.; Shneiderman, Ben (In Proceedings of the 1998 American Medical Informatic Association Annual Fall SymposiumProc AMIA Symp, 1998)
LifeLines provide a general visualization environment for personal histories. We explore its use for clinical patient records. A Java user interface is described, which presents a one-screen overview of a computerized patient record using timelines. Problems, diagnoses, test results or medications can be represented as dots or horizontal lines. Zooming provides more details; line color and thickness illustrate relationships or significance. The visual display acts as a giant menu, giving direct access to the data.

LifeLines: using visualization to enhance navigation and analysis of patient records. - Plaisant, Catherine; Mushlin,R.; Snyder,A.; Li,J.; Heller,D.; Shneiderman, Ben (Proceedings of the AMIA Symposium, 1998)
LifeLines provide a general visualization environment for personal histories. We explore its use for clinical patient records. A Java user interface is described, which presents a one-screen overview of a computerized patient record using timelines. Problems, diagnoses, test results or medications can be represented as dots or horizontal lines. Zooming provides more details; line color and thickness illustrate relationships or significance. The visual display acts as a giant menu, giving direct access to the data.

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

Salient Frame Detection for Molecular Dynamics Simulations - Kim,Y.; Patro,R.; Ip,C. Y; O’Leary,D. P; Anishkin,A.; Sukharev,S.; Varshney, Amitabh (Scientific Visualization: Interactions, Features, Metaphors, 1998)
Saliency-based analysis can be applied to time-varying 3D datasetsfor the purpose of summarization, abstraction, and motion analysis. As the sizes of time-varying datasets continue to grow, it becomes more and more difficult to comprehend vast amounts of data and information in a short period of time. Au- tomatically generated thumbnail images and previewing of time-varying datasets can help viewers explore and understand the datasets significantly faster as well as provide new insights. In this paper, we introduce a novel method for detect- ing salient frames for molecular dynamics simulations. Our method effectively detects crucial transitions in simulated mechanosensitive ion channel (MscS), in agreement with experimental data.

Specification-based Testing of Reactive Software: A Case Study in Technology Transfer - Jategaonkar Jagadeesan,L.; Porter, Adam; Puchol,C.; Ramming,J. C; Votta,L. G. (Journal of Systems and Software, 1998)

Stabbing Orthogonal Objects in 3-Space - Mount, Dave; Pu,Fan-Tao (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
We consider a problem that arises in the design of data structuresfor answering {\em visibility range queries}, that is, given a $3$-dimensional scene defined by a set of polygonal patches, we wish to preprocess the scene to answer queries involving the set of patches of the scene that are visible from a given range of points over a given range of viewing directions. These data structures recursively subdivide space into cells until some criterion is satisfied. One of the important problems that arise in the construction of such data structures is that of determining whether a cell represents a nonempty region of space, and more generally computing the size of a cell. In this paper we introduce a measure of the {\em size} of the subset of lines in 3-space that stab a given set of $n$ polygonal patches, based on the maximum angle and distance between any two lines in the set. Although the best known algorithm for computing this size measure runs in $O(n^2)$ time, we show that if the polygonal patches are orthogonal rectangles, then this measure can be approximated to within a constant factor in $O(n)$ time. (Also cross-referenced as UMIACS-TR-96-71)
Keywords: Technical Report

Understanding Transportation Management Systems Performance with a Simulation-Based Learning Environment - Plaisant, Catherine; Tarnoff,Phil; Saraf,Aditya; Rose,Anne (Technical Reports of the Computer Science Department, 1998)
We have developed a simulation-based learning environment to provide systemdesigners and operators with an appreciation of the impact of incidents on traffic delay. We used an application framework developed at the University of Maryland for constructing simulation-based learning environments called SimPLE (Simulated Processes in a Learning Environment). Environments developed with SimPLE use dynamic simulations and visualizations to represent realistic time-dependent behavior and are coupled with guidance material and other software aids that facilitate learning. The simulation allows learners to close freeway lanes and divert traffic to an arterial road. Users can see the effect of the detour on freeway and arterial delay. Users can then adjust signal timing interactively on a time space diagram and watch the effect of their adjustment on green band changes and on arterial delays and total delays.
Keywords: Technical Report

Updating Discourse Context with Active Logic - Gurney,John; Purang,Khemdut; Perlis, Don (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
In this paper we present our implementation of a system of active logicthat processes natural language discourses. We focus on problems that involve presupposition and the associated well-known problems of the projection of presupposition. We discuss Heim's largely successful theory of presupposition and point out certain limitations. We then use these observations to build our discourse processor based on active logic. Our main contributions are the handling of problems that go beyond the scope of Heim's theory , especially discourses the involve cancellation of presupposition. Ongoing work suggests that conversational implicature and the cancellation of implicature can also be treated by our methods. Key words: presupposition, discourse, con text, accommodation, active logic, implicature. (Also cross-referenced as UMIACS-TR-96-62)
Keywords: Technical Report

User Interface Reengineering: A Diagnostic Approach - Vanniamparampil,Ajit J; Shneiderman, Ben; Plaisant, Catherine; Rose,Anne (Technical Reports of the Computer Science Department, 1998)
User interface technology has advanced rapidly in recent years.Incorporating new developments in existing systems could result in substantial improvements in usability, thereby improving performance and user satisfaction, while shortening training an d reducing error rates. Our focus is on low-effort high-payoff improvements to aspects such as data display and entry, consistency, messages, documentation, and system access. This paper provides guidelines for managers and designers responsible for use r interface reengineering, based on the experience we gained from six projects, and compiles our observations, recommendations and outcomes. (Also cross-referenced as CAR-TR-767)
Keywords: Technical Report

Viewing personal history records: A comparison of tabular format and graphical presentation using LifeLines - Alonso,Diane Lindwarm; Rose,Anne; Plaisant, Catherine; Norman,Kent L (Behaviour & Information Technology, 1998)
Thirty-six participants used a static version of either LifeLines, a graphical interface, or a tabular representation to answer questions about a database of temporal personal history information. Results suggest that overall the LifeLines representation led to much faster response times, primarily for questions which involved interval comparisons and making intercategorical connections. A 'first impression' test showed that LifeLines can reduce some of the biases of the tabular record summary. A post-experimental memory test led to significantly (p< 0.004) higher recall for LifeLines. Finally, simple interaction techniques are proposed to compensate for the problems of the static LifeLines display's ability to deal with precise dates, attribute coding and overlaps.Thirty-six participants used a static version of either LifeLines, a graphical interface, or a tabular representation to answer questions about a database of temporal personal history information. Results suggest that overall the LifeLines representation led to much faster response times, primarily for questions which involved interval comparisons and making intercategorical connections. A 'first impression' test showed that LifeLines can reduce some of the biases of the tabular record summary. A post-experimental memory test led to significantly (p< 0.004) higher recall for LifeLines. Finally, simple interaction techniques are proposed to compensate for the problems of the static LifeLines display's ability to deal with precise dates, attribute coding and overlaps.

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

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

Anywhere, Anytime Code Inspections: Using the Web to Remove Inspection Bottlenecks in Large-Scale Software Development - Perpich,J. M.; Perry,D. E.; Porter, Adam; Votta,L. G.; Wade,M. W. (Software Engineering, International Conference on, 1997)
The dissemination of critical information and the synchronization of coordinated activities are critical problems in geographically separated, large-scale, software development. While these problems are not insurmountable, their solutions have varying trade-offs in terms of time, cost and effectiveness. Our previous studies have shown that the inspection interval is typically lengthened because of schedule conflicts among inspectors which delay the (usually) required inspection collection meeting.We present and justify a solution using an intranet web that is both timely in its dissemination of information and effective in its coordination of distributed inspectors. First, exploiting a naturally occurring experiment (reported here), we conclude that the asynchronous collection of inspection results is at least as effective as the synchronous collection of those results. Second, exploiting the information dissemination qualities and the on-demand nature of information retrieval of the web, and the platform independence of browsers, we built an inexpensive tool that integrates seamlessly into the current development process. By seamless we mean an identical paper flow that results in an almost identical inspection process.The acceptance of the inspection tool has been excellent. The cost savings just from the reduction in paper work and the time savings from the reduction in distribution interval of the inspection package (sometimes involving international mailings) have been substantial. These savings together with the seamless integration into the existing environment are the major factors for this acceptance. From our viewpoint as experimentalists, the acceptance came too readily. Therefore we lost our op portunity to explore this tool using a series of controlled experiments to isolate the underlying factors or its effectiveness. Nevertheless, by using historical data we can show that the new process is less expensive in terms of cost and at least as effective in terms of quality (defect detection effectiveness).
Keywords: asynchronous; natural occurring inspection experiment; automated support for inspections; code inspections: web-based; meetingless

Assessing software review meetings: results of a comparative analysis of two experimental studies - Porter, Adam; Johnson,P. M (IEEE Transactions on Software Engineering, 1997)
Software review is a fundamental tool for software quality assurance. Nevertheless, there are significant controversies as to the most efficient and effective review method. One of the most important questions currently being debated is the utility of meetings. Although almost all industrial review methods are centered around the inspection meeting, recent findings call their value into question. In prior research the authors separately and independently conducted controlled experimental studies to explore this issue. The paper presents new research to understand the broader implications of these two studies. To do this, they designed and carried out a process of “reconciliation” in which they established a common framework for the comparison of the two experimental studies, reanalyzed the experimental data with respect to this common framework, and compared the results. Through this process they found many striking similarities between the results of the two studies, strengthening their individual conclusions. It also revealed interesting differences between the two experiments, suggesting important avenues for future research
Keywords: Aggregates; Collaborative work; Computer Society; Costs; Helium; Inspection; inspection meeting; Job shop scheduling; Programming; reconciliation; Software development management; Software quality; software quality assurance; software review meeting assessment; Software reviews

Better approximation guarantees for job-shop scheduling - Goldberg,Leslie Ann; Paterson,Mike; Srinivasan, Aravind; Sweedyk,Elizabeth (Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 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

Browsing hierarchical data with multi-level dynamic queries and pruning - Kumar,Harsha P.; Plaisant, Catherine; Shneiderman, Ben (International Journal of Human-Computer Studies, 1997)
Users often must browse hierarchies with thousands of nodes in search of those that best match their information needs. ThePDQ Tree-browser(Pruning with Dynamic Queries) visualization tool was specified, designed and developed for this purpose. This tool presents trees in two tightly-coupled views, one a detailed view and the other an overview. Users can use dynamic queries, a method for rapidly filtering data, to filter nodes at each level of the tree. The dynamic query panels are user-customizable. Sub-trees of unselected nodes are pruned out, leading to compact views of relevant nodes. Usability testing of the PDQ Tree-browser, done with eight subjects, helped assess strengths and identify possible improvements. The PDQ Tree-browser was used in Network Management (600 nodes) and UniversityFinder (1100 nodes) applications. A controlled experiment, with 24 subjects, showed that pruning significantly improved performance speed and subjective user satisfaction. Future research directions are suggested.

Comprehension and object recognition capabilities for presentations of simultaneous video key frame surrogates - Slaughters,Laura; Shneiderman, Ben; Marchionini,Gary (Research and Advanced Technology for Digital LibrariesResearch and Advanced Technology for Digital Libraries, 1997)
The demand for more efficient browsing of video data is expected to increase as greater access to this type of data becomes available. This experiment looked at one technique for displaying video data using key frame surrogates that are presented as a ldquoslide showrdquo. Subjects viewed key frames for between one and four video clips simultaneously. Following this presentation, the subjects performed object recognition and gist comprehension tasks in order to determine human thresholds for divided attention between these multiple displays. It was our belief that subject performance would degrade as the number of slide shows shown simultaneously increased. For object recognition and gist comprehension tasks, a decrease in performance between the one slide show display and the two, three or four slide show displays was found. In the case of two or three video presentations, performance is about the same, and there remains adequate object recognition abilities and comprehension of the video clips. Performance drops off to unacceptable levels when four slide shows are displayed at once.

Consciousness as self-function - Perlis, Don (Journal of Consciousness Studies, 4, 1997)

Content-based Image Retrieval Using Composite Features - Kauniskangas,H.; Sauvola,J.; Pietikainen,M.; David Doermann (Proceedings of the 1997 Scandinavian Conference on Image Analysis, 1997)
In this paper, we demonstrate methods for content-based image retrieval problems utilizing a specially designed retrieval architecture implemented within the 'Intelligent Image Retrieval' system (IIR). The method consists of new image features in the retrieval context, including segmentation methods and use of image frames. They are combined in a unique way with color, texture, shape and localization information with a special data ion construction in a graphical user interface. The IIR system provides an efficient retrieval architecture utilizing a tailored query language, retrieval mechanisms and an object-oriented database enabling the use of complex data structures and relations needed for successful query processing. Functionality and performance of methods and architecture are illustrated with a series of tests using a database that consists of several hundred 'scene' images.

Editorial: Evaluation and assessment in software engineering - Kitchenham,B.; Brereton,P.; Budgen,D.; Linkman,S.; Almstrum,V. L; Pfleeger,S. L; Zelkowitz, Marvin V; Wallace,D. (Information and Software Technology, 1997)

An experiment to assess the cost-benefits of code inspections in large scale software development - Porter, Adam; Siy,H. P; Toman,C. A; Votta,L. G. (IEEE Transactions on Software Engineering, 1997)
We conducted a long term experiment to compare the costs and benefits of several different software inspection methods. These methods were applied by professional developers to a commercial software product they were creating. Because the laboratory for this experiment was a live development effort, we took special care to minimize cost and risk to the project, while maximizing our ability to gather useful data. The article has several goals: (1) to describe the experiment's design and show how we used simulation techniques to optimize it; (2) to present our results and discuss their implications for both software practitioners and researchers; and (3) to discuss several new questions raised by our findings. For each inspection, we randomly assigned three independent variables: (1) the number of reviewers on each inspection team (1, 2, or 4); (2) the number of teams inspecting the code unit (1 or 2); and (3) the requirement that defects be repaired between the first and second team's inspections. The reviewers for each inspection were randomly selected without replacement from a pool of 11 experienced software developers. The dependent variables for each inspection included inspection interval (elapsed time), total effort, and the defect detection rate. Our results showed that these treatments did not significantly influence the defect detection effectiveness, but that certain combinations of changes dramatically increased the inspection interval
Keywords: Analysis of variance; code inspection cost benefits; code unit; commercial software product; Computer Society; cost-benefit analysis; Costs; defect detection effectiveness; defect detection rate; Design optimization; experienced software developers; experiment design; independent variables; Inspection; inspection interval; inspection team; Laboratories; large scale software development; Large-scale systems; live development effort; long term experiment; professional aspects; professional developers; Programming; reviewers; simulation techniques; software cost estimation; software inspection methods; software practitioners; Software quality; Switches

Families of Stationary Patterns Producing Illusory Movement: Insights into the Visual System - Fermüller, Cornelia; Pless,Robert; Aloimonos, J. (Proceedings of the Royal Society of London. Series B: Biological SciencesProc. R. Soc. Lond. B, 1997)
A computational explanation of the illusory movement experienced upon extended viewing of Enigma, a static figure painted by Leviant, is presented. The explanation relies on a model for the interpretation of three–dimensional motion information contained in retinal motion measurements. This model shows that the Enigma figure is a special case of a larger class of figures exhibiting the same illusory movement and these figures are introduced here. Our explanation suggests that eye movements and/or accommodation changes cause weak retinal motion signals, which are interpreted by higher–level processes in a way that gives rise to these illusions, and proposes a number of new experiments to unravel the functional structure of the motion pathway.

Fundamental laws and assumptions of software maintenance - Porter, Adam (Empirical Software Engineering, 1997)

Graphical Tools and Techniques for Querying Document Databases - Sauvola,J.; David Doermann; Kauniskangas,H.; Shin,C.; Koivusaari,M.; Pietikainen,M. (BSDIA, 1997)

How to (plan to) meet a deadline between now and then - Nirkhe,M.; Kraus,S.; Miller,M.; Perlis, Don (Journal of Logic and Computation, 1997)

If your version control system could talk - Ball,T.; Kim,J. M; Porter, Adam; Siy,H. P (ICSE Workshop on Process Modelling and Empirical Studies of Software Engineering, 1997)

Implementing a performance forecasting system for metacomputing: the Network Weather Service - Wolski,Rich; Spring, Neil; Peterson,Chris (Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), 1997)
In this paper we describe the design and implementation of a system called the Network Weather Service (NWS) that takes periodic measurements of deliverable resource performance from distributed networked resources, and uses numerical models to dynamically generate forecasts of future performance levels. These performance forecasts, along with measures of performance fluctuation (e.g. the mean square prediction error) and forecast lifetime that the NWS generates, are made available to schedulers and other resource management mechanisms at runtime so that they may determine the quality-of-service that will be available from each resource.We describe the architecture of the NWS and implementations that we have developed and are currently deploying for the Legion [13] and Globus/Nexus [7] metacomputing infrastructures. We also detail NWS forecasts of resource performance using both the Legion and Globus/Nexus implementations. Our results show that simple forecasting techniques substantially outperform measurements of current conditions (commonly used to gauge resource availability and load) in terms of prediction accuracy. In addition, the techniques we have employed are almost as accurate as substantially more complex modeling methods. We compare our techniques to a sophisticated time-series analysis system in terms of forecasting accuracy and computational complexity.

Interpreting presuppositions using active logic: From contexts to utterances - Gurney,J.; Perlis, Don; Purang,K. (Computational Intelligence, 1997)

Iteration space slicing and its application to communication optimization - Pugh, William; Rosser,E. (Proceedings of the 11th international conference on Supercomputing, 1997)

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

Locally adaptive document skew detection - Sauvola,Jaakko J; David Doermann; Pietikaeinen,Matti (Proceedings of SPIE, 1997)
This paper proposes a new approach to the detection of local orientation and skew in document images. It is based on the observation that there are many documents where a single global estimate of the page skew is not sufficient. These documents require local adaptation to deal robustly with todays complex configurations of components on the page. The approach attempts to identify regions in the image which exhibit locally consistent physical properties and consistent physical properties and consistent orientation. To do this, we rapidly compute a coarse segmentation and delineate regions which differ with respect to layout and/or physical content. Each region is classified as text, graphics, mixed text/graphics, image or background using local features and additional features are extracted to estimate orientation. The local orientation decisions are propagated where appropriate to resolve ambiguity and to produce a global estimate of the skew for the page. The implementation of our algorithms is demonstrated on a set of images which have multiple regions with different orientations.

Low-effort, high-payoff user interface reengineering - Plaisant, Catherine; Rose,A.; Shneiderman, Ben; Vanniamparampil,A. J (IEEE Software, 1997)
Although increasingly sophisticated design methodologies for developing new user interfaces exist, low-effort, high-payoff user interface reengineering represents a new direction-and opportunity. Yet reengineering a working system is complex and risky because of the potential disruption to users and managers, their justifiable fear of change, and the lack of guarantees that such changes will be for the better. Our largely positive experiences with the projects described here lead us to believe that user interface reengineering is a viable and important process. Low effort, high-payoff improvement recommendations can probably be made for most existing systems. Nevertheless, a narrowly focused user interface reengineering plan may be inappropriate when the major problems lie outside the scope of the user interface, such as inadequate functionalities, frequent crashes, and network problems. Attempts at improving less severe problems while ignoring deeper ones may be perceived as insensitive by the users. In such cases it is important to consider either making similar short-term improvements for other parts of the systems or postponing short-term user interface reengineering in favour of a more complete system reengineering. Similarly, the need for interface stability might outweigh the benefits of the short-term improvements if a complete reengineering is planned for the near future. But most likely these proposed diagnostic strategies and opportunities for improvement are only a prelude to the much larger task of business reengineering, which implies extensive user interface reengineering
Keywords: Business process re-engineering; complete system reengineering; Design methodology; Error analysis; Hardware; inadequate functionalities; interface stability; iterative methods; low-effort high-payoff user interface reengineering; short-term improvements; short-term user interface reengineering; software engineering; Software testing; System analysis and design; System testing; systems re-engineering; User centered design; user centred design; User interfaces

Parallelizing and algorithm for visibility on polyhedral terrain - Teng,Y. A; Mount, Dave; Puppo,E.; Davis, Larry S. (International Journal of Computational Geometry and Applications, 1997)
The best known output-sensitive sequential algorithm for computing the viewshedon a polyhedral terrain from a given viewpoint was proposed by Katz, Overmars, and Sharir 10, and achieves time complexity O((k + n(n)) logn) where n and k are the input and output sizes respectively, and () is the inverse Ackermann's function. In this paper, we present a parallel algorithm that is based on the work mentioned above, and achieves O(log2 n) time complexity, with work complexity O((k +n(n)) logn) in a CREW PRAM model. This improves on previous parallel complexity while maintaining work e ciency with respect to the best sequential complexity known.