Agents vs. direct manipulation: what's best to disentangle the Web? - Sánchez,J.A.; Etzioni,O.; Kautz,H.; Lieberman,H.; Shneiderman, Ben (Proceedings of the eighth international conference on World Wide Web, 1999)

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

The budgeted maximum coverage problem - Khuller, Samir; Moss,A.; Naor,J. S (Information Processing Letters, 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)

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

Coupling multiple simulations via a high performance customizable database system - Kurc,T. M; Sussman, Alan; Saltz, J. (Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, 1999)

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

Detection of slow-motion replay sequences for identifying sports videos - Kobla,V.; DeMenthon,D.; David Doermann (Proceedings of IEEE 1999 Workshop on Multimedia Signal Processing, 1999)
Automated classication of digital video is emerging as an important piece of the puzzle in the design of content management systems for digital libraries. The ability to classify videos into various genres such as sports, news, movies, or documentaries increases the efficiency of indexing, browsing, and retrieval of video in large databases. In this paper we present an automated technique for identifying slow motion replays directly from the compressed domain of MPEG video, It uses the macroblock motion and bit-rate information that is readily accessible from MPEG video with very minimal decoding, leading to enormous gains in processing speeds.

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)

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

Efficient preconditioning of the linearized Navier-Stokes equations - Silvester, D.; Elman, Howard; Kay, D.; Wathen, A. (Citeseer, 1999)

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

A hierarchical data archiving and processing system to generate custom tailored products from AVHRR data - Kalluri, SNV; Zhang,Z.; JaJa, Joseph F.; Bader, D.A.; Song,H.; El Saleous,N.; Vermote,E.; Townshend,J.R.G. (Geoscience and Remote Sensing Symposium, 1999. IGARSS '99 Proceedings. IEEE 1999 International, 1999)
A novel indexing scheme is described to catalogue satellite data on a pixel basis. The objective of this research is to develop an efficient methodology to archive, retrieve and process satellite data, so that data products can be generated to meet the specific needs of individual scientists. When requesting data, users can specify the spatial and temporal resolution, geographic projection, choice of atmospheric correction, and the data selection methodology. The data processing is done in two stages. Satellite data is calibrated, navigated and quality flags are appended in the initial processing. This processed data is then indexed and stored. Secondary processing such as atmospheric correction and projection are done after a user requests the data to create custom made products. By dividing the processing in to two stages saves time, since the basic processing tasks such as navigation and calibration which are common to all requests are not repeated when different users request satellite data. The indexing scheme described can be extended to allow fusion of data sets from different sensors
Keywords: archiving; image; AVHRR; GIS; PACS; custom; data; image; land; image; remote; mapping; mapping; PACS; geophysical; measurement; PROCESSING; processing; geophysical; product; data; remote; scheme; infrared; sensing; optical; sensing; terrain; signal; surface; multispectral; system; indexing; tailored; technique; hierarchical; techniques; remote

Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets - Guha,Sudipto; Khuller, Samir (Information and Computation, 1999)
In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on “spider decompositions” was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2 ln k, wherekis the number of terminals. However, the best known lower bound on the approximation ratio is (1−o(1)) ln k, assuming thatNP⊈DTIME[nO(log log n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of ln k. For the weighted case we develop a new decomposition theorem and generalize the notion of “spiders” to “branch-spiders” that are used to design a new algorithm with a worst case approximation factor of 1.5 ln k. We then generalize the method to yield an approximation factor of (1.35+ε) ln k, for any constantε>0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1.6103 ln k. The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0–1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3 ln nby Guha and Khuller. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of (1.35+ε) ln nfor any fixedε>0.

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.

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

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

Machine Translation - Bel,N.; Dorr, Bonnie J; Hovy,E.; Knight,K.; Iida,H.; Boitet,C.; Maegaard,B.; Wilks,Y. (Multilingual Information Management: Current Levels and Future Abilities, 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

Nano-to-millimeter scale integrated systems - Last,H.R.; Deeds,M.; Garvick,D.; Kavetsky,R.; Sandborn,P. A.; Magrab,E. B.; Gupta,S.K. (Components and Packaging Technologies, IEEE Transactions on, 1999)
Over the last several years various industries have been developing nano, micro, and millimeter scale technologies, which have resulted in components ranging from quantum transistors, to widely commercialized integrated circuits, to microelectromechanical sensors. A common emphasis of these fabrication industries has been on the integration of different functions in miniaturized systems; however, the technology currently used to realize these systems is monolithic. A unique class of hybrid technology systems is Integrated nano to millimeter (In2m) systems. An In2m system typically has components spanning multiple sizes, diverse technology domains, and mixtures of electrical, mechanical, thermal, chemical, fluidic, and biological functions
Keywords: fabrication technology; In2m; integrated nano to millimeter system; micromechanical devices; nanotechnology

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

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

Perceptual Organization in Computer Vision - Boyer,K.L.; Sarkar,S.; Feldman,J.; Granlund,G.; Horaud,R.; Hutchinson,S.; Jacobs, David W.; Kak,A.; Lowe,D.; Malik,J. (Academic Press, 1999)

Pivoted Cauchy-Like Preconditioners for Regularized Solution of Ill-Posed Problems - Kilmer,Misha E.; O'Leary, Dianne P. (SIAM Journal on Scientific Computing, 1999)

PLAN: A programming language for active networks - Hicks, Michael W.; Kakkar,P.; Moore,J. T; Gunter,C. A; Nettles,S. (ACM SIGPLAN NOTICES, 1999)
PLAN (Programming Language for Active Networks) is anew language for programs that are carried in the packets of a programmable network. PLAN programs replace the packet headers (which can be viewed as `dumb' programs) used in current networks. As a header replacement, PLAN programs must be lightweight and of limited functionality. These limitations are mitigated by allowing PLAN code to call service routines written in other, more powerful lan- guages. These service routines may also be loaded into the routers dynamically. This two-level architecture, in which PLAN serves as a scripting or `glue' language for more gen- eral services, is the primary contribution of the paper. PLAN is a strict functional language providing a limited set of primitives and datatypes. PLAN de nes primitives for remotely executing PLAN programs on other nodes, and these primitives are used to provide basic data transport in the network. Because remote execution makes debugging di cult, PLAN provides strong static guarantees to the pro- grammer, such as type safety. A more novel property aimed at protecting network availability is a guarantee that PLAN programs use a bounded amount of space and time on active routers and bandwidth in the network.

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

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

Running EveryWare on the computational grid - Wolski,R.; Brevik,J.; Krintz,C.; Obertelli,G.; Spring, Neil; Su,A. (Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), 1999)

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

Special effect edit detection using VideoTrails: a comparison with existing techniques - Kobla,V.; DeMenthon,D.; David Doermann (Proceedings of SPIE - Conference on Storage and Retrieval for Image and Video Databases VII, 1999)
Video Segmentation plays an integral role in many multimedia applications such as digital libraries, content management systems, and various other video browsing, indexing, and retrieval systems. Many algorithms for segmentation of video have appeared in the past few years, Most of these algorithms perform well on cuts, but yield poor performance on gradual transitions or special effect edits. A complete video segmentation system must achieve good performance on special effect edit detection also. In this paper, we discuss the performance of our VideoTrails based algorithms with other existing special effect edit detection algorithms in literature. Results from experiments testing for the ability to detect edits from TV programs ranging from commercials to news magazine programs, and also diverse special effect edits introduced by us have been shown.

Specifying the PLAN Network Programming Langauge - Kakkar,Pankaj; Hicks, Michael W.; Moore,Jon; Gunter,Carl A. (Electronic Notes in Theoretical Computer Science, 1999)
We discuss how the specification of the PLAN programming language supports the design objectives of the language. The specification aims to provide a mathematically precise operational semantics that can serve as a standard for implementing interpreters and portable programs. The semantics should also support proofs of key properties of PLAN that would hold of all conformant implementations. This paper discusses two such properties. (1) Type checking is required, but interpreters are given significant flexibility about when types are checked; the specification must support a clear description of the possible behaviors of a network of conformant implementations. (2) It is essential to have guarantees about how PLAN programs use global resources, but the specification must be flexible about extensions in the network service layer. We illustrate on of kind of issue that will arise in using to specification to prove properties of the network based on the choice of services.

Text Enhancement in Digital Video - Li,H.; Kia,O.; David Doermann (Proceedings of SPIE - Conference on Document Recognition and Retrieval VI, 1999)

Transparent communication for distributed objects in Java - Hicks, Michael W.; Jagannathan,Suresh; Kelsey,Richard; Moore,Jonathan T.; Ungureanu,Cristian (Proceedings of the ACM 1999 conference on Java Grande, 1999)

3-D Device Simulation Using Intelligent Solution Method Control - Kerr,D. C.; Mayergoyz, Issak D (VLSI DESIGN, 1998)
In this paper, a hybrid solution method is implemented for solving the semiconductor trans-port equations. The hybrid "local Newton" method consists of a combination of the fixed- point iteration (FPI) and Newton’s methods. The FPI technique is nearly ideally suitedto solving large, 3-D systems of semiconductor equations on machines of limited computer memory however,it has certain limitations. This motivates the local Newton method, which coordinates the use of both the FPI and Newton’s methods, for convergence faster than either method alone.

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

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

Approximation algorithms for connected dominating sets - Guha,S.; Khuller, Samir (Algorithmica, 1998)
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication.Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c n +1) \ln n where c n ln k is the approximation factor for the node weighted Steiner tree problem (currently c n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ).

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

Automated recovery in a secure bootstrap process - Arbaugh, William A.; Keromytis,A. D; Farber,D. J; Smith,J. M (Proceedings of the Symposium on Network and Distributed Systems Security (NDSS’98), 1998)

Automatic Text Detection and Tracking in Digital Video - Li,H.; David Doermann; Kia,O. (University of Maryland, College Park, 1998)
Text which either appears in a scene or is graphically added to video can provide an important supplemental source of index information as well as clues for decoding the video's structure and for classification. In this paper we present algorithms for detecting and tracking text components that appear within digital video frames. Our system implements a scale-space feature extractor that feeds an artificial neural processor to extract textual regions and track their movement over time. The extracted regions can then be used as input to an appropriate Optical Character Recognition system which produces indexible keywords.

Beyond the Epipolar Constraint: Integrating 3D Motion and Structure Estimation - Brodský,Tomáš; Fermüller, Cornelia; Aloimonos, J. (3D Structure from Multiple Images of Large-Scale Environments3D Structure from Multiple Images of Large-Scale Environments, 1998)
This paper develops a novel solution to the problem of recovering the structure of a scene given an uncalibrated video sequence depicting the scene. The essence of the technique lies in a method for recovering the rigid transformation between the different views in the image sequence. Knowledge of this 3D motion allows for self-calibration and for subsequent recovery of 3D structure. The introduced method breaks away from applying only the traditionally used epipolar constraint and introduces a new constraint based on the interaction between 3D motion and shape. Up to now, structure from motion algorithms proceeded in two well defined steps, where the first and most important step is recovering the rigid transformation between two views, and the subsequent step is using this transformation to compute the structure of the scene in view. Here both aforementioned steps are accomplished in a synergistic manner. Existing approaches to 3D motion estimation are mostly based on the use of optic flow which however poses a problem at the locations of depth discontinuities. If we knew where depth discontinuities were, we could (using a multitude of approaches based on smoothness constraints) estimate accurately flow values for image patches corresponding to smooth scene patches; but to know the discontinuities requires solving the structure from motion problem first. In the past this dilemma has been addressed by improving the estimation of flow through sophisticated optimization techniques, whose performance often depends on the scene in view. In this paper the main idea is based on the interaction between 3D motion and shape which allows us to estimate the 3D motion while at the same time segmenting the scene. If we use a wrong 3D motion estimate to compute depth, then we obtain a distorted version of the depth function. The distortion, however, is such that the worse the motion estimate, the more likely we are to obtain depth estimates that are locally unsmooth, i.e., they vary more than the correct ones. Since local variability of depth is due either to the existence of a discontinuity or to a wrong 3D motion estimate, being able to differentiate between these two cases provides the correct motion, which yields the “smoothest” estimated depth as well as the image locations of scene discontinuities. Although no optic flow values are computed, we show that our algorithm is very much related to minimizing the epipolar constraint when the scene in view is smooth. When however the imaged scene is not smooth, the introduced constraint has in general different properties from the epipolar constraint and we present experimental results with real sequences where it performs better.

BFGS with Update Skipping and Varying Memory - Kolda,Tamara G.; O'Leary, Dianne P.; Nazareth,Larry (SIAM Journal on Optimization, 1998)
We give conditions under which limited-memory quasi-Newton methods with exact line searches will terminate in n steps when minimizing n-dimensional quadratic functions. We show that although all Broyden family methods terminate in n steps in their full-memory versions, only BFGS does so with limited-memory. Additionally, we show that full-memory Broyden family methods with exact line searches terminate in at most n + p steps when p matrix updates are skipped. We introduce new limited-memory BFGS variants and test them on nonquadratic minimization problems.
Keywords: bfgs; Broyden family; limited-memory; minimization; quasi-Newton; update skipping

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

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

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

A Comparative Study of Knowledge-Based Approaches for Cross-Language - Oard, Douglas; Dorr, Bonnie J; Hackett,P.; Katsova,M. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
Cross-language retrieval systems seek to use queries in one natural language to guide theretrieval of documents that might be written in another. Acquisition and representation of translation knowledge plays a central role in this process. This paper explores the util- ity of two sources of manually encoded translation knowledge, bilingual dictionaries and translation lexicons, for cross-language retrieval. We have implemented six query trans- lation techniques that use bilingual dictionaries, one based on lexical-semantic analysis, and one based on direct use of the translation output from an existing machine transla- tion system; these are compared with a document translation technique that uses output from the same existing translation system. Average precision measures on portions of the TREC collection suggest that arbitrarily selecting a single translation from a bilingual dictionary is typically no less effective than using every translation in the dictionary, that query translation using an existing machine translation system can achieve some- what better effectiveness than simple dictionary-based techniques, and that performing document translation rather than query translation may result in further improvements in retrieval effectiveness under some conditions.

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.

The detection of duplicates in document image databases - David Doermann; Huiping Li; Kia,Omid (Image and Vision Computing, 1998)
Document imaging technology has developed to the point where it is not uncommon for organizations to scan large numbers of documents into databases with little or no index information. This may be done for archival purposes with an index as simple as a case number, or with the ultimate goal of automatically extracting index information for content-based queries. Maintaining the integrity of such a database is difficult, however, especially in a distributed environment where copies of the same documents may be scanned at different times.In this paper we present a novel approach to detecting duplicate documents in very large databases using only features extracted from the image. The method is based on a robust `signature' extracted from each document image which is used to index into a table of previously processed documents. The system is able to deal with differences between scanned document instances such resolution, skew and image quality. The approach has a number of advantages over OCR or other recognition-based methods including speed and robustness to imaging distortions. To justify the approach and demonstrate its scalability, we have developed a simulator which allows us to change parameters of the system and examine performance while processing millions of document signatures. A complete system has been implemented and tested on a collection of technical articles and memos.
Keywords: Document image databases; Document indexing; Duplicate detection; Shape coding

Developing High-Level Representations of Video Clips using VideoTrails - Kobla,V.; David Doermann; Faloutsos,C. (Proceedings of the SPIEConference on Storage and Retrieval for Image and Video Databases VI, 1998)
A high-level representation of a video clip comprising information about its physical and semantic structure isnecessary for providing appropriate processing, indexing and retrieval capabilities for video databases. We describe a novel technique which reduces a sequence of MPEG encoded video frames to a trail of points in a low dimensional space. In our earlier work, we presented techniques applicable in 3-D, but in this paper, we describe techniques that can be extended to higher dimensions where improved performance is expected. In the low-dimensional space, we can cluster frames, analyze transitions between clusters and compute properties of the resulting trail. Portions of the trail can be classi ed as either stationary or transitional, leading to high-level descriptions of the video. Tracking the interaction of clusters over time, we lay the groundwork for the complete analysis and representation of the video's physical and semantic structure.

DHCP++: Applying an efficient implementation method for fail-stop cryptographic protocols - Arbaugh, William A.; Keromytis,A. D; Smith,J. M (Proceedings of Global Internet (GlobeCom)’98, 1998)

Document Image Coding for Processing and Retrieval - Kia,O.; David Doermann (Journal of VLSI Signal Processing, 1998)
Document images belong to a unique class of images where the information is embedded in the language represented by a series of symbols on the page rather than in the visual objects themselves. Since these symbols tend to appear repeatedly, a domain-specific image coding strategy can be designed to facilitate enhanced compression and retrieval. In this paper we describe a coding methodology that not only exploits component-level redundancy to reduce code length but also supports efficient data access. The approach identifies and organizes symbol patterns which appear repeatedly. Similar components are represented by a single prototype stored in a library and the location of each component instance is coded along with the residual between it and its prototype. A representation is built which provides a natural information index allowing access to individual components. Compression results are competitive and compressed-domain access is superior to competing methods. Applications to network-related problems have been considered, and show promising results.

Elastic windows: design, implementation, and evaluation of multi‐window operations - Kandogan,Eser; Shneiderman, Ben (Software: Practice and Experience, 1998)
Most windowing systems follow the independent overlapping windows approach, which emerged as an answer to the needs of early computer users. Due to advances in computers, display technology, and increased information needs, modern users demand more functionality from window management systems. We propose Elastic Windows with improved spatial layout and rapid multi-window operations as an alternative to current window management strategies. In this approach, multi-window operations are achieved by issuing operations on window groups hierarchically organized in a space-filling tiled layout similar to TreeMaps.1 Sophisticated multi-window operations have been developed to handle fast task-switching and to structure the work environment of users to their rapidly changing needs. We claim that these multi-window operations and the tiled spatial layout dynamics decrease the cognitive load on users by decreasing the number of window operations. This paper describes the Elastic Windows interface in detail and then presents a user study conducted to compare the performance of 12 users with Elastic Windows and traditional Independent Overlapping Windows. User performance was measured in terms of task environment setup, switching, and task execution for 2, 6, and 12 window situations. Elastic Windows users had statistically significantly faster performance for all tasks in 6 and 12 window situations. These results suggest promising possibilities for multiple window operations and hierarchical nesting, which can be applied to the next generation of tiled as well as overlapped window managers. © 1998 John Wiley & Sons, Ltd.
Keywords: hierarchical windows; multi‐window operations; personal role management; window management; windowing system evaluation; World Wide Web

Engagement Theory: A Framework for Technology-Based Teaching and Learning. - Kearsley,Greg; Shneiderman, Ben (Educational TechnologyEducational Technology, 1998)
Discusses engagement theory (students meaningfully engaged in learning activities through interaction with others and worthwhile tasks) and the three components, collaboration, project orientation, and authentic focus, and outlines research questions to establish its efficacy. (PEN)
Keywords: Computer Uses in Education; Cooperation; Educational Technology; Educational Theories; Instructional Effectiveness; interaction; Learning Activities; Research Needs; Student Motivation; Student Projects; Teaching Methods

Facility Location with Dynamic Distance Functions - Khuller, Samir; Sussmann,Y. J; Bhatia,Randeep; Guha,Sudipto (Journal of Combinatorial Optimization, 1998)
Facility location problems have always been studied with theassumption that the edge lengths in the network are static anddo not change over time. The underlying network could be used to model a city street networkfor emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to trafficcongestion the traversal time on links changes with time. Very often, we have estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) ascenters, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results forthe K-center problem under this model. This is the first comprehensive study regarding approximation algorithmsfor facility location for good time-invariant solutions.

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

Greedy strikes back: improved facility location algorithms - Guha,Sudipto; Khuller, Samir (Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, 1998)

Hydrodynamic Device Simulation with New State Variables Specially Chosen a Block Gummel Iterative Approach - Liang,W.; Kerr,D. C.; Goldsman,N.; Mayergoyz, Issak D (VLSI DESIGN, 1998)
A new numerical formulation for solving the hydrodynamic model of semiconductor devicesis presented. Themethod is based on using new variables to transform the conventional hydrodynamic equations into forms which facilitatenumerical evaluation with a block Gum- mel approach. To demonstrate the new method, we apply it to model a 0.35 wn 2-D LDD MOSFET, where robust convergence properties are observed.

Indexing and Retrieval of MPEG-compressed video - Kobla,V.; David Doermann (The Journal of Electronic Imaging, 1998)
To keep pace with the increased popularity of digital video as an archival medium, thedevelopment of techniques for fast and e cient analysis of video streams is essential. In particular, solutions to the problems of storing, indexing, browsing, and retrieving video data from large multimedia databases are necessary to allow access to these collections. Given that video is often stored e ciently in a compressed format, the costly overhead of decompression can be reduced by analyzing the compressed representation directly. In earlier work, we presented compressed domain parsing techniques which identi ed shots, subshots, and scenes. In this paper, we present e cient key frame selection, feature extraction, indexing, and retrieval techniques that are directly applicable to MPEG compressed video. We develop a frame type independent representation which normalizes spatial and temporal features including frame type, frame size, macroblock encoding, and motion compensation vectors. Features for indexing are derived directly from this representation and mapped to a low- dimensional space where they can be accessed using standard database techniques. Spatial information is used as primary index into the database and temporal information is used to rank retrieved clips and enhance the robustness of the system. The techniques presented enable e cient indexing, querying, and retrieval of compressed video as demonstrated by our system which typically takes a fraction of a second to retrieve similar video scenes from a database, with over 95% recall.

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

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

Lexical Selection for Cross-Language Applications: Combining LCS with WordNet - Dorr, Bonnie J; Katsova,Maria (Machine Translation and the Information SoupMachine Translation and the Information Soup, 1998)
This paper describes experiments for testing the power of large-scale resources for lexical selection in machine translation (MT) and cross-language information retrieval (CLIR). We adopt the view that verbs with similar argument structure share certain meaning components, but that those meaning components are more relevant to argument realization than to idiosyncratic verb meaning. We verify this by demonstrating that verbs with similar argument structure as encoded in Lexical Conceptual Structure (LCS) are rarely synonymous in WordNet. We then use the results of this work to guide our implementation of an algorithm for cross-language selection of lexical items, exploiting the strengths of each resource: LCS for semantic structure and WordNet for semantic content. We use the Parka Knowledge-Based System to encode LCS representations and WordNet synonym sets and we implement our lexical-selection algorithm as Parka-based queries into a knowledge base containing both information types.

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

Models and high-performance algorithms for global BRDF retrieval - Zengyan Zhang; Kalluri, SNV; JaJa, Joseph F.; Liang,Shunlin; Townshend,J.R.G. (Computational Science Engineering, IEEE, 1998)
The authors describe three models for retrieving information related to the scattering of light on the Earth's surface. Using these models, they've developed algorithms for the IBM SP2 that efficiently retrieve this information
Keywords: algorithms; BRDF; Earth; geomorphology; geophysical; global; high-performance; IBM; information; light; machines; models; Parallel; processing; reflectivity; retrieval; retrieval; scattering; signal; SP2; surface

A New Method to Recover Vectorial Electric Fields and Current Densities from Unstructured Meshes - Kerr,D. C.; Mayergoyz, Issak D (VLSI DESIGN, 1998)
In the context of 2-D and 3-D unstructured mixed-element meshes, a new method of recover-ing vectorial fields and currents in multidimensional simulation is introduced. The new method, called the method of edge elements, directly interpolates the projections of the vec- tors on the edges of an element into its interior. The new method is compared to two other recovery methods on the basis of resolution, consistency, and implementation ease.

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

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

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

Providing Advisory Notices for UNIX Command Users: Design, Implementation, and Empirical Evaluations - Kuah,Boon-Teck; Shneiderman, Ben (Technical Reports of the Computer Science Department, 1998)
UNIX Notices (UN) was developed to study the problems in providing advice tousers of complex systems. The issues studied were: what, when, and how to present the advice. The first experiment with 24 subjects examined how different presentation styles affect the effectiveness of UNs advice. The three presentation styles studied were: notice appears in separate window; notice appears only on request; notice appears in users window immediately. The results showed that the third style was significantly more effective than the first style. Furthermore, the results indicated that the most effective presentation method is also the most disruptive. The second experiment with 29 subjects studied how delay in the advice feedback affects the performance of UN. The treatments were: immediate feedback, feedback at end of session, and no feedback. Over a period of 6 weeks, the commands entered by the subjects were logged and studied. The results showed that immediate feedback caused subjects to repeat significantly fewer inefficient command sequences. However, immediate feedback and feedback at end of session may have given subjects a negative feeling towards UNIX. (Also cross-referenced as CAR-TR-651)
Keywords: Technical Report

Safety and security of programmable network infrastructures - Alexander,S.; Arbaugh, William A.; Keromytis,A. D; Smith,J. M (IEEE Communications Magazine, 1998)
Safety and security are two reliability properties of a system. A “safe” system provides protection against errors of trusted users, while a “secure” system protects against errors introduced by untrusted users. There is considerable overlap between mechanisms to support each property. Requirements for rapid service creation have stimulated the development of programmable network infrastructures, where end users or service providers can customize the properties of a network infrastructure while it continues to operate. A central concern of potential users of such systems is their reliability and, most specifically, their safety and security. In this article we explain the impact the network service model and architecture have on safety and security, and provide a model with which policies can be translated into restrictions of a general system. We illustrate these ideas with the Secure Active Network Environment (SANE) architecture, which provides a means of controlling access to the functions provided by any programmable infrastructure
Keywords: Access control; error protection; IP networks; Multicast protocols; network architecture; network operating systems; network service model; operating system; Power system dynamics; Power system modeling; Power system reliability; programmable languages; programmable network infrastructures; programming languages; Proposals; Protection; reliability properties; Safety; Secure Active Network Environment; Security; security of data; service creation; service providers; Switches; telecommunication computing; telecommunication network reliability; Web and internet services

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

A secure active network environment architecture: realization in SwitchWare - Alexander,D. S; Arbaugh, William A.; Keromytis,A. D; Smith,J. M (IEEE Network, 1998)
An active network is a network infrastructure which is programmable on a per-user or even per-packet basis. Increasing the flexibility of such network infrastructures invites new security risks. Coping with these security risks represents the most fundamental contribution of active network research. The security concerns can be divided into those which affect the network as a whole and those which affect individual elements. It is clear that the element problems must be solved first, since the integrity of network-level solutions will be based on trust in the network elements. In this article we describe the architecture and implementation of a secure active network environment (SANE), which we believe provides a basis for implementing secure network-level solutions. We guarantee that a node begins operation in a trusted state with the AEGIS secure bootstrap architecture. We guarantee that the system remains in a trusted state by applying dynamic integrity checks in the network element's runtime system, using a novel naming system, and applying node-to-node authentication when needed. The construction of an extended LAN is discussed
Keywords: access protocols; AEGIS secure bootstrap architecture; architecture; Authentication; Collaboration; Communication switching; dynamic integrity checks; extended LAN; Functional programming; implementation; integrity; Intelligent networks; IP networks; Local area networks; network infrastructure; network infrastructures; network operating systems; network-level solutions; node; node-to-node authentication; packet switching; Proposals; ramming system; SANE; secure active network environment architecture; security of data; Switches; SwitchWare; trusted state; Web and internet services

A semidiscrete matrix decomposition for latent semantic indexing information retrieval - Kolda,Tamara G.; O'Leary, Dianne P. (ACM Trans. Inf. Syst., 1998)
The vast amount of textual information available today is useless unless it can be effectively and efficiently searched. The goal in information retrieval is to find documents that are relevant to a given user query. We can represent and document collection by a matrix whose (i, j) entry is nonzero only if the ith term appears in the jth document; thus each document corresponds to a columm vector. The query is also represented as a column vector whose ith term is nonzero only if the ith term appears in the query. We score each document for relevancy by taking its inner product with the query. The highest-scoring documents are considered the most relevant. Unfortunately, this method does not necessarily retrieve all relevant documents because it is based on literal term matching. Latent semantic indexing (LSI) replaces the document matrix with an approximation generated by the truncated singular-value decomposition (SVD). This method has been shown to overcome many difficulties associated with literal term matching. In this article we propose replacing the SVD with the semidiscrete decomposition (SDD). We will describe the SDD approximation, show how to compute it, and compare the SDD-based LSI method to the SVD-based LSI methods. We will show that SDD-based LSI does as well as SVD-based LSI in terms of document retrieval while requiring only one-twentieth the storage and one-half the time to compute each query. We will also show how to update the SDD approximation when documents are added or deleted from the document collection.
Keywords: data mining; latent semantic indexing; semidiscrete decomposition; singular-value decomposition; text retrieval

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

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

Text Extraction and Recognition in Digital Video - Li,H.; David Doermann; Kia,O. (Proceedings of Third IAPRWorkshop on Document Analysis Systems, 1998)

Three-Dimensional Hydrodynamic Modeling of MOSFET Devices - Kerr,Daniel C.; Goldsman,Neil; Mayergoyz, Issak D (VLSI Design, 1998)
The hydrodynamic (HD) model of semiconductor devices is solved numerically inthree-dimensions (3-D) for the MOSFET device. The numerical instabilities of the HD model are analyzed to develop a stable discretization. The formulation is stabilized by using a new, higher-order discretization for the relaxation-time approximation (RTA) term of the energy-balance (EB) equation. The developed formulation is used to model the MOSFET.

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)

Using elastic windows for World-Wide Web Browsing - Kandogan,Eser; Shneiderman, Ben (CHI 98 conference summary on Human factors in computing systems, 1998)
Keywords: elastic windows; User interfaces; window management; World-wide web

Video Summarization by Curve Simplification - DeMenthon,Daniel; Kobla,Vikrant; David Doermann (University of Maryland, College Park, 1998)
A video sequence can be represented as a trajectory curve in a high dimensional feature space. This emphvideo curve can be analyzed by tools similar to those developed for planar curves. In particular, the classic binary curve splitting algorithm has been found to be a useful tool for video analysis. With a splitting condition that checks the dimensionality of the curve segment being split, the video curve can be recursively simplified and represented as a tree structure, and the frames that are found to be junctions between curve segments at different levels of the tree can be used as keyframes to summarize the video sequences at different levels of detail. These keyframes can be combined in various spatial and temporal configurations for browsing purposes. We describe a simple video player that displays the keyframes sequentially and lets the user change the summarization level on the fly with a slider. We also describe an approach to automatically selecting a summarization level that provides a concise and representative set of keyframes.

Video Summarization by Curve Simplification - DeMenthon,D.; David Doermann; Kobla,V. (Proceedings of ACM - Multimedia 98, Bristol, England, 1998)
A video sequence can be represented as a trajectory curve in a high dimensional feature space. This emphvideo curve can be analyzed by tools similar to those developed for planar curves. In particular, the classic binary curve splitting algorithm has been found to be a useful tool for video analysis. With a splitting condition that checks the dimensionality of the curve segment being split, the video curve can be recursively simplified and represented as a tree structure, and the frames that are found to be junctions between curve segments at different levels of the tree can be used as keyframes to summarize the video sequences at different levels of detail. These keyframes can be combined in various spatial and temporal configurations for browsing purposes. We describe a simple video player that displays the keyframes sequentially and lets the user change the summarization level on the fly with a slider. We also describe an approach to automatically selecting a summarization level that provides a concise and representative set of keyframes.

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

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

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

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

Collabcad: A toolkit for integrated synchronous and asynchronous sharing of cad applications - Mishra,P.; Varshney, Amitabh; Kaufman,A. (Proceedings TeamCAD: GVU/NIST Workshop on Collaborative Design, Atlanta, GA, USA, 1997)
We are developing CollabCAD, a novel software architecture and toolkit, that supports shar-ing of arbitrary user-defined objects or applications over intranets and the internet. Developers can use CollabCAD to rapidly re-engineer existing CAD applications to be collaboration-capable or build new collaboration-capable CAD applications. CollabCAD provides the following functionalities: 1. Support for fiexible forms of sharing in which users can interact with multiple presentations of CAD applications or objects. 2. asynchronous and synchronous sharing, as well as a mixture of both, 3. effective communication between users by supporting direct manipulation of user-defined objects, and a new form of sharing called para-synchronous sharing, 4. support for asymmetric collaborations between users with 1 different roles, or, 2 systems with different input-output, hardware and network capabilities. We plan to test and evaluate CollabCAD by building collaboration systems in several CAD- oriented application areas: these include virtual reality for mechanical, architectural and molec- ular CAD, and volume visualization and volume graphics for CAD applications.

Comments on "Towards a framework for software measurement validation" - Morasca,S.; Briand,L.C.; Basili, Victor R.; Weyuker,E.J.; Zelkowitz, Marvin V; Kitchenham,B.; Lawrence Pfleeger,S.; Fenton,N. (Software Engineering, IEEE Transactions on, 1997)
A view of software measurement that disagrees with the model presented by Kitchenham, Pfleeger, and Fenton (1995), is given. Whereas Kitchenham et al. argue that properties used to define measures should not constrain the scale type of measures, the authors contend that that is an inappropriate restriction. In addition, a misinterpretation of Weyuker's (1988) properties is noted.
Keywords: measurement; metrics; software; testing; program; validation; program; verification; software

Compressed Domain video indexing techniques using DCT and motion vector information in MPEG video - Kobla,V.; David Doermann; Lin,K-I.; Faloutsos,C. (Proceedings of SPIE - conference on Storage and Retrieval for Image and Video Databases V, 1997)
Development of various multimedia applications hinges on the availability of fast and e cient storage, brows-ing, indexing, and retrieval techniques. Given that video is typically stored e ciently in a compressed format, if we can analyze the compressed representation directly, we can avoid the costly overhead of decompressing and operating at the pixel level. Compressed domain parsing of video has been presented in earlier work where a video clip is divided into shots, subshots, and scenes. In this paper, we describe key frame selection, feature extraction, and indexing and retrieval techniques that are directly applicable to MPEG compressed video. We develop a frame-type independent representation of the various types of frames present in an MPEG video in which all frames can be considered equivalent. Features are derived from the available DCT, macroblock, and motion vector information and mapped to a low-dimensional space where they can be accessed with standard database techniques. The spatial information is used as primary index while the temporal information is used to enhance the robustness of the system during the retrieval process. The techniques presented enable fast archiv- ing, indexing, and retrieval of video. Our operational prototype typically takes a fraction of a second to retrieve similar video scenes from our database, with over 95% success.

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

The Detection of Duplicates in Document Image Databases - David Doermann; Li,H.; Kia,O. (ICDAR, 1997)
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.

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)

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

Elastic Windows: a hierarchical multi-window World-Wide Web browser - Kandogan,E.; Shneiderman, Ben (Proceedings of the 10th annual ACM symposium on User interface software and technology, 1997)

Elastic Windows: evaluation of multi-window operations - Kandogan,E.; Shneiderman, Ben (Proceedings of the SIGCHI conference on Human factors in computing systems, 1997)

Extracting Features for Indexing MPEG-Compressed Video - Kobla,V.; David Doermann (Proceedings of the IEEEFirst Workshop on Multimedia Signal Processing, 1997)

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

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

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

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

Integrated Segmentation and Clustering for Enhanced Compression of Document Images - Kia,Omid E; David Doermann (ICDAR, 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.

OCR-based rate-distortion analysis of residual coding - Kia,O. E; David Doermann (Image Processing, 1997. Proceedings., International Conference on, 1997)
Symbolic compression of document images provides access to symbols found in document images and exploits the redundancy found within them. Document images are highly structured and contain large numbers of repetitive symbols. We have shown that while symbolically compressing a document image we are able to perform compressed-domain processing. Symbolic compression forms representative prototypes for symbols and encode the image by the location of these prototypes and a residual (the difference between symbol and prototype). We analyze the rate-distortion tradeoff by varying the amount of residual used in compression for both distance- and row-order coding. A measure of distortion is based on the performance of an OCR system on the resulting image. The University of Washington document database images, ground truth, and OCR evaluation software are used for experiments
Keywords: analysis; redundancy; representative; character; coding; distortion; coding; image; coding; lossy; coding; row-order; coding; symbolic; compression; data; compression; document; compression; lossy; database; distortion; Evaluation; image; images; document; images; experiments; ground; measure; document; OCR; of; performance; University; processing; distance-order; processing; image; prototypes; residual; recognition; rate; representation; optical; representation; progressive; software; OCR; system; theory; transmission; rate-distortion; truth; image; Washington; compressed-domain

The role of compressed document images in transmission and retrieval - Kia,O.; David Doermann (Multimedia Signal Processing, 1997., IEEE First Workshop on, 1997)
Document images belong to a unique class of images where the information content is contained in the language represented by a series of symbols on the page, rather than in the visual objects themselves. For this reason, it is essential to preserve the fidelity of individual components when considering methods of compression. Likewise the component level structure should be a prime consideration when ordering information for lossy or progressive transmission. We refine our work on document image compression as it applies to transmission and retrieval. We first overview the basic compression scheme, then describe a structural hierarchy which provides desirable properties for transmission. We present the results of a rate distortion experiment and discuss the implications for network applications
Keywords: applications; progressive; coding; multimedia; component; compression; document; compression; image; computing; query; content; lossy; databases; distortion; experiment; structural; hierarchy; symbols; visual; image; level; objects; data; processing; image; processing; visual; retrieval; image; structure; document; transmission; information; transmission; multimedia; network; transmission; rate

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

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.

Techniques for Automated Testing for Automated Testing of Document Analysis Algorithms - Sauvola,J.; Kauniskangas,H.; David Doermann; Pietikainen,M. (Proceedings of the First Brazilian Symposium on Document Image Analysis, 1997)

User Interfaces for a Complex Robotic Task: A Comparison of Tiles vs. Overlapped Windows - Lane,J. Corde; Kuester,Steven P; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1997)
High complexity tasks, such as remote teleoperation of robotic vehicles, often require multiple windows. For these complex tasks, the windows necessary for task completion, may occupy more area than available on a single visual display unit (VDU). Since the focus of the robotic task constantly changes, modular control panels that can be opened, closed, and moved on the screen are invaluable to the operator. This study describes a specific robotic task and the need for a multi window interface that can be easily manipulated. This paper examines two multi-window management strategies: tiled (fixed size) and arbitrary overlap. Multi-window searches were performed using the two management styles and they were compared on the basis of search completion time and error rates. Results with 35 novice users showed faster completion times for the tiled management strategy than for the arbitrary overlap strategy. Over factors such as the number of windows available, the number of displayed windows workload of opening or closing windows, and effect of learning are discussed.
Keywords: Human computer interaction; overlapped; Systems Integration Methodology; tiled; user interface design; window management

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

VideoTrails: Representing and Visualizing Structure in Video Sequences - Kobla,V.; David Doermann; Faloutsos,C. (Proceedings of the ACMInternational Multimedia Conference, 1997)

Archiving, indexing, and retrieval of video in compressed domain - Kobla,V.; David Doermann; Lin,K-I. (SPIEConference on Multimedia Storage and Archiving Systems, 1996)

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

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.

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

The 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)

Differential expression of the expression site-associated gene I family in African trypanosomes - Morgan,R. W; El‐Sayed, Najib M.; Kepa,J. K; Pedram,M.; Donelson,J. E (Journal of Biological Chemistry, 1996)

Elastic windows: improved spatial layout and rapid multiple window operations - Kandogan,Eser; Shneiderman, Ben (Proceedings of the workshop on Advanced visual interfaces, 1996)
Most windowing systems follow the independent overlapping windows approach, which emerged as an answer to the needs of the 80s' application and technology. Advances in computers, display technology, and the applications demand more functionality from window management systems. Based on these changes and the problems of current windowing appraoches, we have updated the requirements for multiwindow systems to guide new methods of window management. We propose elastic windows with improved spatial layout and rapid multi-window operations. Multi-window operations are achieved by issuing operations on window groups hierachically organized in a space-filling tiled layout. Sophisticated multi-window operations and spatial layout dynamics helps users to handle fast task-switching and to structure thier work environment to their rapidly changing needs. We claim that these multi-window operations and the improved spatial layout decrease the cognitive load on users. Users found our prototype system to be comprehensible and enjoyable as they playfully explored the way multiple windows are reshaped.
Keywords: CAD; elastic windows; multi-window operations; personal role manager; programming environment; task switching; window manager

An empirical exploration of code evolution - Karr,A.; Porter, Adam; Votta,L. (International Workshop on Empirical Studies of Software Maintenance, 1996)

Fast algorithms for removing atmospheric effects from satellite images - Fallah-Adl,H.; JaJa, Joseph F.; Liang, S.; Townshend,J.; Kaufman,Y.J. (Computational Science Engineering, IEEE, 1996)
The varied features of the earth's surface each reflect sunlight and other wavelengths of solar radiation in a highly specific way. This principle provides the foundation for the science of satellite based remote sensing. A vexing problem confronting remote sensing researchers, however, is that the reflected radiation observed from remote locations is significantly contaminated by atmospheric particles. These aerosols and molecules scatter and absorb the solar photons reflected by the surface in such a way that only part of the surface radiation can be detected by a sensor. The article discusses the removal of atmospheric effects due to scattering and absorption, ie., atmospheric correction. Atmospheric correction algorithms basically consist of two major steps. First, the optical characteristics of the atmosphere are estimated. Various quantities related to the atmospheric correction can then be computed by radiative transfer algorithms, given the atmospheric optical properties. Second, the remotely sensed imagery is corrected by inversion procedures that derive the surface reflectance. We focus on the second step, describing our work on improving the computational efficiency of the existing atmospheric correction algorithms. We discuss a known atmospheric correction algorithm and then introduce a substantially more efficient version which we have devised. We have also developed a parallel implementation of our algorithm
Keywords: algorithms; reflectivity; remote; Atmospheric; based; computing; image; correction; atmospheric; effects; atmospheric; efficiency; inversion; enhancement; parallel; imagery; satellite; images; solar; implementation; reflected; particles; computational; photons; surface; procedures; parallel; radiation; atmospheric; radiation; remote; reflectance; atmospheric; remote; research; remotely; sensed; sensing; sensing; sensing; satellite; techniques; geophysics

Feature Normalization for Video Indexing and Retrieval - Kobla,Vikrant; David Doermann; Lin,King-Ip (David); Faloutsos,Christos (University of Maryland, College Park, 1996)
Fast and efficient storage, browsing, indexing, and retrieval of video is necessary for the development of various multimedia database applications. Given that video is typically stored efficiently in a compressed format, if we can analyze the compressed representation directly, we can avoid the costly overhead of decompressing and operating at the pixel level. Compressed domain parsing of video has been presented in earlier work where key frames are identified for shots, subshots, and scenes. In this paper, we describe key frame selection, feature extraction, indexing, and retrieval techniques that are directly applicable to MPEG-compressed video. We develop a frame-type independent representation of the various types of frames present in an MPEG video in which all frames can be considered equivalent. Features are derived from the available DCT, macroblock, and motion vector information and mapped to a low-dimensional space where they can be accessed using standard database techniques. The spatial information is used as primary index while the temporal information is used to enhance the robustness of the system during the retrieval process. The techniques presented enable fast archiving, indexing, and retrieval of video. Our operational prototype typically takes a fraction of a second to retrieve similar video scenes from our database, with over 95% success.

FINESSE: a financial information spreadsheet - Varshney, Amitabh; Kaufman,A. (Information Visualization '96, Proceedings IEEE Symposium on, 1996)
We outline a spreadsheet-based system for visualization of real-time financial information. Our system permits the user to define arithmetic and presentation relationships amongst the various cells of the spreadsheet. The cells contain primitives that can be numbers, text, images, functions and graphics. Presenting financial information in this format allows its intended clients, the financial analysts, to work in the familiar environment of a spreadsheet and allows them the flexibility afforded by the powerful interface of the spreadsheet paradigm. In addition, our system permits real-time visualization of the financial data stream allowing its user to visually trade the changing market trends in two and three dimensions
Keywords: cells; text; three; data; dimensions; two; dimensions; user; financial; FINESSE; arithmetic; data; information; information; spreadsheet; interface; data; interfaces; presentation; market; processing; real-time; programs; user; spreadsheet; functions; graphics; images; information; systems; spreadsheet; trends; numbers; presentation; real-time; visualisation; financial; visualization; financial

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.

Simulation of the logic switching characteristics of hot-carrier-degraded ultra-thin SOI CMOS inverters - Tai,Gwo-Chung; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1996)
The switching characteristics of ultra-thin SOI CMOS inverters with hot-carrier-induced degradations are examined by using device simulations. The simulator employs a robust fixed-point iteration method to avoid conventional matrix solutions. Potential-dependent interface traps and oxide trapped charges are used to model the degradations. The effects of front and back channel degradations in an nMOS device of a CMOS inverter are investigated in steady-state and transient regimes. The nonlinear variation of interface charges cannot be simulated by using a single nMOS device alone since the transition of the inverter is also determined by the pMOS transistor. It is found that the stagnant holes generated by impact ionization have a much greater effect on the rate of the pull-down transient than that of interface charges.

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.

Structural compression for document analysis - Kia,O. E; David Doermann (Pattern Recognition, 1996., Proceedings of the 13th International Conference on, 1996)
In this paper we describe a structural compression technique to be used for document text image storage and retrieval. The primary objective is to provide an efficient representation, storage, transmission and display. A secondary objective is to provide an encoding which allows access to specified regions within the image and facilitates traditional document processing operations without requiring complete decoding. We describe an algorithm which symbolically decomposes a document image and structurally orders the error bitmap based on a probabilistic model. The resultant symbol and error representations lend themselves to reasonably high compression ratios and are structured so as to allow operations directly on the compressed image. The compression scheme is implemented and compared to traditional compression methods
Keywords: analysis; document; bitmap; error; coding; image; compression; compression; document; compression; symbol; decomposition; data; image; manipulation; processing; image; ratios; document; recognition; probability; symbol; representations; structural; representations; symbolic; retrieval; document; storage; error; text

Structure Preserving Document Image Compression and Transmission - Kia,O.; David Doermann (ICIP, 1996)

A three-dimensional MOSFET solver implementing the fixed point iteration technique - Madabhushi,Rajiv; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1996)
Our implementation of a fixed-point iteration technique for the three-dimensional (3D) steady-state simulation of MOSFET devices is presented. The simulation program is employed to investigate narrow channel effects on the device current-voltage characteristics. Particularly, the effects of impact ionization and the effects of variations in channel width and the field oxide bird's beak angle are evaluated. The degree to which various field oxide configurations isolate the device from the gate contact over the oxide transition region is determined by comparing the current-voltage characteristics with those of an idealized device with perfect isolation. Perfect isolation is simulated by setting the normal component of the electric field to zero at the semiconductor-field oxide interface. Simulation results show that the 3D computations are essential to account for rapidly varying charge densities and generation rates near the channel edge. Moreover, it is observed that the isolation effects of field oxides increase for larger bird's beak angles.

Tools for creating and exploiting content - Kolker,R.; Shneiderman, Ben (Getty Art History Information Program (1996) Research Agenda for Networked Cultural Heritage, Santa Monica. CA: Getty AHIP, 1996)

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

Visual metaphor and the problem of complexity in the design of Web sites: techniques for generating, recognizing and visualizing structure - Joyce,Michael; Kolker,Robert; Moulthrop,Stuart; Shneiderman, Ben; Unsworth,John Merritt (Proceedings of the the seventh ACM conference on Hypertext, 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)

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

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

Efficient Algorithms for Atmospheric Correction of Remotely Sensed Data - Fallah-Adl,H.; JaJa, Joseph F.; Liang,Shunlin; Kaufman,Y.J.; Townshend,J. (Supercomputing, 1995. Proceedings of the IEEE/ACM SC95 Conference, 1995)
Remotely sensed imagery has been used for developing and validating various studies regarding land cover dynamics. However, the large amounts of imagery collected by the satellites are largely contaminated by the effects of atmospheric particles. The objective of atmospheric correction is to retrieve the surface reflectance from remotely sensed imagery by removing the atmospheric effects. We introduce a number of computational techniques that lead to a substantial speedup of an atmospheric correction algorithm based on using look-up tables. Excluding I/O time, the previous known implementation processes one pixel at a time and requires about 2.63 seconds per pixel on a SPARC-10 machine, while our implementation is based on processing the whole image and takes about 4-20 microseconds per pixel on the same machine. We also develop a parallel version of our algorithm that is scalable in terms of both computation and I/O. Experimental results obtained show that a Thematic Mapper (TM) image (36 MB per band, 5 bands need to be corrected) can be handled in less than 4.3 minutes on a 32-node CM-5 machine, including I/O time.
Keywords: Atmospheric; AVHRR; computing; correction; high; I/O; Parallel; performance; processing; remote; scalable; sensing; TM

Finding Legal Reordering Transformations using Mappings - Pugh, William; Kelly, Wayne (Languages and compilers for parallel computing: 7th International Workshop, Ithaca, NY, USA, August 8-10, 1994: proceedings, 1995)
We present a unified framework for applying iteration reordering transformations. This framework is able to represent traditional transformations such as loop interchange, loop skewing and loop distribution as well as compositions of these transformations. Using a unified framework rather than a sequence of adhoc transformations makes it easier to analyze and predict the effects of these transformations. Our framework is based on the idea that all reordering transformations can be represented as a mapping from the original iteration space to a new iteration space. An optimizing compiler would use our framework by finding a mapping that both corresponds to a legal transformation and produces efficient code. We present the mapping selection problem as a search problem by decomposing it into a sequence of smaller choices. We then characterize the set of all legal mappings by defining a search tree.

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

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.

Hybrid thinning through reconstruction - David Doermann; Kia,O. (Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, 1995)
One difficulty with many pixel-wise thinning algorithms is that they produce unacceptable results at junction points, or in the presence of contour noise. The authors present a novel approach to detecting ambiguous regions in a thinned image. The method uses the reconstructability properties of appropriate thinning algorithms to reverse the thinning process and automatically detect those pixels which may have resulted from more then one stroke in the image. The ambiguous regions are then interpreted and reconstructed using domain specific or derived contextual information. The approach has the advantage of using local methods to rapidly identify strokes (or regions) which have been thinned correctly and allowing more detailed analysis based on non-local methods in the remaining regions
Keywords: algorithms; edge; ambiguous; detection; automatic; detection; contextual; detection; image; information; contour; methods; nonlocal; methods; pixel-wise; noise; hybrid; Pixel; points; local; reconstruction; image; region; segmentation; noise; stroke; junction; thinning; thinning; image

Improved approximation algorithms for uniform connectivity problems - Khuller, Samir; Raghavachari,Balaji (Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 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

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

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

A simple randomized sieve algorithm for the closest-pair problem - Khuller, Samir; Matias,Y. (Information and Computation, 1995)
We present a linear time randomized sieve algorithm for the closest-pair problem. Thealgorithm as well as its analysis are simple. The algorithm is extended to obtain a randomized linear time approximation algorithm for the closest bichromatic pair problem.

Switching as an exit problem - Korman,C.E.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1995)
Previously, it has been shown that Preisach type models driven by stochastic inputs can be employed to model aftereffect. In this model, the machinery of the ldquo;exit problem rdquo; is instrumental in computing the time evolutions of the expected value and the distributions of switching times. Here, for the first time, we present numerical simulation results of the aforementioned viscosity models and demonstrate that these models can be employed to compute switching times and time evolutions of the expected value of magnetization
Keywords: aftereffect; magnetic; aftereffect; stochastic; analysis; distribution; viscosity; force; fluctuations; magnetic; hysteresis; magnetic; inputs; switching; models; coercive; models; exit; Preisach; problem; expected; switching; numerical; times; type; value; magnetization; model

Thinking takes time: a modal active-logic for reasoning in time - Nirkhe,M.; Kraus,S.; Perlis, Don (Proc. of BISFAI-95, 1995)

A unifying framework for iteration reordering transformations - Kelly,W.; Pugh, William (Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP., IEEE First International Conference on, 1995)

Using synthetic perturbations and statistical screening to assay shared-memory programs - Snelick,R.; JaJa, Joseph F.; Kacker,R.; Lyon,G. (Information processing letters, 1995)

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

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)

Biconnectivity approximations and graph carvings - Khuller, Samir; Vishkin, Uzi (Journal of the ACM (JACM), 1994)
A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard.We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity, our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP-hard as well. We also consider the case where the graph has edge weights. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a k-edge connected spanning subgraph. This improves an approximation factor of 3 for k = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any k (with an increased running time though).
Keywords: biconnectivity; connectivity; sparse subgraphs

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

Calibrating, Counting, Grounding, Grouping - Elgot-drapkin,J.; Gordon,D.; Kraus,S.; Miller,M.; Nirkhe,M.; Perlis, Don (Association for the Advancement of Artificial Intelligence, 1994)

Concept-based lexical selection - Dorr, Bonnie J; Voss,C.; Peterson,E.; Kiker,M. (Proceedings of the AAAI-94 Fall Symposium on Knowledge Representation for Natural Language Processing in Implemented Systems, 1994)

Flow in planar graphs with vertex capacities - Khuller, Samir; Naor,J. (Algorithmica, 1994)
Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).

The input dependent Preisach model with stochastic input as a model for aftereffect - Korman,C.E.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 1994)
In a previous work, it has been suggested to use the Preisach model driven by stochastic inputs as a model for aftereffect. Here, we further extend this approach by employing the more accurate nonlinear input dependent Preisach model. The time evolution of the expected value of the output (magnetization) is derived in terms of the stochastic description of the input. It is shown that the mathematical machinery of the ldquo;exit problem rdquo; is instrumental for calculations of time evolutions of the expected value of the output of the nonlinear input dependent Preisach model
Keywords: aftereffect; input; aftereffect; magnetic; dependent; evolutions; magnetic; hysteresis; input; time; model; stochastic; Preisach

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

Introduction: Special issue on building lexicons for machine translation - Dorr, Bonnie J; Klavans,Judith (Machine Translation, 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

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.

On the parallel complexity of digraph reachability - Khuller, Samir; Vishkin, Uzi (Information Processing Letters, 1994)
We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s−t reachability problem.
Keywords: combinatorial problems; Parallel algorithms

A parallel-in-time method for the transient simulation of SOI devices with drain current overshoots - Tai,G.-C.; Korman,C.E.; Mayergoyz, Issak D (Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 1994)
This paper presents a new parallel-in-time algorithm for the two dimensional transient simulation of SOI devices. With this approach, simulation in both space and time domains is performed in parallel As a result, the CPU time is reduced significantly from the conventional serial-in-time method. This new approach fully exploits the inherent parallelism of the finite difference formulation of the basic semiconductor device equations and the massively parallel architecture of SIMD computers. The space domain computations are inherently parallel due to the nature of our technique of solving the finite-difference equations. Time domain parallelism is achieved by shifting the potentials from previous time points to subsequent points one-step forward along the time axis with each Gummel iteration. This algorithm employs a fixed-point iteration technique, therefore a direct solution of matrix equations is avoided. The algorithm is especially suitable for the transient simulation of SOI devices that exhibit transient drain current overshoot. Numerical experiments show that the new parallel-in-time method is up to eight times faster than the conventional serial-in-time method in SOI transient simulations. The program is coded in CM Fortran for the Connection Machine
Keywords: 2D; algorithms; semiconductor; analysis; transient; architecture; parallel-in-time; boundaries; silicon; time-domain; computations; time; computers; SOI; computing; finite; current; device; devices; drain; devices; parallel; difference; dimensional; domain; effect; engineering; equations; fixed-point; equations; space; field; Fortran; CPU; gate; iteration; iteration; SIMD; Machine; Gummel; method; semiconductor; methods; insulated; methods; metal-insulator-semiconductor; models; semiconductor-insulator; overshoots; finite-difference; Parallel; parallelism; transient; response; simulation; CM; simulation; digital; simulation; electronic; simulation; two; technique; massively; time; Connection; transistors; iterative

A primal-dual parallel approximation technique applied to weighted set and vertex covers - Khuller, Samir; Vishkin, Uzi; Young,N. (Journal Algorithms, 1994)

Simulation of the transient characteristics of partially- and fully-depleted SOI MOSFETs - Tai,Gwo-Chung; Korman,Can E.; Mayergoyz, Issak D (Solid-State Electronics, 1994)
We present a numerical technique which employs a local-in-time initial guess for the transient simulation of SOI MOSFETs. Specifically, the goal of this work is to compute the transient drain current which exhibits overshoot. A critical factor in such computations is the choice of the initial guess at each time point after the gate ramp. Our numerical simulations have shown that the use of the previous time point solution as an initial guess in the Gummel iterations fails to predict the decay in the drain current from its maximum overshoot value. This difficulty is circumvented when the steady-state solution is used as a local-in-time initial guess. We use the diagonally implicit Runge-Kutta method for the time domain discretization. A fixed-point iteration technique is employed for the space domain iterations. To demonstrate the usefulness of the local-in-time method, numerical results of the transient drain current for various device parameters, such as the silicon film doping, silicon film thickness and back-gate bias are presented.

Slipped-strand mispairing in a plastid gene: ıt rpoC2 in grasses (Poaceae) - Cummings, Michael P.; King,L. M; Kellogg,E. A (Mol Biol Evol, 1994)
An exception to the generally conservative nature of plastid gene evolution is the gene coding for the beta" subunit of RNA polymerase, rpoC2. Previous work by others has shown that maize and rice have an insertion in the coding region of rpoC2, relative to spinach and tobacco. To assess the distribution of this extra coding sequence, we surveyed a broad phylogenetic sample comprising 55 species from 17 angiosperm families by using Southern hybridization. The extra coding sequence is restricted to the grasses (Poaceae). DNA sequence analysis of 11 species from all five subfamilies within the grass family demonstrates that the extra sequence in the coding region of rpoC2 is a repetitive array that exhibits more than a twofold increase in nucleotide substitution, as well as a large number of insertion/deletion events, relative to the adjacent flanking sequences. The structure of the array suggests that slipped-strand mispairing causes the repeated motifs and adds to the mechanisms through which the coding sequence of plastid genes are known to evolve. Phylogenetic analyses based on the sequence data from grass species support several relationships previously suggested by morphological work, but they are ambiguous about broad relationships within the family.

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

A syntactic approach to scale-space-based corner description - Fermüller, Cornelia; Kropatsch,W. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994)
Planar curves are described by information about corners integrated over various levels of resolution. The detection of corners takes place on a digital representation. To compensate for ambiguities arising from sampling problems due to the discreteness, results about the local behavior of curvature extrema in continuous scale-space are employed
Keywords: Computer vision; corner detection; curvature extrema; edge detection; IMAGE PROCESSING; image resolution; Image segmentation; Laboratories; Large-scale systems; PARALLEL PROCESSING; pattern recognition; planar curves; resolution; Sampling methods; sampling problems; scale space based corner description; SHAPE; Smoothing methods; syntactic approach

Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima - Berkman,Omer; JaJa, Joseph F.; Krishnamurthy,Sridhar; Thurimella,Ramakrishna; Vishkin, Uzi (SIAM Journal on Computing, 1994)
A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size $n$, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ * n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $Ω (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348–355].The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ * n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.
Keywords: Parallel algorithms; pram algorithms; prefix minima; VLSI routing

Approximation Algorithms for Graph Augmentation - Khuller, Samir; Thurimella,R. (Journal of Algorithms, 1993)
The problem of increasing both edge and vertex connectivity of a graph at an optimal cost is studied. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optima]. Previous algorithms either do not take edge costs into consideration, or they run slower than our algorithm. Our algorithm takes as input an undirected graph G0 = (V, E0) on n vertices, that is not necessarily connected, and a set Feasible of m weighted edges on V, and outputs a subset Aug of edges which when added to G0 make it two-connected. The weight of Aug, when G0 is initially connected, is no more than twice the weight of the least weight subset of edges of Feasible that increases the connectivity to two. The running time of our algorithm is O(m + n log n). As a consequence of our results, we can find an approximation to the least-weight two-connected spanning subgraph of a two-connected weighted graph.

Development of machining alternatives, based on MRSEVs - Nau, Dana S.; Gupta,S.K.; Kramer,T. R.; Regli,W. C.; Zhang, G. (Computers in Engineering, 1993)
One missing link between CAD and CAM is the lack ofa systematic methodology for generating and evaluating al- ternative ways to manufacture a proposed design. To ad- dress this problem, we are developing a systematic approach for generating and evaluating alternative ways to manufac- ture machined parts, in order to provide information to the designer about the manufacturability of the proposed de- sign, and information to the process engineer about how best to machine the part. This paper describes our overall approach, and how MRSEVs (Material Removal Shape El- ement Volumes, a STEP library of machining features) can be used to support it.

Evaluating product machinability for concurrent engineering - Nau, Dana S.; Zhang, G.; Gupta,S.K.; Karinthi,R. R. (Concurrent Engineering: Contemporary Issues and Modern Design Tools, 1993)

Geometric knapsack problems - Arkin,E. M; Khuller, Samir; Mitchell,J. S.B (Algorithmica, 1993)
We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following ldquofence enclosurerdquo problem: given a setS ofn points in the plane with valuesv i ge 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the ldquovaluerdquo of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.

The lattice structure of flow in planar graphs - Khuller, Samir; Naor,J. S; Klein,P. (SIAM Journal on Discrete Mathematics, 1993)

Remote direct manipulation: A case study of a telemedicine workstation - Keil-Slawik,R.; Plaisant, Catherine; Shneiderman, Ben (Sparks of innovation in human-computer interactionSparks of innovation in human-computer interaction, 1993)

Restructuring knowledge for an electronic encyclopedia - Kreitzberg,C.B.; Shneiderman, Ben (Sparks of innovation in human-computer interaction, 1993)

Situated reasoning within tight deadlines and realistic space and computation bounds - Nirkhe,M.; Kraus,S.; Perlis, Don (Proc. Common Sense, 1993)

Speech versus mouse commands for word processing: an empirical evaluation - Karl,Lewis R.; Pettey,Michael; Shneiderman, Ben (International Journal of Man-Machine Studies, 1993)
Despite advances in speech technology, human factors research since the late 1970s has provided only weak evidence that automatic speech recognition devices are superior to conventional input devices such as keyboards and mice. However, recent studies indicate that there may be advantages to providing an additional input channel based on speech input to supplement the more common input modes. Recently the authors conducted an experiment to demonstrate the advantages of using speech-activated commands over mouse-activated commands for word processing applications when, in both cases, the keyboard is used for text entry and the mouse for direct manipulation. Sixteen experimental subjects, all professionals and all but one novice users of speech input, performed four simple word processing tasks using both input groups in this counterbalanced experiment. Performance times for all tasks were significantly faster when using speech to activate commands as opposed to using the mouse. On average, the reduction in task time due to using speech was 18·7%. The error rates due to subject mistakes were roughly the same for both input groups, and recognition errors, averaged over all the tasks, occurred for 6·3% of the speech-activated commands. Subjects made significantly more memorization errors when using speech as compared with the mouse for command activation. Overall, the subjects reacted positively to using speech input and preferred it over the mouse for command activation; however, they also voiced concerns about recognition accuracy, the interference of background noise, inadequate feedback and slow response time. The authors believe that the results of the experiment provide evidence for the utility of speech input for command activation in application programs.

Systolic architectures for finite-state vector quantization - Kolagotla,R. K.; Yu,S. S.; JaJa, Joseph F. (The Journal of VLSI Signal Processing, 1993)
We present a new systolic architecture for implementing Finite State Vector Quantization in real-time for both speech and image data. This architecture is modular and has a very simple control flow. Only one processor is needed for speech compression. A linear array of processors is used for image compression; the number of processors needed is independent of the size of the image. We also present a simple architecture for converting line-scanned image data into the format required by this systolic architecture. Image data is processed at a rate of 1 pixel per clock cycle. An implementation at 31.5 MHz can quantize 1024×1024 pixel images at 30 frames/sec in real-time. We describe a VLSI implementation of these processors.

Using MRSEVs to develop machining alternatives - Nau, Dana S.; Gupta,S.K.; Kramer,T. R.; Regli,W. C.; Zhang, G. (1993)

Using Synthetic-Perturbation Techniques for Tuning Shared Memory Programs - Snelick,Robert; JaJa, Joseph F.; Kacker,Raghu; Lyon,Gordon (Parallel Processing, 1993. ICPP 1993. International Conference on, 1993)
The Synthetic-Perturbation Tuning (SPT) methodology is base d on compirical approach that introduces artificial delays into the MIMD program and captures the effects of such delays by using the modrn branch statistics called design of experiments.

Vacuum-logic - Elgot-drapkin,J.; Kraus,S.; Miller,M.; Nirkhe,M.; Perlis, Don (Proceedings of AAAI 1993 Fall Symposium Series: Instantiating Real-World Agents, 1993)

VLSI implementation of a tree searched vector quantizer - Kolagotla,R. K.; Yu,S.-S.; JaJa, Joseph F. (Signal Processing, IEEE Transactions on, 1993)
The VLSI design and implementation of a tree-searched vector quantizer is presented. The number of processors needed is equal to the depth of the tree. All processors are identical, and data flow between processors is regular. No global control signals are needed. The processors have been fabricated using 2 mu;m <e1>N</e1>-well process on a 7.9 times;9.2 mm die. Each processor chip contains 25000 transistors and has 84 pins. The processors have been thoroughly tested at a clock frequency of 20 MHz
Keywords: (mathematics); 2; 20; chips; coding; compression; data; design; digital; image; implementation; MHz; micron; PROCESSING; quantisation; quantizer; searched; signal; tree; TREES; vector; VLSI; VLSI

copia-like retrotransposons are ubiquitous among plants - Voytas,D. F; Cummings, Michael P.; Koniczny,A.; Ausubel,F. M; Rodermel,S. R (Proc Natl Acad Sci USA, 1992)
Transposable genetic elements are assumed to be a feature of all eukaryotic genomes. Their identification, however, has largely been haphazard, limited principally to organisms subjected to molecular or genetic scrutiny. We assessed the phylogenetic distribution of copia-like retrotransposons, a class of transposable element that proliferates by reverse transcription, using a polymerase chain reaction assay designed to detect copia-like element reverse transcriptase sequences. copia-like retrotransposons were identified in 64 plant species as well as the photosynthetic protist Volvox carteri. The plant species included representatives from 9 of 10 plant divisions, including bryophytes, lycopods, ferns, gymnosperms, and angiosperms. DNA sequence analysis of 29 cloned PCR products and of a maize retrotransposon cDNA confirmed the identity of these sequences as copia-like reverse transcriptase sequences, thereby demonstrating that this class of retrotransposons is a ubiquitous component of plant genomes.

On the difficulty of Manhattan channel routing - Greenberg,Ronald; JaJa, Joseph F.; Krishnamurthy,Sridhar (Information Processing Letters, 1992)
We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Ω(n) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
Keywords: combinatorial problems; computational complexity; lower bounds; VLSI channel routing

Efficient minimum cost matching using quadrangle inequality - Aggarwal,A.; Bar-Noy,A.; Khuller, Samir; Kravets,D.; Schieber,B. (Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on, 1992)
The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red cup; Blue, Red times; Blue), where |Red| = n, |Blue| = m, n les; m, and the cost function obeys the quadrangle inequality. The first results assume that all the red points and all the blue points lie on a curve that is homeomorphic to either a line or a circle and the cost function is given by the Euclidean distance along the curve. They present a linear time algorithm for the matching problem. They generalize the method to solve the corresponding transportation problem in O((m+n)log(m+n)) time. The next result is an O(n log m) algorithm for minimum cost matching when the cost array is a bitonic Monge array. An example of this is when the red points lie on one straight line and the blue points lie on another straight line (that is not necessarily parallel to the first one). Finally, they provide a weakly polynomial algorithm for the transportation problem in which the associated cost array is a bitonic Monge array
Keywords: algorithm; array; bipartite; bitonic; blue; complexity; computational; cost; distance; Euclidean; function; geometry; graph; graphs; inequality; linear; MATCHING; matching; minimisation; minimum; Monge; perfect; points; polynomial; problem; quadrangle; red; theory; TIME; transportation; transportation; weakly

Hierarchical curve representation - Fermüller, Cornelia; Kropatsch,W. (, 11th IAPR International Conference on Pattern Recognition, 1992. Vol.III. Conference C: Image, Speech and Signal Analysis, Proceedings, 1992)
Presents a robust method for describing planar curves in multiple resolution using curvature information. The method is developed by taking into account the discrete nature of digital images as well as the discrete aspect of a multiresolution structure (pyramid). The authors deal with the robustness of the technique, which is due to the additional information that is extracted from observing the behavior of corners in the pyramid. Furthermore the resulting algorithm is conceptually simple and easily parallelizable. They develop theoretical results, analyzing the curvature of continuous curves in scale-space, which show the behavior of curvature extrema under varying scale. These results are used to eliminate any ambiguities that might arise from sampling problems due to the discreteness of the representation. Finally, experimental results demonstrate the potential of the method
Keywords: Automation; continuous curves; curvature; data mining; digital images; Educational institutions; Feature extraction; hierarchical curve representation; IMAGE PROCESSING; image recognition; image resolution; Image segmentation; multiresolution structure; Object recognition; planar curves; pyramid; Robustness; Sampling methods; Smoothing methods

Incremental construction and dynamic maintenance of constrained Delaunay triangulations - Kao,T.C.; Mount, Dave (Proceedings of the 4th Canadian Conference on Computational Geometry, 1992)

On independent spanning trees - Khuller, Samir; Schieber,Baruch (Information Processing Letters, 1992)
We prove that if any k-vertex connected graph has k vertex independent spanning trees, then any k-edge connected graph has k edge independent spanning trees. Thus, answering a question raised by Zehavi and Itai [J. Graph Theory 13 (1989)] in the affirmative.
Keywords: combinatorial problems; edge connectivity; spanning trees; vertex connectivity

Multi-resolution shape description by corners - Fermüller, Cornelia; Kropatsch,W. (, 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992. Proceedings CVPR '92, 1992)
A robust method for describing planar curves in multiple resolution using curvature information is presented. The method is developed by taking into account the discrete nature of digital images as well as the discrete aspect of a multiresolution structure (pyramid). The main contribution lies in the robustness of the technique, which is due to the additional information that is extracted from observing the behavior of corners in the whole pyramid. Furthermore, the resulting algorithm is conceptually simple and easily parallelizable. Theoretical results are developed analyzing the curvature of continuous curves in scale-space and showing the behavior of curvature extrema under varying scale. The results are used to eliminate any ambiguities that might arise from sampling problems due to the discreteness of the representation. Experimental results demonstrate the potential of the method
Keywords: ambiguities; Automation; computational geometry; Computer vision; continuous curves; corners; curvature extrema; curvature information; curve fitting; digital images; Feature extraction; IMAGE PROCESSING; image resolution; Image segmentation; Laboratories; multiple resolution; multiresolution structure; parallelizable; planar curves; Robustness; Sampling methods; scale-space; SHAPE; Smoothing methods; varying scale

Parallel computational geometry of rectangles - Chandran,S.; Kim,S. K; Mount, Dave (Algorithmica, 1992)
Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).

Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph - Khuller, Samir; Mitchell,S. G; Vazirani,V. V (SIAM Journal on Computing, 1992)

VLSI Architectures and Implementation of Predictive Tree- Searched Vector Quantizers for Real-Time Video Compression - Yu,S.-S.; Kolagotla,Ravi K.; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1992)
We describe a pipelined systolic architecture for implementing predictive Tree-Searched Vector Quantization (PTSVQ) for real- time image and speech coding applications. This architecture uses identical processors for both the encoding and decoding processes. the overall design is regular and the control is simple. Input data is processed at a rate of 1 pixel per clock cycle, which allows real-time processing of images at video rates. We implemented these processors using 1.2um CMOS technology. Spice simulations indicate correct operation at 40 MHz. Prototype version of these chips fabricated using 2um CMOS technology work at 20 MHz.
Keywords: data compression; IMAGE PROCESSING; Signal processing; Speech processing; Systems Integration; systolic architecture; Vector quantization; VLSI architectures

VLSI Implementation of Real-Time Parallel DCT/DST Lattice Structures for Video - Chiu,Ching-Te; Kolagotla,Ravi K.; Liu,K. J. Ray; JaJa, Joseph F. (Institute for Systems Research, University of Maryland, College Park, 1992)
The alternate use [1] of the discrete cosine transform (DCT) and the discrete sine transform (DST) can achieve a higher data compression rate and less block effect in image processing. A parallel lattice structure that can dually generate the 1-D DCT and DST is proposed. We also develop a fully-pipelined 2-D DCT lattice architecture that consists of two 1-D DCT/DST arrays without transposition. Both architectures are ideally suited for VLSI implementation because they are modular, regular, and have only local interconnections. the VLSI implementation of the lattice module using the distributed arithmetic approach is described. This realization of the lattice module using 2 um CMOS technology can achieve an 80Mb/s data rate.
Keywords: Parallel architectures; Signal processing; Systems Integration; VLSI architectures

Computing generalized Voronoi diagrams in improved time and space bounds - Kao,Thomas C.; Mount, Dave (University of Maryland at College Park, 1991)

Deadline-coupled real-time planning - Kraus,S.; Nirkhe,M.; Perlis, Don (Innovative approaches to planning, scheduling and control: proceedings of a Workshop [on Innovative Approaches to Planning, Scheduling, and Control], held at San Diego, California, November 5-8, 1991, 1991)

Editing to structure a reader's experience - Shneiderman, Ben; Kreitzberg,C.; Berk,E. (Hypertext/hypermedia handbookHypertext/hypermedia handbook, 1991)