Visualizing digital library search results with categorical and hierarchical axes - Shneiderman, Ben; Feldman,David; Rose,Anne; Grau,Xavier Ferré (Proceedings of the fifth ACM conference on Digital libraries, 2000)
Digital library search results are usually shown as a textual list, with 10-20 items per page. Viewing several thousand search results at once on a two-dimensional display with continuous variables is a promising alternative. Since these displays can overwhelm some users, we created a simplified two-dimensional display that uses categorical and hierarchical axes, called hieraxes. Users appreciate the meaningful and limited number of terms on each hieraxis. At each grid point of the display we show a cluster of color-coded dots or a bar chart. Users see the entire result set and can then click on labels to move down a level in the hierarchy. Handling broad hierarchies and arranging for imposed hierarchies led to additional design innovations. We applied hieraxes to a digital video library of science topics used by middle school teachers, a legal information system, and a technical library using the ACM Computing Classification System. Feedback from usability testing with 32 subjects revealed strengths and weaknesses.
Keywords: categorical axes; digital libraries; Graphical user interfaces; hierarchy; hieraxes; Information Visualization

Visualizing high-dimensional predictive model quality - Rheingans,P.; desJardins, Marie (Visualization 2000. Proceedings, 2000)
Using inductive learning techniques to construct classification models from large, high-dimensional data sets is a useful way to make predictions in complex domains. However, these models can be difficult for users to understand. We have developed a set of visualization methods that help users to understand and analyze the behavior of learned models, including techniques for high-dimensional data space projection, display of probabilistic predictions, variable/class correlation, and instance mapping. We show the results of applying these techniques to models constructed from a benchmark data set of census data, and draw conclusions about the utility of these methods for model understanding.

Web Query Optimizer - Zadorozhny,Vladimir; Bright,Laura; Raschid, Louiqa; Urhan,Tolga; Vidal,Maria Esther (Data Engineering, International Conference on, 2000)
We demonstrate a Web Query Optimizer (WQO) within an architecture of mediators and wrappers, for WebSources of limited capability in a wide area environment. The WQO has several innovative features including a CBR (capability based rewriting) Tool, an enhanced randomized relational optimizer extended to a Web environment, and a WebWrapper cost model that can provide relevant metrics for accessing WebSources. The prototype has been tested against a number of WebSources.

WebView materialization - Labrinidis,Alexandros; Roussopoulos, Nick (SIGMOD Rec., 2000)
A WebView is a web page automatically created from base data typically stored in a DBMS. Given the multi-tiered architecture behind database-backed web servers, we have the option of materializing a WebView inside the DBMS, at the web server, or not at all, always computing it on the fly (virtual). Since WebViews must be up to date, materialized WebViews are immediately refreshed with every update on the base data. In this paper we compare the three materialization policies (materialized inside the DBMS, materialized at the web server and virtual) analytically, through a detailed cost model, and quantitatively, through extensive experiments on an implemented system. Our results indicate that materializing at the web server is a more scalable solution and can facilitate an order of magnitude more users than the virtual and materialized inside the DBMS policies, even under high update workloads.

The active MultiSync controller of the cubetree storage organization - Roussopoulos, Nick; Kotidis,Y.; Sismanis,Y. (ACM SIGMOD Record, 1999)

The Bible as a parallel corpus: Annotating the ‘Book of 2000 Tongues’ - Resnik, Philip; Olsen,M.B.; Diab,M. (Computers and the Humanities, 1999)

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

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

A comparative study of the backbone dynamics of two closely related lipid binding proteins: Bovine heart fatty acid binding protein and porcine ileal lipid binding protein - Lücke,Christian; Fushman, David; Ludwig,Christian; Hamilton,James A.; Sacchettini,James C.; Rüterjans,Heinz (Molecular and Cellular Biochemistry, 1999)
The backbone dynamics of bovine heart fatty acid binding protein (H-FABP) and porcine ileal lipid binding protein (ILBP) were studied by 15N NMR relaxation (T1 and T2) and steady state heteronuclear 15N1H NOE measurements. The microdynamic parameters characterizing the backbone mobility were determined using the ‘model-free’ approach. For H-FABP, the non-terminal backbone amide groups display a rather compact protein structure of low flexibility. In contrast, for ILBP an increased number of backbone amide groups display unusually high internal mobility. Furthermore, the data indicate a higher degree of conformational exchange processes in the µsec-msec time range for ILBP compared to H-FABP. These results suggest significant differences in the conformational stability for these two structurally highly homologous members of the fatty acid binding protein family.
Keywords: Biomedical and Life Sciences

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)

Creating a parallel corpus from the book of 2000 tongues - Resnik, Philip; Olsen,M.B.; Diab,M. (Computers and the Humanities, 1999)

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

Distinguishing systems and distinguishing senses: New evaluation methods for word sense disambiguation - Resnik, Philip; Yarowsky,D. (Natural language engineering, 1999)

DynaMat: a dynamic view management system for data warehouses - Kotidis,Y.; Roussopoulos, Nick (Proceedings of the 1999 ACM SIGMOD international conference on Management of data, 1999)

Interhemispheric effects on map organization following simulated cortical lesions - Levitan,S.; Reggia, James A. (Artificial intelligence in medicine, 1999)

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

Lesion effects in a bihemispheric letter-identification model - Shevtsova,N.; Reggia, James A. (Neural Networks, 1999. IJCNN'99. International Joint Conference on, 1999)

Mining the web for bilingual text - Resnik, Philip (Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, 1999)

A model of lateralization and asymmetries in cortical maps - Levitan,S.; Stoica,I.; Reggia, James A. (Neural Networks, 1999. IJCNN'99. International Joint Conference on, 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

A neural network model of lateralization during letter identification - Shevtsova,N.; Reggia, James A. (Journal of Cognitive Neuroscience, 1999)

New algorithmic aspects of the Local Lemma with applications to routing and partitioning - Leighton,Tom; Rao,Satish; Srinivasan, Aravind (Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, 1999)

Pathogenic mechanisms in ischemic damage: a computational study - Ruppin,E.; Ofer,E.; Reggia, James A.; Revett,K. (Computers in biology and medicine, 1999)

Penumbral tissue damage following acute stroke: a computational investigation - Ruppin,E.; Revett,K.; Ofer,E.; Goodall,S.; Reggia, James A. (Progress in brain research, 1999)

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

A Study of the Structure of the Web - Deshpande, Amol; Huang,R.; Raman,V.; Riggs,T.; Song,D.; Subramanian,L. (University of California, Berkeley, 1999)
The World Wide Web is a huge, growing repository of information on a wide range of topics. It is alsobecoming important, commercially and sociologically, as a place of human interaction within different communities. In this paper we present an experimental study of the structure of the Web. We analyze link topologies of various communities, and patterns of mirroring of content, on 1997 and 1999 snapshots of the Web. Our results give insight into patterns of interaction within communities and how they evolve, as well as patterns of data replication. We also describe the techniques we have developed for performing complex processing on this large data set, and our experiences in doing so. We present new algorithms for finding partial and complete mirrors in URL hierarchies; these are also of independent interest for search and redirection. In order to study and visualize link topologies of different communities, we have developed techniques to compact these large link graphs without much information loss.

Support for interactive document selection in cross-language information retrieval - Oard, Douglas; Resnik, Philip (Information Processing & Management, 1999)
As digital libraries grow to global scale, the provision of interactive access to content in many languages will become increasingly important. In systems that support query-based searching, the presence of multilingual content will affect both the search technology itself and the user interface components that support query formulation, document selection and query refinement. This article describes the interactions among these components and presents a practical way of evaluating the adequacy of the selection interface. A categorization-based model for the user's selection process is presented and an experimental methodology suitable for obtaining process centered results in this context is developed. The methodology is applied to assess the adequacy of a selection interface in which multiple candidate translations for a term can be simultaneously presented. The results indicate that the modeled selection process is somewhat less effective when users are presented with multi-translation glosses from Japanese to English rather than materials generated originally in English, but that users with access to the gloss translations substantially outperform a Naive Bayes classification algorithm.

Visualization of high-dimensional model characteristics - desJardins, Marie; Rheingans,Penny (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)
Using inductive learning techniques to construct explanatory models for large, high-dimensional data sets is a useful way to discover useful information. However, these models can be difficult for users to understand. We have developed a set of visualization methods that enable a user to evaluate the quality of learned models, to compare alternative models, and identify ways in which a model might be improved We describe the visualization techniques we have explored, including methods for high-dimensional data space projection, variable/class correlation, instance mapping, and model sampling We show the results of applying these techniques to several models built from a benchmark data set of census data.
Keywords: data mining and knowledge discovery; multidimensional information spaces; Visualization

An alternative storage organization for ROLAP aggregate views based on cubetrees - Kotidis,Y.; Roussopoulos, Nick (ACM Sigmod Record, 1998)

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

The Bible, Truth, and Multilingual OCR Evaluation - Kanungo,Tapas; Resnik, Philip (University of Maryland, College Park, 1998)
Multilingual OCR has emerged as an important information technology, thanks to the increasing need for cross-language information access. While many research groups and companies have developed OCR algorithms for various languages, it is difficult to compare the performance of these OCR algorithms across languages. This difficulty arises because most evaluation methodologies rely on the use of a document image dataset in each of the languages and it is difficult to find document datasets in different languages that are similar in content and layout. In this paper we propose to use the Bible as a dataset for comparing OCR accuracy across languages. Besides being available in a wide range of languages, Bible translation are closely parallel in content, carefully translated, surprisingly relevant with respect to modern-day language, and quite inexpensive. A project at the University of Maryland is currently implementing this idea. We have created a scanned image dataset with groundtruth from an Arabic Bible. We have also used image degradation models to create synthetically degraded images of a French Bible. We hope to generate similar Bible datasets for other languages, and we are exploring alternative corpora such as the Koran and the Bhagavad Gita that have similar properties. Quantitative OCR evaluation based on the Arabic Bible dataset is currently in progress.
Keywords: *BIBLE; *CORPUS; *DATASETS; *GROUNDTRUTH; *OPTICAL CHARACTER RECOGNITION; *TEST SETS; *TRANSLATIONS; accuracy; algorithms; CYBERNETICS; DOCUMENT IMAGES; DOCUMENTS; IMAGES; INFORMATION SCIENCE; LANGUAGE; linguistics; MULTILINGUAL OCR(OPTICAL CHARACTER RECOGNITION); SYMPOSIA; TEST AND EVALUATION

Buttons vs. menus: An exploratory study of pull-down menu selection as compared to button bars - Ellis,Jason; Tran,Chi; Ryoo,Jake; Shneiderman, Ben (Technical Reports of the Computer Science Department, 1998)
Button bars are a relatively new interaction method intended to speedup application use as compared to pull-down menus. This exploratory study compares three command selection methods: pull-down menus, button bars, and user choice of pull-down menus or button bars. Effectiveness was measured in two ways: speed of selection and error rate. 15 participants performed 15 word processor related tasks. Results show that in frequently used functions, such as character attribute selection (bold, italic, u nderline, etc.), button bars are faster. There were no statistically significant differences in error rates between the three interaction methods. (Also cross-referenced as CAR-TR-764)
Keywords: Technical Report

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

Clustering appearances of 3D objects - Basri,R.; Roth,D.; Jacobs, David W. (Computer Vision and Pattern Recognition, 1998. Proceedings. 1998 IEEE Computer Society Conference on, 1998)
We introduce a method for unsupervised clustering of images of 3D objects. Our method examines the space of all images and partitions the images into sets that form smooth and parallel surfaces in this space. It further uses sequences of images to obtain more reliable clustering. Finally, since our method relies on a non-Euclidean similarity measure we introduce algebraic techniques for estimating local properties of these surfaces without first embedding the images in a Euclidean space. We demonstrate our method by applying it to a large database of images
Keywords: 3D; clustering; image; clustering; sequences; images; unsupervised; objects; local; of; properties; reliable; recognition; sequences; object

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

Computational studies of lateralization of phoneme sequence generation - Reggia, James A.; Goodall,S.; Shkuro,Y. (Neural Computation, 1998)

The Cubetree Storage Organization - Roussopoulos, Nick; Kotidis,Y. (VLDB, 1998)

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.

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.

Equal Time for Data on the Internet with WebSemantics - Raschid,G. A.M.L; Tomasic,A. (Advances in Database Technology—EDBT'98, 1998)

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

Feature Recognition for Interactive Applications: Exploiting Distributed Resources - Regli,William C.; Gupta, Satyandra K.; Nau, Dana S. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
The availability of low-cost computational power is a drivingforce behind the growing sophistication of CAD software. Tools designed to reduce time-consuming build-test-redesign iterations are essential for increasing engineering quality and productivity. However, automation of the design process poses many difficult computational problems. As more downstream engineering activities are being considered during the design phase, guaranteeing reasonable response times within design systems becomes problematic. Design is an interactive process and speed is a critical factor in systems that enable designers to explore and experiment with alternative ideas during the design phase. Achieving interactivity requires an increasingly sophisticated allocation of computational resources in order to perform realistic design analyses and generate feedback in real time. This paper presents our initial efforts to develop techniques to apply distributed algorithms to the problem of recognizing machining features from solid models. Existing work on recognition of features has focused exclusively on serial computer architectures. Our objective is to show that distributed algorithms can be employed on realistic parts with large numbers of features and many geometric and topological entities to obtain significant improvements in computation time using existing hardware and software tools. Migrating solid modeling applications toward a distributed computing framework enables interconnection of many of the autonomous and geographically diverse software tools used in the modern manufacturing enterprise. (Also cross-referenced as UMIACS-TR-94-126.1)
Keywords: Technical Report

The function of documents - David Doermann; Rivlin,Ehud; Rosenfeld,Azriel (Image and Vision Computing, 1998)
The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper, we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval.To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.
Keywords: Document functionality; Information transfer

IMACS: a case study in real-world planning - Gupta,S.K.; Nau, Dana S.; Regli,W. C. (Intelligent Systems and their Applications, IEEE, 1998)
This article discusses the complexities of real-world planning and how to create planning systems to address them. IMACS (Interactive Manufacturability Analysis and Critiquing System), an automated designer's aid, evaluates machined parts and suggests design modifications to improve their manufacturability, offering advantages over the planning techniques used in classical planning systems
Keywords: automated designer's aid; CAD/CAM; case study; computer aided analysis; computer aided production planning; design modifications; IMACS; intelligent design assistants; Interactive Manufacturability Analysis and Critiquing System; interactive systems; machined parts evaluation; machining; manufacturability; planning (artificial intelligence); planning systems

Improved bounds and algorithms for hypergraph two-coloring - Radhakrishnan,J.; Srinivasan, Aravind (39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings, 1998)
We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn)×2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1)×2n due to Beck (1978). We further generalize this to a “local” version, improving on one of the first applications of the Lovasz Local Lemma
Keywords: algorithms; Application software; Approximation algorithms; bounds; computational geometry; Computer science; Contracts; Erbium; graph colouring; History; hypergraph two-coloring; Lab-on-a-chip; MATHEMATICS; n-uniform hypergraph; Parallel algorithms; Polynomials; probability

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.

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

Linger longer: Fine-grain cycle stealing for networks of workstations - Ryu, K. D; Hollingsworth, Jeffrey K (Proceedings of the 1998 ACM/IEEE Conference on Supercomputing (CDROM), 1998)

Logic knowledge bases with two default rules - Ruiz,C.; Minker, Jack (Annals of Mathematics and Artificial Intelligence, 1998)

Low Degree Spanning Trees of Small Weight - Khuller, Samir; Raghavachari,Balaji; Young,Neal (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
Given n points in the plane, the degree-K spanning tree problemasks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for K>2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree three whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree four whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d [greater than or equal to] 3, an arbitrary collection of points in DimD contains a spanning tree of degree three, whose weight is at most 5/3 times the weight of a minimum spanning tree. This is the first paper that achieves factors better than two for these problems. (Also cross-referenced as UMIACS-TR-94-1)
Keywords: Technical Report

Materialized views and data warehouses - Roussopoulos, Nick (ACM SIGMOD RecordSIGMOD Rec., 1998)

A Meta-Wrapper for Scaling up to Multiple Autonomous Distributed Information Sources - Vidal,Maria Esther; Raschid, Louiqa; Gruser,Jean Robert (Cooperative Information Systems, IFCIS International Conference on, 1998)
Abstract Current mediator and wrapper architectures do not have the flexibility to scale to multiple wrapped sources, where some sources may be redundant, and some sources may provide incomplete answers to a query. We propose a meta-wrapper component which is capable of handling multiple wrapped sources, in a particular domain, where the multiple sources provide related information. The meta-wrapper makes these sources transparent to the mediator, and provides a single meta-wrapper interface for all these sources. Source descriptions specify the content and query capability of the sources. These are used to determine the meta-wrapper interface and to decide which queries from a mediator can be accepted. Sources are partitioned into equivalence classes, based on their descriptions. These equivalence classes are partially ordered, and the lattices that correspond to these orderings are used to identify the relevant sources for a query submitted by the mediator. If there is redundancy of the sources, the meta-wrapper identifies alternate sources for the query. A meta-wrapper cost model is then used to select among alternate relevant sources and choose the best plan.
Keywords: information resource discovery; integration and interoperability; metadata use and management; wrappers and mediators

Modeling and evaluating design alternatives for an on-line instrumentation system: a case study - Waheed, A.; Rover, D. T; Hollingsworth, Jeffrey K (IEEE Transactions on Software Engineering, 1998)
This paper demonstrates the use of a model-based evaluation approach for instrumentation systems (ISs). The overall objective of this study is to provide early feedback to tool developers regarding IS overhead and performance; such feedback helps developers make appropriate design decisions about alternative system configurations and task scheduling policies. We consider three types of system architectures: network of workstations (NOW), symmetric multiprocessors (SMP), and massively parallel processing (MPP) systems. We develop a Resource OCCupancy (ROCC) model for an on-line IS for an existing tool and parameterize it for an IBM SP-2 platform. This model is simulated to answer several “what if” questions regarding two policies to schedule instrumentation data forwarding: collect-and-forward (CF) and batch-and-forward (BF). In addition, this study investigates two alternatives for forwarding the instrumentation data: direct and binary tree forwarding for an MPP system. Simulation results indicate that the BF policy can significantly reduce the overhead and that the tree forwarding configuration exhibits desirable scalability characteristics for MPP systems. Initial measurement-based testing results indicate more than 60 percent reduction in the direct IS overhead when the BF policy was added to Paradyn parallel performance measurement tool
Keywords: alternative system configurations; Application software; batch-and-forward; collect-and-forward; Computer aided software engineering; design alternatives; design decisions; Feedback; IBM SP-2 platform; Instruments; massively parallel processing; model-based evaluation approach; Monitoring; multiprocessing programs; on-line instrumentation system; Paradyn parallel performance measurement tool; PARALLEL PROCESSING; Real time systems; scalability characteristics; software metrics; software tools; Space technology; symmetric multiprocessors; system architectures; system monitoring; System testing; task scheduling policies; tool developers; tree forwarding configuration; Workstations

Multicommodity flow and circuit switching - Leighton,T.; Rao,S.; Srinivasan, Aravind (, Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998, 1998)
Given a set of request pairs in a network, the problem of routing virtual circuits with low congestion is to connect each pair by a path so that few paths use the same link in the network. We build on an earlier multicommodity flow based approach of Leighton and Rao (1996) to show that short flow paths lead to path selections with low congestion. This shows that such good path selections exist for constant-degree expanders with strong expansion, generalizing a result of (Broder et al., 1994). We also show, for infinitely many n, n-vertex undirected graphs Gn along with a set T of connection requests, such that: T is fractionally realizable using flow-paths that impose a (fractional) congestion of at most 1; but any rounding of such a flow to the given set of flow-paths, leads to a congestion of Ω(log n/log log n). This is progress on a long-standing open problem
Keywords: Application software; Bandwidth; circuit switching; Computer science; constant-degree expanders; graph theory; High speed integrated circuits; Integrated circuit technology; Laboratories; low congestion; MATHEMATICS; multicommodity flow; National electric code; network routing; path selections; Routing; short flow paths; Switching circuits; switching theory; undirected graphs; virtual circuit routing

Optimization of wrappers and mediators for web accessible data sources (websources) - Bright,L.; Raschid, Louiqa; Vidal,M. E (Workshop Web Inf. Data Management (WIDM), Washington DC, 1998)

Parallel strands: A preliminary investigation into mining the web for bilingual text - Resnik, Philip (Machine Translation and the Information Soup, 1998)

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

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

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

Semantics for Disjunctive and Normal Disjunctive Logic Programs - Lobo,J.; Minker, Jack; Rajasekar,A. (Handbook of logic in artificial intelligence and logic programming, 1998)

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

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)

Spreading depression in focal ischemia: A computational study - Revett,K.; Ruppin,E.; Goodall,S.; Reggia, James A. (Journal of Cerebral Blood Flow & Metabolism, 1998)

Techniques for update handling in the enhanced client-server DBMS - Delis,A.; Roussopoulos, Nick (IEEE Transactions on Knowledge and Data Engineering, 1998)
The Client-Server computing paradigm has significantly influenced the way modern Database Management Systems are designed and built. In such systems, clients maintain data pages in their main-memory caches, originating from the server's database. The Enhanced Client-Server architecture takes advantage of all the available client resources, including their long-term memory. Clients can cache server data into their own disk units if these data are part of their operational spaces. However, when updates occur at the server, a number of clients may need to not only be notified about these changes, but also obtain portions of the updates as well. In this paper, we examine the problem of managing server imposed updates that affect data cached on client disk managers. We propose a number of server update propagation techniques in the context of the Enhanced Client-Server DBMS architecture, and examine the performance of these strategies through detailed simulation experiments. In addition, we study how the various settings of the network affect the performance of these policies
Keywords: client disk managers; client resources; client-server computing paradigm; client-server systems; Computational modeling; Computer architecture; concurrency control; data pages; Database systems; distributed databases; enhanced client-server DBMS; Hardware; Local area networks; long-term memory; main-memory caches; Network servers; operational spaces; Personal communication networks; server update propagation techniques; Transaction databases; update handling; Workstations; Yarn

Time-Domain Extraction of Broad-Band Sources by Tikhonov-Phillips Regularization of Triangular Toeplitz Kernels* - Roginsky,Jacob; Stewart, G.W. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
Single receiver source deconvolution in a shallow waterenvironment is an ill-posed problem whose difficulty is compounded by the multipath nature of the propagation operator. If only sources that are quiescent prior to some initial time to are considered, the result of discretizatizing the problem in the time domain is an ill-conditioned triangular Toeplitz system. In this paper we show how an algorithm of Elden can be used to implement Tikhonov-Phillips regularization for this system. Unlike the multichannel deconvolution techniques used in underwater acoustics, this method can extract source signatures using the outputs of a single sensor. In addition, when the propagation is multipath and source signature extraction is performed as part of an optimization procedure for environmental inversion, we can work with shorter time windows so that the process becomes computationally more efficient than frequency domain deconvolution. A number of examples of the use of the Tikhonov-Philips regularization method for source series extraction are provided. (Also cross-referenced as UMIACS-TR-95-87)
Keywords: Technical Report

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

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

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

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.

When Two Hands Are Better Than One: Enhancing Collaboration Using Single Display Groupware. CHI’98 - Stewart,J.; Raybourn,E.; Bederson, Benjamin B.; Druin, Allison (Extended Abstracts, 1998)

WordNet and class-based probabilities - Resnik, Philip (WordNet: An electronic lexical database, 1998)

Wrapper generation for Web accessible data sources - Gruser,J.; Raschid, Louiqa; Vidal,M. E; Bright,L. (3rd IFCIS International Conference on Cooperative Information Systems, 1998. Proceedings, 1998)
There is an increase in the number of data sources that can be queried across the WWW. Such sources typically support HTML forms-based interfaces and search engines query collections of suitably indexed data. The data is displayed via a browser: One drawback to these sources is that there is no standard programming interface suitable for applications to submit queries. Second, the output (answer to a query) is not well structured. Structured objects have to be extracted from the HTML documents which contain irrelevant data and which may be volatile. Third, domain knowledge about the data source is also embedded in HTML documents and must be extracted. To solve these problems, we present technology to define and (automatically) generate wrappers for Web accessible sources. Our contributions are as follows: (1) Defining a wrapper interface to specify the capability of Web accessible data sources. (2) Developing a wrapper generation toolkit of graphical interfaces and specification languages to specify the capability of sources and the functionality of the wrapper (3) Developing the technology to automatically generate a wrapper appropriate to the Web accessible source, from the specifications.
Keywords: application program interfaces; data mining; Databases; Educational institutions; Electrical capacitance tomography; HTML; HTML documents; Internet; Query processing; Read only memory; Search engines; Specification languages; Uniform resource locators; World Wide Web; wrapper generation toolkit; WWW

Automated manufacturability analysis: A survey - Gupta, Satyandra K.; Regli,William C.; Das,Diganta; Nau, Dana S. (Research in Engineering Design, 1997)
In the market-place of the 21st century, there is no place for traditional ‘over-the-wall’ communications between design and manufacturing. In order to ‘design it right the very first time’, designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool — enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them.
Keywords: engineering

Automatic discovery of self-replicating structures in cellular automata - Lohn,J. D; Reggia, James A. (Evolutionary Computation, IEEE Transactions on, 1997)

Combining Closed World Assumptions with Stable Negation - Ruiz,Carolina; Minker, Jack (Fundamenta Informaticae, 1997)
We study the semantics of disjunctive logic programs that simultaneously contain multiple kinds of default negations. We introduce operators notG, notW, and notSTB in the language of logic programs to represent the Generalized Closed World Assumption, the Weak Generalized Closed World Assumption, and the stable negation, respectively. The notion of stratification involving different kinds of negations is defined and the meaning of stratified programs with multiple negations is described. The class of stratified programs is extended to the class of quasi-stratified programs and the semantics of the latest class is studied.

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

Computer models: A new approach to the investigation of disease - Reggia, James A.; Ruppin,E.; Berndt,R. S (MD Computing, 1997)

The distributed information search component (disco) and the world wide web - Naacke,H.; Kapitskaia,O.; Tomasic,A.; Bonnet,P.; Raschid, Louiqa; Amouroux,R. (Proc. of ACM SIGMOD Conf. on Management of Data, 1997)

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

Evaluating multilingual gisting of Web pages - Resnik, Philip (Association for the Advancement of Artificial Intelligence, 1997)

The Function of Documents - David Doermann; Rosenfeld, A.; Rivlin,E. (ICDAR, 1997)
The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval. To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.

Image Indexing with Minimum Adaptive Spatial Segmentation - Zhong,S.; David Doermann; Rosenfeld, A. (Proceedings of VISUAL 1997, 1997)

Implicit object constructions and the (in) transitivity continuum - Olsen,M.B.; Resnik, Philip (33rd Proceedings of the Chicago Linguistic Society, 1997)

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

A Language Identification Application Built on the Java Client/Server Platform - Adams,G.; Resnik, Philip (From Research to Commercial Applications: Making NLP Work in Practice, 1997)

Local correspondence for detecting random forgeries - Guo,J. K; David Doermann; Rosenfeld, A. (Document Analysis and Recognition, 1997., Proceedings of the Fourth International Conference on, 1997)
Progress on the problem of signature verification has advanced more rapidly in online applications than offline applications, in part because information which can easily be recorded in online environments, such as pen position and velocity, is lost in static offline data. In offline applications, valuable information which can be used to discriminate between genuine and forged signatures is embedded at the stroke level. We present an approach to segmenting strokes into stylistically meaningful segments and establish a local correspondence between a questioned signature and a reference signature to enable the analysis and comparison of stroke features. Questioned signatures which do not conform to the reference signature are identified as random forgeries. Most simple forgeries can also be identified, as they do not conform to the reference signature's invariant properties such as connections between letters. Since we have access to both local and global information, our approach also shows promise for extension to the identification of skilled forgeries
Keywords: applications; online; applications; questioned; correspondence; offline; detection; reference; extraction; handwriting; features; stroke; forged; forgeries; random; forgeries; stroke; Forgery; level; stroke; meaningful; processing; properties; local; recognition; image; segmentation; stylistically; segmentation; word; segments; feature; signature; random; signature; signature; signatures; invariant; verification; skilled

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

Model generation and state generation for disjunctive logic programs - Seipel,Dietmar; Minker, Jack; Ruiz,Carolina (The Journal of Logic Programming, 1997)
This paper investigates two fixpoint approaches for minimal model reasoning with disjunctive logic programs P. The first one, called model generation, is based on an operator TPINT defined on sets of Herbrand interpretations whose least fixpoint is logically equivalent to the set of minimal Herbrand models of the program. The second approach, called state generation, uses a fixpoint operation TPs based on hyperresolution. It operates on disjunctive Herbrand states, and its least fixpoint is the set of logical consequences of P, the so-called minimal model state of the program. We establish a useful relationship between hyperresolution by PPs and model generation by TPINT. Then we investigate the problem of continuity of the two operators TPs and TPINT. It is known that the operator TPs is continuous, and so it reaches its least fixpoint in at most ω iterations. On the other hand, the question of whether TPINT is continuous has been open. We show by a counterexample that TPINT is not continuous. Nevertheless, we prove that it converges towards its least fixpoint in at most ω iterations, too, as follows from the relationship that we show exists between hyperresolution and model generation. We define an iterative version of TPINT that computes the perfect model semantics of stratified disjunctive logic programs. On each stratum of the program, this operator converges in at most ω iterations. Model generations for the stable semantics and the partial stable semantics are respectively achieved by using this iterative operator together with the evidential transformation and the 3-S transformation.

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

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees - Fekete,Sándor P; Khuller, Samir; Klemmstein,Monika; Raghavachari,Balaji; Young,Neal (Journal of Algorithms, 1997)
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning treeTusingadoptionsto meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraintd(v) for eachvis at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min{(d(v) − 2)/(degT(v) − 2) : degT(v) > 2}, where degT(v) is the initial degree ofv. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds foranyalgorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. ChoosingTto be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by variousLpnorms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2.

A perspective on word sense disambiguation methods and their evaluation - Resnik, Philip; Yarowsky,D. (Proceedings of the ACL SIGLEX workshop on tagging text with lexical semantics: Why, what, and how, 1997)

A practical approximation algorithm for the LMS line estimator - Mount, Dave; Netanyahu,Nathan S.; Romanik,Kathleen; Silverman,Ruth; Wu,Angela Y. (Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, 1997)
Keywords: Approximation algorithms; least median-of-squares regression; line arrangements; line fitting; randomized algorithms; robust estimation

Selectional preference and sense disambiguation - Resnik, Philip (Proceedings of the ACL SIGLEX Workshop on Tagging Text with Lexical Semantics: Why, What, and How, 1997)

Semantic query optimization for object databases - Grant,J.; Gryz,J.; Minker, Jack; Raschid, Louiqa (Data Engineering, 1997. Proceedings. 13th International Conference on, 1997)

Semantic query optimization for object databases - Grant,J.; Gryz,J.; Minker, Jack; Raschid, Louiqa (Data Engineering, 1997. Proceedings. 13th International Conference on, 1997)
Presents a technique for semantic query optimization (SQO) for object databases. We use the ODMG-93 (Object Data Management Group) standard ODL (Object Database Language) and OQL (Object Query Language) languages. The ODL object schema and the OQL object query are translated into a DATALOG representation. Semantic knowledge about the object model and the particular application is expressed as integrity constraints. This is an extension of the ODMG-93 standard. SQO is performed in the DATALOG representation, and an equivalent logic query and (subsequently) an equivalent OQL object query are obtained. SQO is based on the residue technique of Chakravarthy et al. (1990). We show that our technique generalizes previous research on SQO for object databases. It can be applied to queries with structure constructors and method application. It utilizes integrity constraints about keys, methods and knowledge of access support relations, to produce equivalent queries, which may have more efficient evaluation plans
Keywords: application; object; constraints; keys; method; constructors; DATALOG; data; databases; object-oriented; databases; query; Datalog; Evaluation; integrity; data; languages; query; Logic; object; optimization; structure; plans; residue; processing; software; query; query; access; query; integrity; relations; equivalent; representation; ODL; schema; ODMG-93; standard; OQL; standards; structures; object-oriented; Support; technique; semantic

Semi-automatic acquisition of domain-specific translation lexicons - Resnik, Philip; Melamed,I.D. (Proceedings of the fifth conference on Applied natural language processing, 1997)

Specification-based Testing of Reactive Software: Tools and Experiments - Jagadeesan,Lalita Jategaonkar; Porter, Adam; Puchol,Carlos; Ramming,J. Christopher; Votta,Lawrence G. (Software Engineering, International Conference on, 1997)
Testing commercial software is expensive and time consuming. Automated testing methods promise to save a great deal of time and money throughout the software industry. One approach that is well-suited for the reactive systems found in telephone switching systems is specification-based testing.We have built a set of tools to automatically test softmare applications for violations of safety properties expressed in temporal logic. Our testing system automatically constructs finite state machine oracles corresponding to safety properties, builds test harnesses, and integrates them with the application. The test harness then generates inputs automatically to test the application.We describe a study examining the feasibility of this approach for testing industrial applications. To conduct this study we formally modeled an Automatic Protection Switching system (APS), which is an application common to many telephony systems. We then asked a number of computer science graduate students to develop several versions of the APS and use our tools to test them. We found that the tools are very effective, save significant amounts of human effort (at the expense of machine resources), and are easy to use. We also discuss improvements that are needed before we can use the tools with professional developers building commercial products.
Keywords: empirical studies; reactive systems; specification-based testing; temporal logic

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

Testing simple polygons - Arkin,Esther M.; Belleville,Patrice; Mitchell,Joseph S.B.; Mount, Dave; Romanik,Kathleen; Salzberg,Steven; Souvaine,Diane (Computational Geometry, 1997)
We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.
Keywords: probing; Testing; Verifying

Towards multiprocessor feature recognition - Regli,William C.; Gupta, Satyandra K.; Nau, Dana S. (Computer-Aided Design, 1997)
The availability of low-cost computational power is enabling the development of increasingly sophisticated cad software. Automation of design and manufacturing activities poses many difficult computational problems—significant among them is how to develop interactive systems that enable designers to explore and experiment with alternative ideas. As more downstream manufacturing activities are considered during the design phase, computational costs become problematic. Creating working software-based solutions requires a sophisticated allocation of computational resources in order to perform realistic design analyses and generate feedback. This paper presents our initial efforts to employ multiprocessor algorithms to recognize machining features from solid models of parts with large numbers of features and many geometric and topological entities. Our goal is to outline how improvements in computation time can be obtained by migrating existing software tools to multiprocessor architectures. An implementation of our approach is discussed.
Keywords: Distributed computing; feature recognition; feature-based modelling; multiprocessor solid modelling

User Interface Reengineering: Low-Effort, High-Payoff Strategies - Plaisant, Catherine; Rose,A.; Shneiderman, Ben; Vanniamparampil,A. J (IEEE Software, 1997)
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 and reducing error rates. We describe low-effort, high-payoff strategies that focus attention on improvements to data display and entry, consistency, messages, documentation, system access and additional functionality. We report on experience from six projects, describing observations, recommendations and outcomes. We close with guidance for managers and designers who are responsible for user interface reengineering.

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

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

Answering queries using OQL view expressions - Florescu,D.; Raschid, Louiqa; Valduriez,P. (In Workshop on Materialized Views, in cooperation with ACM SIGMOD, 1996)

Applying algebraic and differential invariants for logo recognition - David Doermann; Rivlin,E.; Weiss, I. (Machine Vision and Applications, 1996)
The problem of logo recognition is of great interest in the document domain, especially for document databases. By recognizing the logo we obtain semantic information about the document which may be useful in deciding whether or not to analyze the textual components. Given a logo block candidate from a document image and alogo database, we would like to determine whether the region corresponds to a logo in the database. Similarly, if we are given a logo block candidate and adocumentdatabase, we wish to determine whether there are any documents in the database of similar origin. Both problems require indexing into a possibly large model space.In this contribution, we present a novel application of algebraic and differential invariants to the problem of logo recognition. By using invariants we have shape descriptors for matching that are unique and independent of the point of view. The algebraic invariants handle cases in which the whole shape of the logo is given and it is easy to describe. The differential invariants cover complex arbitrary logo shape and handle situations in which only part of the logo is recovered. We outline a hierarchical approach to logo recognition and define methods for page segmentation, feature extraction, and indexing. We demonstrate our approach and present results on a database of approximately 100 logos.

The Balancing Act: Combining Symbolic and Statistical Approaches to Language - Klavans,Judith L.; Resnik, Philip (MIT Press, 1996)
Symbolic and statistical approaches to language have historically been at odds—the former viewed as difficult to test and therefore perhaps impossible to define, and the latter as descriptive but possibly inadequate. At the heart of the debate are fundamental questions concerning the nature of language, the role of data in building a model or theory, and the impact of the competence-performance distinction on the field of computational linguistics. Currently, there is an increasing realization in both camps that the two approaches have something to offer in achieving common goals.The eight contributions in this book explore the inevitable "balancing act" that must take place when symbolic and statistical approaches are brought together—including basic choices about what knowledge will be represented symbolically and how it will be obtained, what assumptions underlie the statistical model, what principles motivate the symbolic model, and what the researcher gains by combining approaches.The topics covered include an examination of the relationship between traditional linguistics and statistical methods, qualitative and quantitative methods of speech translation, study and implementation of combined techniques for automatic extraction of terminology, comparative analysis of the contributions of linguistic cues to a statistical word grouping system, automatic construction of a symbolic parser via statistical techniques, combining linguistic with statistical methods in automatic speech understanding, exploring the nature of transformation-based learning, and a hybrid symbolic/statistical approach to recovering from parser failures.
Keywords: computational linguistics; Computational linguistics - Congresses; Computational linguistics/ Congresses; Computers / Intelligence (AI) & Semantics; Foreign Language Study / General; Language Arts & Disciplines / Linguistics / General; linguistics; Linguistics - Statistical methods - Congresses; Linguistics/ Statistical methods/ Congresses; Social Science / General

The block distributed memory model - JaJa, Joseph F.; Ryu,Kwan Woo (Parallel and Distributed Systems, IEEE Transactions on, 1996)
We introduce a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity. Ongoing experimental work in testing and evaluating these algorithms has thus far shown very promising results
Keywords: accesses; single; address; algorithms; performance; algorithms; performance; remote; allocation; sorting; balancing; matrix; bandwidth; communication; communication; load; complexity; computation; complexity; computational; complexity; cost; complexity; distributed; distributed; evaluation; resource; FFT; block; Fourier; latency; parallel; locality; communication; machines; interconnection; measure; data; memory; model; communication; model; computational; multiplication; memory; multiplication; parallel; problems; distributed; rearrangement; space; sorting; spatial; systems; fast; topology; interprocessor; transforms; matrix

Compressed Video Segmentation - Kobla,Vikrant; David Doermann; Rosenfeld,Azriel (University of Maryland, College Park, 1996)
Segmentation of video into shots and scenes in the compressed domain allows rapid, real-time analysis of video content using standard hardware. This paper presents robust techniques for parsing MPEG-compressed video sequences into shots based on their physical structure and further into scenes based on their semantic structure by identifying changes in content and camera motion. The analysis is performed in the compressed domain using available macroblock and motion vector information, and if necessary, DCT information. Motion vector analysis yields a qualitative description of the camera motion and is used to subdivide shots into subshots. Key frames for the shots and scenes can be used for browsing, indexing, and retrieval.

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

The Development of a General Framework for Intelligent Document Image Retrieval - David Doermann; Sauvola,J.; Kauniskangas,H.; Shin,C.; Pietikainen,M.; Rosenfeld, A. (Proceedings in the International Workshop on Document Analysis Systems, 1996)

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

Feature discovery and classification of Doppler umbilical artery blood flow velocity waveforms - Baykal,Nazife; Reogia,James A.; Yalabik,Nese; Erkmen,Aydan; Beksac,M.Sinan (Computers in Biology and Medicine, 1996)
Doppler umbilical artery blood flow velocity waveform measurements are used in perinatal surveillance for the evaluation of fetal condition. There is an ongoing debate on the predictive value of Doppler measurements concerning the critical effect of the selection of parameters for the interpretation of Doppler waveforms. In this paper, we describe how neural network methods can be used both to discover relevant classification features and subsequently to classify Doppler umbilical artery blood flow velocity waveforms. Results obtained from 199 normal and high risk patients' umbilical artery waveforms highlighted a classification concordance varying from 90 to 98% accuracy.
Keywords: Doppler umbilical artery blood flow velocity waveforms; Feature extraction; IMAGE PROCESSING; Pattern classification

The Function of Documents - David Doermann; Rivlin,Ehud; Rosenfeld,Azriel (University of Maryland, College Park, 1996)
The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval. To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.

Graph and network algorithms - Khuller, Samir; Raghavachari,Balaji (ACM Computing Surveys, 1996)

Hybrid network management (communication systems) - Baras,J. S; Ball,M.; Karne,R. K; Kelley,S.; Jang,K.D.; Plaisant, Catherine; Roussopoulos, Nick; Stathatos,K.; Vakhutinsky,A.; Valluri,J. (16th AIAA International Communications Satellite Systems Conference, 1996)
We describe our collaborative efforts towards the design and implementation of a next-generation integrated network management system for hybrid networks (INMS/HN). We describe the overall software architecture of the system at its current stage of development. This NMS is specifically designed to address issues relevant to complex heterogeneous networks consisting of seamlessly interoperable terrestrial and satellite networks. NMSs are a key element for interoperability in such networks. We describe the integration of configuration management and performance management. The next step in this integration is fault management. In particular, we describe the object model, issues concerning the graphical user interface, browsing tools, performance data graphical widget displays, and management information database organization issues.

Integrated network management of hybrid networks - Baras,John S; Ball,Mike; Karne,Ramesh K; Kelley,Steve; Jang,Kap D; Plaisant, Catherine; Roussopoulos, Nick; Stathatos,Kostas; Vakhutinsky,Andrew; Jaibharat,Valluri; Whitefield,David (AIP Conference Proceedings, 1996)
We describe our collaborative efforts towards the design and implementation of a next generation integrated network management system for hybrid networks (INMS/HN). We describe the overall software architecture of the system at its current stage of development. This network management system is specifically designed to address issues relevant for complex heterogeneous networks consisting of seamlessly interoperable terrestrial and satellite networks. Network management systems are a key element for interoperability in such networks. We describe the integration of configuration management and performance management. The next step in this integration is fault management. In particular we describe the object model, issues of the Graphical User Interface (GUI), browsing tools and performance data graphical widget displays, management information database (MIB) organization issues. Several components of the system are being commercialized by Hughes Network Systems. © 1996 American Institute of Physics.

Landmarks in graphs - Khuller, Samir; Raghavachari,Balaji; Rosenfeld,Azriel (Discrete Applied Mathematics, 1996)
Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.

Learning activation rules for associative networks - Reggia, James A.; Grundstrom,E.; Berndt,R. S (Neural Networks, 1996., IEEE International Conference on, 1996)

Learning Activation Rules Rather Than Connection Weights - Grundstrom,E. L; Reggia, James A. (International journal of neural systems, 1996)

LifeLines: visualizing personal histories - Plaisant, Catherine; Milash,Brett; Rose,Anne; Widoff,Seth; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, 1996)
Keywords: History; justice; medical record; overview; personal record; screen design; screen management; timeline; Visualization

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

A methodology for query reformulation in CIS using semantic knowledge - Florescu,D.; Raschid, Louiqa; Valduriez,P. (International Journal of Cooperative Information Systems, 1996)

Mixing a default rule with stable negation - Minker, Jack; Ruiz,C. (Proceedings of the Fourth International Symposium on Artificial Intelligence and Mathematics, 1996)
Logic programs containing only at most one form ofdefault negation have been studied in the literature. We describe a class of logic programs containing multi- ple forms of default negation. We de ne a meaning for these programs based on the well{founded semantics and the stable semantics. We investigate properties of the new combined semantics and calculate the com- putational complexity of determining the existence of models, and of skeptical and credulous reasoning. An e ective procedure to construct the collection of mod- els characterizing the semantics of a program is given. Applications to knowledge representation and knowl- edge base merging are presented.

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

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

An optimal randomized parallel algorithm for the single function coarsest partition problem - JaJa, Joseph F.; Ryu,K. W. (PPL-Parallel Processing Letters, 1996)
We describe a randomized parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n) operations with high probability on the Priority CRCW PRAM. The previous best known algorithms run in O(log2 n) time using O(n log2 n) operations on the CREW PRAM and O(log n) time using O(n log log n) operations on the Arbitrary CRCW PRAM. The technique presented can be used to generate the Euler tour of a rooted tree optimally from the parent representation.

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

Runtime coupling of data-parallel programs - Ranganathan,M.; Acharya, A.; Edjlali,G.; Sussman, Alan; Saltz, J. (Proceedings of the 10th international conference on Supercomputing, 1996)

Scaling heterogeneous databases and the design of DISCO - Tomasic,A.; Raschid, Louiqa; Valduriez,P. (ICDCS, 1996)

Selectional constraints: an information-theoretic model and its computational realization - Resnik, Philip (Cognition, 1996)
A new, information-theoretic model of selectional constraints is proposed. The strategy adopted here is a minimalist one: how far can one get making as few assumptions as possible? In keeping with that strategy, the proposed model consists of only two components: first, a fairly generic taxonomic representation of concepts, and, second, a probabilistic formalization of selectional constraints defined in terms of that taxonomy, computed on the basis of simple, observable frequencies of co-occurrence between predicates and their arguments. Unlike traditional selection restrictions, the information-theoretic approach avoids empirical problems associated with definitional theories of word meaning, accommodates the observation that semantic anomaly often appears to be a matter of degree, and provides an account of how selectional constraints can be learned. A computational implementation of the model “learns” selectional constraints from collections of naturally occurring text; the predictions of the implemented model are evaluated against judgments elicited from adult subjects, and used to explore the way that arguments are syntactically realized for a class of English verbs. The paper concludes with a discussion of the role of selectional constraints in the acquisition of verb meaning.

Semantics of knowledge-based systems with multiple forms of negation - Ruiz,C.; Minker, Jack (University of Maryland at College Park, 1996)

Social impact statements: engaging public participation in information technology design - Shneiderman, Ben; Rose,Anne (Proceedings of the symposium on Computers and the quality of life, 1996)

Sorting strings and constructing digital search trees in parallel - JaJa, Joseph F.; Ryu,Kwan Woo; Vishkin, Uzi (Theoretical Computer Science, 1996)
We describe two simple optimal-work parallel algorithms for sorting a list L= (X1, X2, …, Xm) of m strings over an arbitrary alphabet Σ, where ∑i = 1m¦Xi¦ = n and two elements of Σ can be compared in unit time using a single processor. The first algorithm is a deterministic algorithm that runs in O(log2m/log log m) time and the second is a randomized algorithm that runs in O(logm) time. Both algorithms use O(m log m + n) operations. Compared to the best-known parallel algorithms for sorting strings, our algorithms offer the following improvements. 1.1. The total number of operations used by our algorithms is optimal while all previous parallel algorithms use a nonoptimal number of operations. 2. 2. We make no assumption about the alphabet while the previous algorithms assume that the alphabet is restricted to {1, 2, …, no(1)}. 3. 3. The computation model assumed by our algorithms is the Common CRCW PRAM unlike the known algorithms that assume the Arbitrary CRCW PRAM. 4. 4. Our algorithms use O(m log m + n) space, while the previous parallel algorithms use O(n1 + ε) space, where ε is a positive constant. We also present optimal-work parallel algorithms to construct a digital search tree for a given set of strings and to search for a string in a sorted list of strings. We use our parallel sorting algorithms to solve the problem of determining a minimal starting point of a circular string with respect to lexicographic ordering. Our solution improves upon the previous best-known result to solve this problem.

On strongly connected digraphs with bounded cycle length - Khuller, Samir; Raghavachari,Balaji; Young,Neal (Discrete Applied Mathematics, 1996)
Given a directed graph G = (V, E), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v, if there is a path from u to v in E, then there is a path from u to v among the chosen edges. We show that in graphs having no directed cycle with more than three edges, this problem is equivalent to Maximum Bipartite Matching. This leads to a small improvement in the performance guarantee of the previous best approximation algorithm for the general problem.

A Theory of Document Functionality - Rivlin,E.; Doermann, David; Rosenfeld, A. (Proceedings in FLAIRS, 1996)

Transitive closure of infinite graphs and its applications - Kelly,W.; Pugh, William; Rosser,E.; Shpeisman,T. (Languages and Compilers for Parallel Computing, 1996)

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

An applied ethnographic method for redesigning user interfaces - Rose,Anne; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the 1st conference on Designing interactive systems: processes, practices, methods, & techniques, 1995)

Approximating the minimum equivalent digraph - Khuller, Samir; Raghavachari,B.; Young,N. (SIAM Journal on Computing (SICOMP), 1995)

Automated Manufacturability Analysis: A Survey - Das,Diganta; Gupta, Satyandra K.; Regli,W. C.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1995)
In the marketplace of the 21st century, there is no place for traditional ``over-the-wall'' communications between design and manufacturing. In order to ``design it right the very first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them. In this paper, we provide a survey of current state of the art in automated manufacturability analysis. We present the historical context in which this area has emerged and outline characteristics to compare and classify various systems. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. We describe support tools that enhance the effectiveness of manufacturability analysis systems. Finally, we attempt to expose some of the existing research challenges and future directions.
Keywords: manufacturability; Manufacturing; Solid modeling; Systems Integration Methodology

Balancing minimum spanning trees and shortest-path trees - Khuller, Samir; Raghavachari,B.; Young,N. (Algorithmica, 1995)
We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and agamma>0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+radic2gamma times the shortest-path distance, and yet the total weight of the tree is at most 1+radic2/gamma times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.

Code generation for multiple mappings - Kelly,W.; Pugh, William; Rosser,E. (Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the, 1995)
There has been a great amount of recent work toward unifying iteration reordering transformations. Many of these approaches represent transformations as affine mappings from the original iteration space to a new iteration space. These approaches show a great deal of promise, but they all rely on the ability to generate code that iterates over the points in these new iteration spaces in the appropriate order. This problem has been fairly well-studied in the case where all statements use the same mapping. We have developed an algorithm for the less well-studied case where each statement uses a potentially different mapping. Unlike many other approaches, our algorithm can also generate code from mappings corresponding to loop blocking. We address the important trade-off between reducing control overhead and duplicating code
Keywords: code generation; Computer science; Concurrent computing; control overhead; Educational institutions; iteration reordering transformations; Law; Legal factors; loop blocking; multiple mappings; optimisation; optimising compilers; Optimizing compilers; PARALLEL PROCESSING; Performance analysis; program compilers

Computing stable and partial stable models of extended disjunctive logic programs - Ruiz,C.; Minker, Jack (Non-Monotonic Extensions of Logic Programming, 1995)
n [Prz91], Przymusinski introduced the partial (or 3-valued) stable model semantics which extends the (2-valued) stable model semantics defined originally by Gelfond and Lifschitz [GL88]. In this paper we describe a procedure to compute the collection of all partial stable models of an extended disjunctive logic program. This procedure consists in transforming an extended disjunctive logic program into a constrained disjunctive program free of negation-by-default whose set of 2-valued minimal models corresponds to the set of partial stable models of the original program.

Current Trends and Future Challenges in Automated Manufacturability Analysis - Gupta, Satyandra K.; Das,Diganta; Regli,W. C.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1995)
In the marketplace of the 21st century, there is no place for traditional communications between design and manufacturing. In order to ``design it right the first time,'' designers must ensure that their products are both functional and easy to manufacture. Software tools have had some successes in reducing the barriers between design and manufacturing. Manufacturability analysis systems are emerging as one such tool---enabling identification of potential manufacturing problems during the design phase and providing suggestions to designers on how to eliminate them. In this paper, we survey of current state of the art in automated manufacturability analysis. We describe the two dominant approaches to automated manufacturability analysis and overview representative systems based on their application domain. Finally, we attempt to expose some of the existing research challenges and future directions.
Keywords: computer integrated manufacturing; manufacturability; Manufacturing; Solid modeling; Systems Integration Methodology

Dealing with complexity: uniting agents and direct manipulation (panel session) - Riecken,Doug; Maes,Pattie; Shneiderman, Ben; Smith,David Canfield (Conference companion on Human factors in computing systems, 1995)

Defining, Computing, and Visualizing Molecular Interfaces - Varshney, Amitabh; Brooks Jr,Frederick P.; Manocha,Dinesh; Wright,William V.; Richardson,David C. (Proceedings of the 6th conference on Visualization '95, 1995)
A parallel, analytic approach for defining and computing the inter- and intra-molecular interfaces in three dimensions is described. The "molecular interface surfaces" are derived from approximations to the power-diagrams over the participating molecular units. For a given molecular interface our approach can generate a family of interface surfaces parametrized by alpha and beta, where alpha is the radius of the solvent molecule (also known as the probe-radius) and beta is the interface radius that defines the size of the molecular interface. Molecular interface surfaces provide biochemists with a powerful tool to study surface complementarity and to efficiently characterize the interactions during a protein-substrate docking. The complexity of our algorithm for molecular environments is O(n k \log^2{k}), where n is the number of atoms in the participating molecular units and k is the average number of neighboring atoms -- a constant, given alpha and beta.
Keywords: Computational Biochemistry Algorithms Molecular Graphics; Connolly Surfaces; Molecular Interfaces; Molecular Surfaces; Protein-Protein Recognition

Disambiguating noun groupings with respect to WordNet senses - Resnik, Philip (Proceedings of the Third Workshop on Very Large Corpora, 1995)

Discovery of self-replicating structures using a genetic algorithm - Lohn,J. D; Reggia, James A. (Evolutionary Computation, 1995., IEEE International Conference on, 1995)

Extracting alternative machining features: An algorithmic approach - Regli,William C.; Gupta, Satyandra K.; Nau, Dana S. (Research in Engineering Design, 1995)
Automated recognition of features from CAD models has been attempted for a wide range of application domains. In this article we address the problem of representing and recognizing a complete class of features in alternative interpretation for a given design.
Keywords: engineering

Graphbots: Mobility in discrete spaces - Khuller, Samir; Rivlin,E.; Rosenfeld, A. (Automata, Languages and Programming, 1995)
Most previous theoretical work on motion planning has addressed the problem of path planning for geometrically simple robots in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper we define a natural version of the motion planning problem in a graph theoretic setting. We establish conditions under which a ldquorobotrdquo or team of robots having a particular graph structure can move from any start location to any goal destination in a graph-structured space.

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

Improved approximation algorithms for uniform connectivity problems - Khuller, Samir; Raghavachari,Balaji (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995)

Interactive feature recognition using multi-processor methods - Regli,W. C.; Gupta,S.K.; Nau, Dana S. (1995)

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

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

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

Manufacturing feature instances: which ones to recognize? - Gupta, Satyandra K.; Regli,William C.; Nau, Dana S. (ACM, 1995)

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

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

A neural model of memory impairment in diffuse cerebral atrophy - Ruppin,E.; Reggia, James A. (The British Journal of Psychiatry, 1995)

Next generation network management technology - Baras,John S; Atallah,George C; Ball,Mike; Goli,Shravan; Karne,Ramesh K; Kelley,Steve; Kumar,Harsha; Plaisant, Catherine; Roussopoulos, Nick; Schneiderman,Ben; Srinivasarao,Mulugu; Stathatos,Kosta; et al. (AIP Conference Proceedings, 1995)
Today’s telecommunications networks are becoming increasingly large, complex, mission critical and heterogeneous in several dimensions. For example, the underlying physical transmission facilities of a given network may be ‘‘mixed media’’ (copper, fiber‐optic, radio, and satellite); the subnetworks may be acquired from different vendors due to economic, performance, or general availability reasons; the information being transmitted over the network may be ‘‘multimedia’’ (video, data, voice, and images) and, finally, varying performance criteria may be imposed e.g., data transfer may require high throughput while the others, whose concern is voice communications, may require low call blocking probability. For these reasons, future telecommunications networks are expected to be highly complex in their services and operations. Due to this growing complexity and the disparity among management systems for individual sub‐networks, efficient network management systems have become critical to the current and future success of telecommunications companies. This paper addresses a research and development effort which focuses on prototyping configuration management, since that is the central process of network management and all other network management functions must be built upon it. Our prototype incorporates ergonomically designed graphical user interfaces tailored to the network configuration management subsystem and to the proposed advanced object‐oriented database structure. The resulting design concept follows open standards such as Open Systems Interconnection (OSI) and incorporates object oriented programming methodology to associate data with functions, permit customization, and provide an open architecture environment. © 1995 American Institute of Physics

Parallel algorithms for database operations and a database operation for parallel algorithms - Raman,R.; Vishkin, Uzi (Parallel Processing Symposium, 1995. Proceedings., 9th International, 1995)

Patterns of functional damage in neural network models of associative memory - Ruppin,E.; Reggia, James A. (Neural computation, 1995)

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

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

Seeing and understanding: representing the visual world - Aloimonos, J.; Fermüller, Cornelia; Rosenfeld, A. (ACM Comput. Surv., 1995)

Symmetries of natural and artificial neural networks - Reggia, James A. (Symmetry: Culture and Science, 1995)

Using information content to evaluate semantic similarity in a taxonomy - Resnik, Philip (Arxiv preprint cmp-lg/9511007, 1995)

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

Adaptation of noncompetitive and competitive neural networks to focal lesions - Weinrich,M.; Sutton,G. G; Reggia, James A.; D'Autrechy,C. L (Journal of Artificial Neural Networks, 1994)

An Application of Distributed Solid Modeling: Feature Recognition - Regli,W. C.; Gupta, Satyandra K.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1994)
The availability of low-cost computational power is a driving force behind the growing sophistication of CAD software. Tools designed to reduce time-consuming build-test-redesign iterations are essential for increasing engineering quality and productivity. However, automation of the design process poses many difficult computational problems. As more downstream engineering activities are being considered during the design phase, guaranteeing reasonable response times within design systems becomes problematic. Design is an interactive process and speed is a critical factor in systems that enable designers to explore and experiment with alternative ideas during the design phase. Achieving interactivity requires an increasingly sophisticated allocation of computational resources in order to perform realistic design analyses and generate feedback in real time. This paper presents our initial efforts to develop techniques to apply distributed algorithms to the problem of recognizing machining features from solid models. Existing work on recognition of features has focused exclusively on serial computer architectures. Our objective is to show that distributed algorithms can be employed on realistic parts with large numbers of features and many geometric and topological entities to obtain significant improvements in computation time using existing hardware and software tools. Migrating solid modeling applications toward a distributed computing frame-work enables interconnection of many of the autonomous and geographically diverse software tools used in the modern manufacturing enterprise. This has been implemented on a network of SUN workstations using the ACIS solid modeler and the NIH C++ class library; inter-processor communication is handled with TCP/IP- based network communication tools.
Keywords: Distributed computing; feature recognition; feature- based modeling; multiprocessor solid modeling; Systems Integration Methodology

The block distributed memory model for shared memory multiprocessors - JaJa, Joseph F.; Ryu,Kwan Woo (Parallel Processing Symposium, 1994. Proceedings., Eighth International, 1994)
Introduces a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity
Keywords: accesses; shared; address; algebra; parallel; algorithms; performance; algorithms; performance; pipelined; allocation; shared; balancing; matrix; bandwidth; computation; block; Communication; communication; load; complexity; computational; complexity; cost; complexity; distributed; complexity; optimal; data; distributed; evaluation; resource; Fourier; latency; optimal; locality; communication; measure; data; memory; model; communication; model; computational; multiplication; memory; multiprocessors; single; placement; interprocessor; prefetching; remote; problems; fast; rearrangement; space; sorting; spatial; speedup; parallel; systems; fast; systems; sorting; transforms; input; transforms; matrix

Building MRSEV models for CAM applications - Gupta, Satyandra K.; Kramer,Thomas R.; Nau, Dana S.; Regli,William C.; Zhang,Guangming (Advances in Engineering Software, 1994)
In integrating CAD and CAM applications, one major problem is how to interpret CAD information in a manner that makes sense for CAM. The goal is to develop a general approach that can be used with a variety of CAD and CAM applications for the manufacture of machined parts.In particular, a methodology is presented for taking a CAD model, extracting alternative interpretations of the model as collections of MRSEVs (material removal shape element volumes, a STEP-based library of machining features), and evaluating these interpretations to determine which one is optimal. The evaluation criteria may be defined by the user, in order to select the best interpretation for the particular application at hand.
Keywords: CAD/CAM integration; design critiquing; feature recognition

Confidence Intervals for Discrete Approximations to Ill-Posed Problems - Rust,Bert W.; O'Leary, Dianne P. (The Journal of Computational and Graphical Statistics, 1994)

Cortical map reorganization as a competitive process - Sutton III,G. G.; Reggia, James A.; Armentrout,S. L; D'Autrechy,C. L (Neural Computation, 1994)

Effects of normalization constraints on competitive learning - Sutton,G. G; Reggia, James A. (Neural Networks, IEEE Transactions on, 1994)

An efficient parallel algorithm for the single function coarsest partition problem - JaJa, Joseph F.; Ryu,K. W. (Theoretical computer science, 1994)
We describe an efficient parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O(log n) time using O(n log log n) operations on the arbitrary CRCW PRAM. The previous best-known algorithms run in O(log2 n) time using O(n log2 n) operations on the CREW PRAM, and O(log n) time using O(n log n) operations on the arbitrary CRCW PRAM. Our solution is based on efficient algorithms for solving several subproblems that are of independent interest. In particular, we present efficient parallel algorithms to find a minimal starting point of a circular string with respect to lexicographic ordering and to sort lexicographically a list of strings of different lengths

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

Feature Recognition for Manufacturability Analysis - Regli,W. C.; Gupta, Satyandra K.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 1994)
While automated recognition of features has been attempted for a wide range of applications, no single existing approach possesses the functionality required to perform manufacturability analysis. In this paper, we present a methodology for taking a CAD model and extracting a set of machinable features suitable for generating all alternative interpretations of the model as collections of MRSEVs (Material Removal Shape Element Volumes, a STEP-based library of machining, features). This set of MRSEVs is to be employed for manufacturability analysis. The algorithm handles a variety of features including those describing holes, pockets, slots, and chamfering and filleting operations. In addition, it considers elementary accessibility constraints for these features and is provably complete over a, significant class of machinable parts the features describe. Further, the approach has low-order polynomial-time worst-case complexity.
Keywords: algorithms; Automation; COMPUTER AIDED DESIGN; computer aided manufacturing; computer integrated manufacturing; Feature extraction; manufacturability; Manufacturing; Solid modeling; Systems Integration

High-specificity neurological localization using a connectionist model - Tuhrim,S.; Reggia, James A.; Peng,Y. (Artificial Intelligence in Medicine, 1994)

Instrument Grasp: AModel and its Effects on Handwritten Strokes - David Doermann; Varma,V.; Rosenfeld, A. (Pattern Recognition, 1994)

Integrating DFM with CAD through Design Critiquing - Gupta, Satyandra K.; Regli,William C.; Nau, Dana S. (Concurrent EngineeringConcurrent Engineering, 1994)
The increasing focus on design for manufacturability (DFM) in research in concurrent engineering and engineering design is expanding the scope of traditional design activities in order to identify and eliminate manufacturing problems during the design stage. Manufacturing a product generally involves many different kinds of manufacturing activities, each having different characteristics. A design that is good for one kind of activity may not be good for another; for example, a design that is easy to assemble may not be easy to machine. One obstacle to DFM is the difficulty involved in building a single system that can handle the various manufacturing domains relevant to a design.
Keywords: design critiquing; design for manufacturability; feature-based modeling; manufacturability analysis; multi-agent coordination.

Interpretation of Doppler blood flow velocity waveforms using neural networks. - Baykal,N.; Reggia, James A.; Yalabik,N.; Erkmen,A.; Beksac,M. S. (Proceedings of the Annual Symposium on Computer Application in Medical Care, 1994)

Map formation in proprioceptive cortex. - Cho,S.; Reggia, James A. (International journal of neural systems, 1994)

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

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

Navigating in hyperspace: designing a structure-based toolbox - Rivlin,Ehud; Botafogo,Rodrigo; Shneiderman, Ben (Communications of the ACM, 1994)

A neural model of cortical map reorganization following a focal lesion - Armentrout,S. L; Reggia, James A.; Weinrich,M. (Artificial Intelligence in Medicine, 1994)

Next Generation Network Management Technology - Atallah,George C; Ball,Michael O; Baras,John S; Goli,Shravan K; Karne,Ramesh K; Kelley,Stephen; Kumar,Harsha P.; Plaisant, Catherine; Roussopoulos, Nick; Shneiderman, Ben; Srinivasarao,Mulugu; Stathatos,Kostas; et al. (Institute for Systems Research Technical Reports, 1994)
Today's telecommunications networks are becoming increasingly large, complex, mission critical and heterogeneous in several dimensions. For example, the underlying physical transmission facilities of a given network may be ﲭixed media (copper, fiber- optic, radio, and satellite); the sub networks may be acquired from different vendors due to economic, performance, or general availability reasons; the information being transmitted over the network may be ﲭultimedia (video, data, voice, and images) and, finally, varying performance criteria may be imposed e.g. data transfer may require high throughput while the others, whose concern is voice communications, may require low call blocking probability. For these reasons, future telecommunications networks are expected to be highly complex in their services and operations. Due to this growing complexity and the disparity among management systems for individual sub networks, efficient network management systems have become critical to the current and future success of telecommunications companies. This paper addresses a research and development effort which focuses on prototyping configuration management, since that is the central process of network management and all other network management functions must be built upon it. Our prototype incorporates ergonomically designed graphical user interfaces tailored to the network configuration management subsystem and to the proposed advanced object-oriented database structure. The resulting design concept follows open standards such as Open Systems Interconnection (OSI) and incorporates object oriented programming methodology to associate data with functions, permit customization, and provide an open architecture environment. A revised version of this technical report has been published in The 12th Symposium on Space Nuclear Power and Propulsion/Commercialization, pp. 75-82, Albuquerque, NM, January 8-12, 1995.
Keywords: Constraints for Network Management.; Network Configuration Management; network management; Object Oriented Data Base Model for Network Management; Rules; Systems Integration; Visual Information Management for Network Configuration Management

Optimal randomized parallel algorithms for computing the row maxima of a totally monotone matrix - Raman,R.; Vishkin, Uzi (Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, 1994)

P element-mediated in vivo deletion analysis of white-apricot: deletions between direct repeats are strongly favored. - Kurkulos,M.; Weinberg,J. M.; Roy,D.; Mount, Stephen M. (GeneticsGenetics, 1994)
We have isolated and characterized deletions arising within a P transposon, P[hswa], in the presence of P transposase. P[hswa] carries white-apricot (wa) sequences, including a complete copia element, under the control of an hsp70 promoter, and resembles the original wa allele in eye color phenotype. In the presence of P transposase, P[hswa] shows a high overall rate (approximately 3%) of germline mutations that result in increased eye pigmentation. Of 234 derivatives of P[hswa] with greatly increased eye pigmentation, at least 205 carried deletions within copia. Of these, 201 were precise deletions between the directly repeated 276-nucleotide copia long terminal repeats (LTRs), and four were unique deletions. High rates of transposase-induced precise deletion were observed within another P transposon carrying unrelated 599 nucleotide repeats (yeast 2 mu FLP; recombinase target sites) separated by 5.7 kb. Our observation that P element-mediated deletion formation occurs preferentially between direct repeats suggests general methods for controlling deletion formation.

Principles of computer vision - Aloimonos, J.; Rosenfeld, A. (Handbook of pattern recognition and image processing (vol. 2), 1994)

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

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

Recovery of Temporal Information from Static Images of Handwriting - David Doermann; Rosenfeld, A. (International Journal of Computer Vision, 1994)
The problem of off-line handwritten character recognition has eluded a satisfactory solution for several decades. Researchers working in the area of on-line recognition have had greater success, but the possibility of extracting on-line information from static images has not been fully explored. The experience of forensic document examiners assures us that in many cases, such information can be successfully recovered.We outline the design of a system for the recovery of temporal information from static handwritten images. We provide a taxonomy of local, regional and global temporal clues which are often found in hand-written samples, and describe methods for recovering these clues from the image. We show how this system can benefit from obtaining a comprehensive understanding of the handwriting signal and a detailed analysis of stroke and sub-stroke properties. We suggest that the recovery task requires that we break away from traditional thresholding and thinning techniques, and we provide a framework for such analysis. We demonstrate how isolated temporal clues can reliably be extracted from this framework and propose a control structure for integrating the partial information. We show how many seemingly ambiguous situations can be resolved by the derived clues and our knowledge of the writing process, and provide several examples to illustrate our approach. The support of this research by the Ricoh Corporation is gratefully acknowledged.

A rule-based approach to prepositional phrase attachment disambiguation - Brill,E.; Resnik, Philip (Proceedings of the 15th conference on Computational linguistics-Volume 2, 1994)

A Semantics for a class of non-deterministic and causal production system programs - Raschid, Louiqa; Lobo,J. (Journal of Automated Reasoning, 1994)

A simulation-based study on the concurrent execution of rules in a database environment - Raschid, Louiqa; Sellis,T.; Delis,A. (Journal of Parallel and Distributed computing, 1994)