The International Children's Digital Library - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

The International Children's Digital Library: Description and analysis of first use - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

Intradomain Overlays: Architecture and Applications - Kommareddy,Christopher; Guven,Tuna; Bhattacharjee, Bobby; La,Richard; Shayman,Mark (Technical Reports from UMIACS, UMIACS-TR-2003-70, 2003)
We introduce an architecture for ``Intradomain Overlays'', where a subset of routers within a domain is augmented with a dedicated host. These strategically placed hosts form an overlay network, and we describe a number of applications for such overlays. These applications include efficient network monitoring, policy- and load-based packet re-routing, and network resource accounting. In this paper, we elaborate on the network monitoring application and describe a distributed protocol for monitoring routers within an AS which has been augmented with a few overlay nodes. The routers and other infrastructure are unaware of the overlay nodes, and the monitoring of individual elements is conducted using plain SNMP. We describe techniques for efficiently synthesizing and transporting the monitored SNMP data, and present results using trace data collected from an AS with 400+ routers. Our results show that the overlay-based monitoring reduces overheads by 2--4 orders of magnitude, and thus enables much finer grained monitoring and traffic engineering than is otherwise possible. (UMIACS-TR-2003-70)
Keywords: Technical Report

IRIS: Internet-scale Resource-Intensive Sensor Services - Deshpande, Amol; Nath,S.; Gibbons,P.B.; Seshan,S. (Intel Research, UC Berkeley, Carnegie Mellon University, 2003)
The proliferation and affordability of smart sensors such aswebcams, microphones etc., has created opportunities for exciting new classes of distributed services. A key stum- bling block to mining these rich information sources is the lack of a common, scalable networked infrastructure for col- lecting, filtering, and combining the video feeds, extracting the useful information, and enabling distributed queries. In this demo, we demonstrate the design and an early prototype of such an infrastructure, called IRIS (Internet- scale Resource-Intensive Sensor services). IRIS is a poten- tially global network of smart sensor nodes, with webcams or other sensors, and organizing nodes that provide the means to query recent and historical sensor-based data. IRIS ex- ploits the fact that high-volume sensor feeds are typically attached to devices with significant computing power and storage, and running a standard operating system. Aggres- sive filtering, smart query routing, and semantic caching are used to dramatically reduce network bandwidth utilization and improve query response times, as we will demonstrate. The service that we demonstrate here is that of a park- ing space finder. This service utilizes webcams that monitor parking spaces to answer queries such as the availability of parking spaces near a user’s destination.

IrisNet: an architecture for internet-scale sensing services - Nath,Suman; Deshpande, Amol; Ke,Yan; Gibbons,Phillip B.; Karp,Brad; Seshan,Srinivasan (Proceedings of the 29th international conference on Very large data bases - Volume 29, 2003)
We demonstrate the design and an early prototype of IrisNet (Internet-scale Resource-Intensive Sensor Network services), a common, scalable networked infrastructure for deploying wide area sensing services. IrisNet is a potentially global network of smart sensing nodes, with webcams or other monitoring devices, and organizing nodes that provide the means to query recent and historical sensor-based data. IrisNet exploits the fact that high-volume sensor feeds are typically attached to devices with significant computing power and storage, and running a standard operating system. It uses aggressive filtering, smart query routing, and semantic caching to dramatically reduce network bandwidth utilization and improve query response times, as we demonstrate. Our demo will present two services built on Iris-Net, from two very different application domains. The first one, a parking space finder, utilizes webcams that monitor parking spaces to answer queries such as the availability of parking spaces near a user's destination. The second one, a distributed infrastructure monitor, uses measurement tools installed in individual nodes of a large distributed infrastructure to answer queries such as average network bandwidth usage of a set of nodes.

Latency Profiles: Performance Monitoring for Wide Area Applications - Raschid, Louiqa; Wen,Hui-Fang; Gal,Avigdor; Zadorozhny,Vladimir (Internet Applications, IEEE Workshop on, 2003)
Recent technological advances have enabled the deployment of wide area applications against Internet accessible sources. A performance challenge to applications in such a setting is the unpredictable end-to-end latency of accessing these sources. We use passive information gathering mechanisms to learn end-to-end latency distributions and construct Latency Profiles (LPs). We hypothesize that a group of clients, within an autonomous system (AS), that are accessing a content server, in another AS, may be represented by (one or more) LPs. Related networking research on IDMaps, points of congestion, and BGP routes support such hypothesis. We develop aggregate LPs to provide coverage of groups (clusters) of client-server pairs. Using data gathered from a (limited) experiment we demonstrate the feasibility of constructing LPs.

Learning Structure From Statistical Models - Getoor, Lise (IEEE Data Engineering Bulletin, 2003)
Statistical relational learning is a newly emerging area of machine learning that combines statisticalmodeling with relational representations. Here we argue that it provides a unified framework for the discovery of structural information that can be exploited by a data management system. The categories of structure that can be discovered include: instance-level dependencies and correlations, for example intra-table column dependencies and inter-table join dependencies; record linkages and duplicates; and schema matching and schema discovery from unstructured and semi-structured data.

Link mining: a new data mining challenge - Getoor, Lise (ACM SIGKDD Explorations Newsletter, 2003)
A key challenge for data mining is tackling the problem of mining richly structured datasets, where the objects are linked in some way. Links among the objects may demonstrate certain patterns, which can be helpful for many data mining tasks and are usually hard to capture with traditional statistical models. Recently there has been a surge of interest in this area, fueled largely by interest in web and hypertext mining, but also by interest in mining social networks, security and law enforcement data, bibliographic citations and epidemiological records.

Lower bounds on the efficiency of encryption and digital signature schemes - Gennaro,Rosario; Gertner,Yael; Katz, Jonathan (Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 2003)
A central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. Typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. In addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions.Among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. Here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can invert π on a fraction larger than 1/S of its inputs), our results show that:Any public-key encryption scheme for m-bit messages must query π at least Ω(m log S) times.Any private-key encryption scheme for m-bit messages (with k-bit keys) must query π at least Ω(m-k/log S) times.Any signature verification algorithm for m-bit messages must query π at least Ω(m log S) times.Our bounds match known upper bounds for the case of encryption.We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.
Keywords: black-box; digital signatures; encryption; lower bounds

Manufacturability Analysis of Multi-Material Objects Molded by Rotary Platen Multi-Shot Molding Process - Li,Xuejun; Gupta, Satyandra K. (ASME, 2003)
This paper describes a systematic approach for manufacturability analysis of multi-material objects molded using rotary platen multi-shot injection molding process. In this paper we first identify potential manufacturability problems that are associated with objects molded by the rotary platen process. Identified problems include infeasibility of molding sequences, unnecessary mold complexity, undesired friction during mold opening and closing, and undesired material flash on finished faces. These problems are unique to multi-material molding and do not occur in traditional injection molding. For each of the above four potential manufacturability problems, this paper also describes geometric algorithms for detecting the potential occurrence of the problem based on the object and mold design, finding its causes, and offering appropriate redesign suggestions. We expect that these algorithms will help in decreasing the product development time and improving the product quality for molded multi-material objects

Method of DNA extraction and application of multiplex polymerase chain reaction to detect toxigenic Vibrio cholerae O1 and O139 from aquatic ecosystems - Rivera,Irma N. G.; Lipp,Erin K.; Gil,Ana; Choopun,Nipa; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2003)
Vibrio cholerae is a free-living bacterium found in water and in association with plankton. V. cholerae non-O1/non-O139 strains are frequently isolated from aquatic ecosystems worldwide. Less frequently isolated are V. cholerae O1 and V. cholerae O139, the aetiological agents of cholera. These strains have two main virulence-associated factors, cholera toxin (CT) and toxin co-regulated pilus (TCP). By extracting total DNA from aquatic samples, the presence of pathogenic strains can be determined quickly and used to improve a microbiological risk assessment for cholera in coastal areas. Some methods suggested for DNA extraction from water samples are not applicable to all water types. We describe here a method for DNA extraction from coastal water and a multiplex polymerase chain reaction (PCR) for O1 and O139 serogroups. DNA extraction was successfully accomplished from 117 sea water samples collected from coastal areas of Perú, Brazil and the USA. DNA concentration in all samples varied from 20 ng to 480 µg µl−1. The sensitivity of the DNA extraction method was 100 V. cholerae cells in 250 ml of water. The specificity of multiplex O1/O139 PCR was investigated by analysing 120 strains of V. cholerae, Vibrio and other Bacteria species. All V. cholerae O1 and O139 tested were positive. For cholera surveillance of aquatic environments and ballast water, total DNA extraction, followed by V. cholerae PCR, and O1/O139 serogroup and tcpA/ctxA genes by multiplex PCR offers an efficient system, permitting risk analysis for cholera in coastal areas.

MobiCom poster: mining a world of smart sensors - Nath,Suman; Deshpande, Amol; Gibbons,Phillip B.; Seshan,Srinivasan (SIGMOBILE Mob. Comput. Commun. Rev., 2003)

Performance of a Three-Stage System for Multi-Document Summarization - Dunlavy,Daniel M.; Conroy,John M.; Schlesinger,Judith D.; Goodman,Sarah A.; Okurowski,Mary Ellen; O'Leary, Dianne P.; Halteren,Hans van (DUC 03 Conference ProceedingsDUC 03 Conference Proceedings, 2003)

Planning in Answer Set Programming Using Ordered Task Decomposition - Dix,Jürgen; Kuter,Ugur; Nau, Dana S. (KI 2003: Advances in Artificial Intelligence, 2003)
In this paper we introduce a formalism for solving Hierarchical Task Network ( HTN ) Planning using Answer Set Programming ( ASP ). We consider the formulation of HTN planning as described in the SHOP planning system and define a systematic translation method from SHOP ’s representation of the planning problem into logic programs with negation. We show that our translation is sound and complete : answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. We compare our method to (1) similar approaches based on non- HTN planning and (2) SHOP , a dedicated planning system. We show that our approach outperforms non- HTN methods and that its performance is better with ASP systems that allow for nonground programs than with ASP systems that require ground programs.
Keywords: Computer science

Predictability of Vibrio Cholerae in Chesapeake Bay - Louis,Valérie R.; Russek-Cohen,Estelle; Choopun,Nipa; Rivera,Irma N. G.; Gangle,Brian; Jiang,Sunny C.; Rubin,Andrea; Patz,Jonathan A.; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2003)
Vibrio cholerae is autochthonous to natural waters and can pose a health risk when it is consumed via untreated water or contaminated shellfish. The correlation between the occurrence of V. cholerae in Chesapeake Bay and environmental factors was investigated over a 3-year period. Water and plankton samples were collected monthly from five shore sampling sites in northern Chesapeake Bay (January 1998 to February 2000) and from research cruise stations on a north-south transect (summers of 1999 and 2000). Enrichment was used to detect culturable V. cholerae, and 21.1% (n = 427) of the samples were positive. As determined by serology tests, the isolates, did not belong to serogroup O1 or O139 associated with cholera epidemics. A direct fluorescent-antibody assay was used to detect V. cholerae O1, and 23.8% (n = 412) of the samples were positive. V. cholerae was more frequently detected during the warmer months and in northern Chesapeake Bay, where the salinity is lower. Statistical models successfully predicted the presence of V. cholerae as a function of water temperature and salinity. Temperatures above 19°C and salinities between 2 and 14 ppt yielded at least a fourfold increase in the number of detectable V. cholerae. The results suggest that salinity variation in Chesapeake Bay or other parameters associated with Susquehanna River inflow contribute to the variability in the occurrence of V. cholerae and that salinity is a useful indicator. Under scenarios of global climate change, increased climate variability, accompanied by higher stream flow rates and warmer temperatures, could favor conditions that increase the occurrence of V. cholerae in Chesapeake Bay.

PXML: a probabilistic semistructured data model and algebra - Hung,E.; Getoor, Lise; V.S. Subrahmanian (Data Engineering, 2003. Proceedings. 19th International Conference on, 2003)
Despite the recent proliferation of work on semistructured data models, there has been little work to date on supporting uncertainty in these models. We propose a model for probabilistic semistructured data (PSD). The advantage of our approach is that it supports a flexible representation that allows the specification of a wide class of distributions over semistructured instances. We provide two semantics for the model and show that the semantics are probabilistically coherent. Next, we develop an extension of the relational algebra to handle probabilistic semistructured data and describe efficient algorithms for answering queries that use this algebra. Finally, we present experimental results showing the efficiency of our algorithms.
Keywords: algebra; data; databases; instances; model; models; probabilistic; processing; PXML; query; relational; semistructured; structures; tree; XML

Random MAX SAT, random MAX CUT, and their phase transitions - Coppersmith,D.; Gamarnik,D.; Hajiaghayi, Mohammad T.; Sorkin,G. B (Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003)

Safe and flexible memory management in Cyclone - Hicks, Michael W.; Morrisett,G.; Grossman,D.; Jim,T. (Technical Reports from UMIACS, 2003)
Cyclone is a type-safe programming language intended for applications requiring control over memory management. Our previous work on Cyclone included support for stack allocation, lexical region allocation, and a garbage-collected heap. We achieved safety (i.e., prevented dangling pointers) through a region-based type-and-effects system. This paper describes some new memory-management mechanisms that we have integrated into Cyclone: dynamic regions, unique pointers, and reference-counted objects. Our experience shows that these new mechanisms are well suited for the timely recovery of objects in situations where it is awkward to use lexical regions. Crucially, programmers can write reusable functions without unnecessarily restricting callers' choices among the variety of memory-management options. To achieve this goal, Cyclone employs a combination of polymorphism and scoped constructs that temporarily let us treat objects as if they were allocated in a lexical region.

The sequence and analysis of Trypanosoma brucei chromosome II - El‐Sayed, Najib M.; Ghedin,E.; Song,J.; MacLeod,A.; Bringaud,F.; Larkin,C.; Wanless,D.; Peterson,J.; Hou,L.; Taylor,S.; others (Nucleic acids research, 2003)

Sports Video Classification Using HMM - Gilbert,X.; Li,H.; David Doermann (ICME, 2003)

A Step Towards Automated Design of Rotary-Platen Multi-Shot Molds - Li,Xuejun; Gupta, Satyandra K. (ASME, 2003)
This paper describes an improved algorithm for automated design of rotary-platen type of multi-shot molds for manufacturing multi-material objects. The algorithm described in this paper accounts for geometric constraints resulting from the rotary-platen process and it can handle significantly more complex interfaces. Our algorithm works in the following manner. First, we classify the multi-material object into several basic types based on the relationships among different single material components in the object. For every basic type, we find a manufacturing sequence based on the precedence constraints resulting due to accessibility and disassembly requirements. Then, starting from the last mold stage, we generate the mold pieces for every mold stage based on the manufacturing sequence. We expect that the algorithm described in this paper will provide the necessary foundations for automating the design of rotary-platen molds and therefore will help in significantly reducing the mold manufacturing lead-time associated with these types of molds.

Structure discovery using statistical relational learning - Getoor, Lise (Data Engineering, 2003)
Statistical relational learning is a newly emerging area of machine learning that combines statisticalmodeling with relational representations. Here we argue that it provides a unified framework for the discovery of structural information that can be exploited by a data management system. The categories of structure that can be discovered include: instance-level dependencies and correlations, for example intra-table column dependencies and inter-table join dependencies; record linkages and duplicates; and schema matching and schema discovery from unstructured and semi-structured data.

A Survey of Shape Similarity Assessment Algorithms for Product Design and Manufacturing Applications - Cardone, Antonio; Gupta, Satyandra K.; Karnik,Mukul (Journal of Computing and Information Science in EngineeringJ. Comput. Inf. Sci. Eng., 2003)
Keywords: CAD; computational geometry; production engineering computing; spatial reasoning

A system for generating process and material selection advice during embodiment design of mechanical components - Gupta,S.K.; Chen,Y.; Feng,S.; Sriram,R. (Journal of manufacturing systems, 2003)
This paper describes a systematic approach to material and process selection during theembodiment design of mechanical components and a system for generating process and material selection advice. Quite often during the embodiment design stage, design requirements are not precisely defined. Therefore, the system described in this paper accounts for imprecision in design requirements during generation and evaluation of alternative process sequences and material options. To reduce the computational effort, the system uses a depth-first branch-and- bound search algorithm. This aids in exploring promising process sequences and material options that can be used to meet the given set of design requirements. Various process sequences and material options are evaluated by using a commercial cost estimation tool.

Team formation in complex networks - Gaston,M.; desJardins, Marie (Proceedings of the 1st NAACSOS Conference, 2003)
The concept of team formation, or joint action, is central to a wide variety of disciplines includingorganizational design, computational organization theory, planning and learning in multi-agent systems, and distributed artificial intelligence. One key feature of team formation is the under- lying social network topology which determines the direct interactions among the individuals of the organization. Traditional models of social phenomena have been restricted to regular lattice, or fully-connected, network topologies, but recent results have shown that real-world networks have much different and much richer structure. Using a simple agent-based computational model of team formation, various virtual experiments are conducted to examine the impact of complex network structures on the dynamics of team formation.

Temporal probabilistic object bases - Biazzo,V.; Giugno,R.; Lukasiewicz,T.; V.S. Subrahmanian (Knowledge and Data Engineering, IEEE Transactions on, 2003)
There are numerous applications where we have to deal with temporal uncertainty associated with objects. The ability to automatically store and manipulate time, probabilities, and objects is important. We propose a data model and algebra for temporal probabilistic object bases (TPOBs), which allows us to specify the probability with which an event occurs at a given time point. In explicit TPOB-instances, the sets of time points along with their probability intervals are explicitly enumerated. In implicit TPOB-instances, sets of time points are expressed by constraints and their probability intervals by probability distribution functions. Thus, implicit object base instances are succinct representations of explicit ones; they allow for an efficient implementation of algebraic operations, while their explicit counterparts make defining algebraic operations easy. We extend the relational algebra to both explicit and implicit instances and prove that the operations on implicit instances correctly implement their counterpart on explicit instances.
Keywords: algebra; algebraic; bases; constraints; data; database; database; databases; distribution; explicit; functions; handling; implicit; instances; integrity; intervals; management; model; models; object; object-oriented; operations; probabilistic; probability; probability; relational; temporal; theory; Uncertainty; uncertainty

Two methods for solving a 3D acoustic inverse scattering problem - Seydou,Fadoulourahmane; Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2003)
We consider the problem of finding the refractive index of a buried object by using far‐field measurements in an inhomogeneous medium. We describe two methods for solving the inverse problem. Both methods are implemented in two steps in order to better deal with the ill‐posedness of the problem. In the first method an integral equation of the first kind is derived for the far‐field operator which is solved via least‐squares and Tikhonov regularization. We then use the solution of the integral equation to derive an over‐posed boundary value problem, i.e., the Helmholtz equation in a bounded domain with Cauchy data on the boundary. The index that satisfies this over‐posed problem most closely is obtained via the Levenberg–Marquardt algorithm. The second method is an iterative method and is based on the Lippmann–Schwinger equation. It is implemented via the Newton method. The first step consists, as for the other method. Here we use a Fourier integral approach and regularization via discretization. The second step is to obtain the index by iterating the Lippmann–Schwinger equation starting with the Born approximation.

When does a random Robin Hood win? - Gasarch,William; Golub,Evan; Srinivasan, Aravind (Theoretical Computer Science, 2003)
A certain two-person infinite game (between “Robin Hood” and the “Sheriff”) has been studied in the context of set theory. In certain cases, it is known that for any deterministic strategy of Robin Hood's, if the Sheriff knows Robin Hood's strategy, he can adapt a winning counter-strategy. We show that in these cases, Robin Hood wins with “probability one” if he adopts a natural random strategy. We then characterize when this random strategy has the almost-surely winning property. We also explore the case of a random Sheriff versus a deterministic Robin Hood.
Keywords: Games; Randomized strategy; STRATEGY

Which comes first, usability or utility? - Grinstein,Georges; Kobsa,Alfred; Plaisant, Catherine; Shneiderman, Ben; Stasko,John T (Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003)

AAAI 2002 Workshops - Blake,Brian; Haigh,Karen; Hexmoor,Henry; Falcone,Rino; Soh,Leen-Kiat; Baral,Chitta; McIlraith,Sheila; Gmytrasiewicz,Piotr; Parsons,Simon; Malaka,Rainer; Krueger,Antonio; Bouquet,Paolo; et al. (AI Magazine, 2002)

Algorithmic issues in modeling motion - Agarwal,Pankaj K.; Guibas,Leonidas J.; Edelsbrunner,Herbert; Erickson,Jeff; Isard,Michael; Har-Peled,Sariel; Hershberger,John; Jensen,Christian; Kavraki,Lydia; Koehl,Patrice; Lin,Ming; Manocha,Dinesh; et al. (ACM Comput. Surv., 2002)
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.
Keywords: computational geometry; Computer vision; mobile networks; modeling; molecular biology; motion modeling; physical simulation; robotoics; spatio-temporal databases

Approximating the head-related transfer function using simple geometric models of the head and torso - Algazi,V. R; Duda,R. O; Duraiswami, Ramani; Gumerov, Nail A.; Tang,Z. (The Journal of the Acoustical Society of America, 2002)

Argument structure saturation in a constraint based model - Drury,J.; Resnik, Philip; Weinberg, Amy; Gennari,S.; Aoshima,S. (2002)

Automated design of multi-stage molds for manufacturing multi-material objects - Kumar,M.; Gupta,S.K. (Journal of Mechanical Design, 2002)

Automatic transcription of Czech language oral history in the MALACH project: resources and initial experiments - Oard, Douglas; Demner-Fushman,D.; Hajic,J.; Ramabhadran,B.; Gustman,S.; Byrne,WJ; Soergel,D.; Dorr, Bonnie J; Resnik, Philip; Picheny,M. (Proceedings of the The 5th International Conference on Text, Speech and Dialogue, 2002)

Beam Search for Feature Selection in Automatic SVMDefect Classification - Gupta,P.; David Doermann; DeMenthon,D. (International Conference on Pattern Recognition, 2002)
Often in pattern classification problems, one tries to extract a large number of features and base the classifier decision on as much information as possible. This yields an array of features that are 'potentially' useful. Most of the time however, large feature sets are sub-optimal in describing the samples since they tend to over-represent the data and model noise along with the useful information in the data. Selecting relevant features from the available set of features is, therefore, a challenging task. In this paper, we present an innovative feature selection algorithm called Smart Beam Search (SBS), which is used with a Support Vector Machine based classifier for automatic defect classification. This feature selection approach not only reduces the dimensionality of the feature space substantially, but also improves the classifier performance.

Bounds on the efficiency of encryption and digital signatures - Gennaro,R.; Gertner,Y.; Katz, Jonathan (Rutgers University, 2002)
A central focus of modern cryptography is to investigate the weakest possible assumptionsunder which various cryptographic algorithms exist. Typically, a proof that a “weak” prim- itive (e.g., a one-way function) implies the existence of some “strong” algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. Beyond merely showing such a construction, an equally important research direction is to explore the efficiency of the construction. One might argue that this line of research has become even more important now that minimal assumptions are known for many (but not all) algorithms of interest. Protocols for encryption (in both the public- and private-key setting) and for digital signatures are fundamental to cryptography. In this work, we show the first lower bounds on the efficiency of constructions of these protocols based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can “break” π in the appropriate sense on a fraction larger than 1/S of its inputs), our results show that: • Any public-key encryption algorithm for m-bit messages must query π at least Ω(m/log S) times. This matches the known upper bound. • Any private-key encryption algorithm for m-bit messages which uses a k-bit key must query π at least Ω(m−k logS ) times. This matches the known upper bound. • Any signature verification algorithm for m-bit messages must query π at least Ω(m/log S) times. We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.

Complete genome sequence and comparative analysis of the metabolically versatile Pseudomonas putida KT2440 - Nelson,K. E; Weinel,C.; Paulsen,IT; Dodson,RJ; Hilbert,H.; Martins dos Santos,VAP; Fouts,DE; Gill,S. R; Pop, Mihai; Holmes,M.; others (Environmental microbiology, 2002)
Pseudomonas putida is a metabolically versatile saprophytic soil bacterium that has been certified as a biosafety host for the cloning of foreign genes. The bacterium also has considerable potential for biotechnological applications. Sequence analysis of the 6.18 Mb genome of strain KT2440 reveals diverse transport and metabolic systems. Although there is a high level of genome conservation with the pathogenic Pseudomonad Pseudomonas aeruginosa (85% of the predicted coding regions are shared), key virulence factors including exotoxin A and type III secretion systems are absent. Analysis of the genome gives insight into the non-pathogenic nature of P. putida and points to potential new applications in agriculture, biocatalysis, bioremediation and bioplastic production.

Computation of scattering from N spheres using multipole reexpansion - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2002)

A configurable CORBA gateway for providing adaptable system properties - Seri,M.; Courtney,T.; Michel Cukier; Gupta,V.; Krishnmamurthy,S.; Lyons,J.; Ramasamy,H.; Ren,J.; Sanders,W. H. (2002)

Constraints on the Generation of Tense, Aspect, and Connecting Words from Temporal Expressions - Dorr, Bonnie J; Gaasterland,T. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
Generating language that reflects the temporal organization of represented knowledgerequires a language generation model that integrates contemporary theories of tense and aspect, temporal representations, and methods to plan text. This paper presents a model that produces event combinations and appropriate connecting words to relate them. We distinguish between inherent and non-inherent aspectual features of verbs and describe an algorithm that uses these features to select tense, aspect, and temporal connecting words for generating text based on time-stamped information. The main result of this work is the successful incorporation of constrained linguistic theories of tense and as- pect in a self-contained module called CONGEN that produces a ranked list of temporal connectives and tense/aspect possibilities from pairs of time-stamped literals. We show that the theoretical results described herein have been verified in a large-scale corpus analysis. The framework serves as the basis of a component designed to enhance the English output of a constrained generation system.

Cyclone: A safe dialect of C - Jim,T.; Morrisett,G.; Grossman,D.; Hicks, Michael W.; Cheney,J.; Wang, Y. (USENIX Annual Technical Conference, 2002)
Cyclone is a safe dialect of C. It has been designed from the ground up to prevent the buffer overflows, format string attacks, and memory management errors that are common in C programs, while retaining C's syntax and semantics. This paper examines safety violations enabled by C's design, and shows how Cyclone avoids them, without giving up C's hallmark control over low-level details such as data representation and memory management.

Dependent rounding in bipartite graphs - Gandhi,R.; Khuller, Samir; Parthasarathy,S.; Srinivasan, Aravind (The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, 2002)
We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
Keywords: Application software; Approximation algorithms; bipartite graph; bipartite graphs; broadcast channels; broadcast scheduling; Broadcasting; capacitated vertex cover; Character generation; computational complexity; Computer science; Delay; edge-sets; Educational institutions; fair scheduling; fractional vectors; graph theory; per-user fairness properties; pipage rounding technique; Processor scheduling; Random variables; random-graph models; randomized rounding approach; rounding method; scheduling; Scheduling algorithm; telecommunication computing; unrelated parallel machines

Estimating the Optimal Number of Alternatives to Be Explored in Large Design Spaces: A Step Towards Incorporating Decision Making - Gupta,S.K. (2002)

Evaluating Arabic Retrieval from English or French Queries: The TREC-2001 Cross-Language Information Retrieval Track - Oard, Douglas; Gey,F.C.; Dorr, Bonnie J (Proceedings of the Post Workshop of LREC, 2002)
The Cross-language information retrieval track at the 2001 Text Retrieval Conference (TREC-2001) produced the first large informationretrieval test collection for Arabic. The collection contains 383,872 Arabic news stories, 25 topic descriptions in Arabic, English and French from which queries can be formed, and manual (ground truth) relevance judgments for a useful subset of the topic-document combinations. This paper describes the way in which the collection was created, explains the evaluation measures that the collection is designed to support, and provides an overview of the results from the first set of experiments with the collection. The results make it possible to draw some inferences regarding the utility of the collection for post hoc evaluations.

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

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

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

An extraction-based verification methodology for MEMS - Baidya,B.; Gupta,S.K.; Mukherjee,T. (Microelectromechanical Systems, Journal of, 2002)
Micromachining techniques are being increasingly used to develop miniaturized sensor and actuator systems. These system designs tend to be captured as layout, requiring extraction of the equivalent microelectromechanical circuit as a necessary step for design verification. This paper presents an extraction methodology to (re-)construct a circuit schematic representation from the layout, enabling the designer to use microelectromechanical circuit simulators to verify the functional behavior of the layout. This methodology uses a canonical representation of the given layout on which feature-based and graph-based recognition algorithms are applied to generate the equivalent extracted schematic. Extraction can be performed to either the atomic level or the functional level representation of the reconstructed circuit. The choice of level in hierarchy is governed by the trade off between simulation time and simulation accuracy of the extracted circuit. The combination of the MEMS layout extraction and lumped-parameter circuit simulation provides MEMS designers with VLSI-like tools enabling faster design cycles, and improved design productivity
Keywords: atomic level; canonical representation; circuit schematic representation; circuit simulation; design cycles; design productivity; design verification; digital simulation; equivalent circuits; equivalent microelectromechanical circuit; extraction-based verification methodology; feature-based recognition algorithms; functional behavior; functional level; graph-based recognition algorithms; layout extraction; lumped parameter networks; lumped-parameter circuit simulation; MEMS; microelectromechanical circuit simulators; micromachining techniques; micromechanical devices; simulation accuracy; simulation time

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

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

Identification of non-autonomous non-LTR retrotransposons in the genome of Trypanosoma cruzi - Bringaud,Frédéric; García-Pérez,José Luis; Heras,Sara R.; Ghedin,Elodie; El‐Sayed, Najib M.; Andersson,Björn; Baltz,Théo; Lopez,Manuel C. (Molecular and Biochemical Parasitology, 2002)
As observed for most eukaryotic cells, trypanosomatids contains non-LTR retrotransposons randomly inserted in the nuclear genome. Autonomous retroelements which, code for their own transposition, have been characterized in Trypanosoma brucei (ingi) and Trypanosoma cruzi (L1Tc), whereas non-autonomous retroelements have only been characterized in T. brucei (RIME). Here, we have characterized in the genome of Trypanosoma cruzi four complete copies of a non-autonomous non-LTR retrotransposon, called NARTc. This 0.26 kb NARTc element has the characteristics of non-LTR retrotransposons: the presence a poly(dA) tail and of a short flanking duplicated motif. Analysis of the Genome Survey Sequence databases indicated that the Trypanosoma cruzi haploid genome contains about 140 NARTc copies and about twice as many L1Tc copies. Interestingly, the NARTc and L1Tc retroelements share, with the Trypanosoma brucei ingi and RIME retrotransposons, a common sequence (the first 45 bp with 91% identity), whereas the remaining sequences are very divergent. This suggests that these four trypanosome non-LTR retrotransposons were derived from the same common ancester and the sequence of their 5'-extremity may have a functional role. In addition, the genome of Leishmania major contains the same conserved motif present in the trypanosome retroelements, whicle no transposable elements have been detected so far in Leishmania sp.
Keywords: Ingi; L1Tc; Non-LTR retrotransposon; RIME; Trypanosoma brucei; Trypanosoma cruzi

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

Irisnet: An architecture for compute-intensive wide-area sensor network services - Nath,S.; Deshpande, Amol; Ke,Y.; Gibbons,P.; Karp,B.; Seshan,S. (Intel Corporation, Pittsburgh IRPTR-02, 2002)
Previous work on sensor networks has targeted adhoc wireless networks of closely-colocated, resource- constrained scalar sensor motes. Such work has over- looked richer sensor types such as webcams and mi- crophones, which are typically attached to Internet- connected machines with significant computing power and storage. In this paper, we describe IrisNet (Internet- scale Resource-Intensive Sensor Network services), an architecture for wide-area sensor networks based on these more capable sensing nodes. IrisNet provides a common, scalable software infrastructure that enables the flexible creation of sensor-based Internet services. It dramatically reduces network bandwidth utilization through the use of senselets, binary code fragments that perform intensive data filtering at the sensing nodes, leveraging the available processing power and mem- ory. IrisNet employs a two-tier hierarchy of sensing nodes and query processing nodes. Key features of IrisNet include flexible data partitioning, efficient and protected sharing of sensor nodes, low-latency queries, partial match caching, query-specified freshness toler- ances, and monitoring and logging support. This pa- per reports on experiments with a working IrisNet pro- totype running a parking space finder service, demon- strating the effectiveness of IrisNet’s features in achiev- ing scalability and reducing query response times.

Learning structured statistical models from relational data - Getoor, Lise; Friedman,N.; Koller,D. (Linköping Electronic Articles in Computer and Information Science, 2002)
Here we describe tools for constructing statistical models from relational data. Our goal is to learn structured probabilistic models that represent statistical correlations both between the properties of an entity and between the properties of related entities. These statistical models can then be used for a variety of tasks including knowledge discovery, exploratory data analysis, data summarization and anomaly detection. Unfortunately, most statistical learning methods work only with "flat" data representations. Thus, to apply these methods, we are forced to convert the data into a flat form, thereby not only losing its compact representation and structure but also potentially introducing statistical skew. These drawbacks severely limit the ability of current statistical methods to model relational databases. Here we describe two complementary approaches: one approach suited to making probabilistic statements about individuals and the second approach suited to making statements about frequencies in relational data. We describe algorithms for both learning and making inferences in these models, and give experimental results.

A logic-based approach to data integration - Grant,John; Minker, Jack (Theory Pract. Log. Program., 2002)
An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.
Keywords: Clark completion; Data integration; materialized views; query folding; resolution method; stratified databases

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

Methods and apparatus for multi-layer data hiding - Yu,Hong Heather; M. Wu; Li,Xin; Gelman,Alexander D. (2002)
A data hiding system and method for providing a method of embedding multiple layers of hidden data into multimedia data. First, a media unit of the multimedia data is evaluated to determine an appropriate embedding procedure. Next during a first embedding pass, a ruling layer of primary hidden data is embedded into the media unit. In another embedding pass, a governing layer of secondary hidden data is embedded on top of the ruling layer. The secondary hidden data provides control information for controlling the primary hidden data and the host data. Control information such as error correction data, synchronization data, decoding data, and authentication data is embedded in the governing layer. Embedding schemes such as base domain and spectrum domain embedding are employed.

Multiple scattering from N spheres - Gumerov, Nail A.; Duraiswami, Ramani (Antennas and Propagation Society International Symposium, 2002. IEEE, 2002)

Numerical study of the influence of the torso on the HRTF - Gumerov, Nail A.; Duraiswami, Ramani; Tang,Z. (Acoustics, Speech, and Signal Processing, 1993. ICASSP-93., 1993 IEEE International Conference on, 2002)

Page classification through logical labelling - Liang,Jian; David Doermann; Ma,M.; Guo,J. K (Pattern Recognition, 2002. Proceedings. 16th International Conference on, 2002)
We propose an integrated approach to page classification and logical labelling. Layout is represented by a fully connected attributed relational graph that is matched to the graph of an unknown document, achieving classification and labelling simultaneously. By incorporating global constraints in an integrated fashion, ambiguity at the zone level can be reduced, providing robustness to noise and variation. Models are automatically trained from sample documents. Experimental results show promise for the classification and labelling of technical article title pages, and supports the idea of a hierarchical model base.
Keywords: article; attributed; base; character; classification; constraints; document; document; experimental; global; graph; graph; hierarchical; image; images; labelling; logical; model; noise; OCR; optical; page; pages; processing; recognition; relational; results; technical; theory; title; unknown

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

Reconstructing Images of Bar Codes for Construction Site Object Recognition - Gilsinn,David E.; Cheok,Geraldine S.; O'Leary, Dianne P. (Proceedings of the 19th International Symposium on Automation and Robotics in Construction, 2002)

Region-based memory management in cyclone - Grossman,Dan; Morrisett,Greg; Jim,Trevor; Hicks, Michael W.; Wang,Yanling; Cheney,James (SIGPLAN Not., 2002)
Cyclone is a type-safe programming language derived from C. The primary design goal of Cyclone is to let programmers control data representation and memory management without sacrificing type-safety. In this paper, we focus on the region-based memory management of Cyclone and its static typing discipline. The design incorporates several advancements, including support for region subtyping and a coherent integration with stack allocation and a garbage collector. To support separate compilation, Cyclone requires programmers to write some explicit region annotations, but a combination of default annotations, local type inference, and a novel treatment of region effects reduces this burden. As a result, we integrate C idioms in a region-based framework. In our experience, porting legacy C to Cyclone has required altering about 8% of the code; of the changes, only 6% (of the 8%) were region annotations.

Sheet metal bending: forming part families for generating shared press-brake setups - Gupta,S.K.; Rajagopal,D. (Journal of manufacturing systems, 2002)
Sheet metal bending press-brakes can be setup to produce more than one type of part withoutrequiring a setup change. To exploit this flexibility, we need setup planning techniques so that press-brake setups can be shared among many different parts. In this paper, we describe algorithms for partitioning a given set of parts into setup compatible part families that can be produced on the same setup. First, we present a greedy algorithm to form part family using a bottom-up approach that makes use of the mixed integer linear programming formulation for generating shared setups for each part family. Second, we present a mixed integer linear programming formulation to generate a shared setup for a given set of parts if such a setup exists. We expect that by producing many different types of parts on the same setup, we can significantly reduce the number of setup operations, improve machine tool utilization and enable cost-effective small-batch manufacturing.

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

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

A Step Towards Automated Design of Multi-Piece Sacrificial Molds - Dhaliwal,Savinder; Gupta, Satyandra K.; Huang,Jun; Kumar,Malay (ASME, 2002)
This paper describes a feature-based approach for design of multi-piece sacrificial molds. Our mold design algorithm consists of the following three steps. First, the desired gross mold shape is formed based on the feature-based description of the part geometry. Second, if the desired gross mold shape is not machinable as a single piece, the gross mold shape is decomposed into simpler geometric components to make sure that each component is manufacturable using 3-axis CNC machining. The decomposition is performed to ensure that each component is accessible to end-milling tools, and decomposed components can be assembled together to form the gross mold shape. Finally, assembly features are added to mold components to facilitate assembly of mold components and eliminate unnecessary degree of freedoms from the final mold assembly. We expect that our decomposition algorithm will provide a step towards the necessary foundations for automating the design of multi-piece mold and therefore will help in significantly reducing the mold design and manufacturing lead-time.

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

Theoretical and Empirical Aspects of a Planner in a Multi-agent Environment - Dix,Jürgen; Munoz-Avila,Hector; Nau, Dana S.; Zhang,Lingling (Logics in Artificial Intelligence, 2002)
We give the theoretical foundations and empirical evaluation of a planning agent, ashop, performing HTN planning in a multi-agent environment. ashop is based on ASHOP , an agentised version of the original SHOP HTN planning algorithm, and is integrated in the IMPACT multi-agent environment. We ran several experiments involving accessing various distributed, heterogeneous information sources, based on simplified versions of noncombatant evacuation operations, NEO’s. As a result, we noticed that in such realistic settings the time spent on communication (including network time) is orders of magnitude higher than the actual inference process. This has important consequences for optimisations of such planners. Our main results are: (1) using NEO’s as new, more realistic benchmarks for planners acting in an agent environment, and (2) a memoization mechanism implemented on top of shop, which improves the overall performance considerably.
Keywords: Computer science

Trypanosoma cruzi: RNA structure and post-transcriptional control of tubulin gene expression - Bartholomeu,Daniella C.; Silva,Rosiane A.; Galvão,Lucia M. C.; El‐Sayed, Najib M.; Donelson,John E.; Teixeira,Santuza M.R. (Experimental Parasitology, 2002)
Changes in tubulin expression are among the biochemical and morphological adaptations that occur during the life cycle of Trypanosomatids. To investigate the mechanism responsible for the differential accumulation of tubulin mRNAs in Trypanosoma cruzi, we determine the sequences of [alpha]- and [beta]-tubulin transcripts and analyzed their expression during the life cycle of the parasite. Two [beta]-tubulin mRNAs of 1.9 and 2.3 kb were found to differ mainly by an additional 369 nucleotides at the end of the 3' untranslated region (UTR). Although their transcription rates are similar in epimastigotes and amastigotes, [alpha]- and [beta]-tubulin transcripts are 3- to 6-fold more abundant in epimastigotes than in trypomastigotes and amastigotes. Accordingly, the half-lives of [alpha]- and [beta]-tubulin mRNAs are significantly higher in epimastigotes than in amastigotes. Transient transfection experiments indicated that positive regulatory elements occur in the 3' UTR plus downstream intergenic region of the [alpha]-tubulin gene and that both positive and negative elements occur in the equivalent regions of the [beta]-tubulin gene.Index Descriptions and Abbreviations: Kinetoplastida; Trypanosoma cruzi; tubulin; gene regulation; PCR, polymerase chain reaction; UTR, untranslated region; IR, intergenic region; SL, spliced leader; BAC, bacterial artificial chromosome.

Web-based innovation alert services to support product design evolution - Gupta,S.K.; Lin,E.; Lo,A. J.; Xu,C. (2002)
Technological innovations provide an opportunity toimprove product performance and reduce cost. Therefore, design organizations are interested in monitoring technological innovations. A large number of innovations are announced every year. Monitoring them manually is very time consuming. We are developing web-based innovation-alert services that can be used to monitor and communicate information about innovations relevant to a particular product design. In this paper, we discuss the required infrastructure, relevant design issues, and our approach to developing web-based innovation alert services to support product design evolution. We also describe a prototype innovation monitoring service for computer components and an interactive tool to transform semi-structured web contents into semantic representations in XML.

Zoomable user interfaces as a medium for slide show presentations - Good,L.; Bederson, Benjamin B. (Information Visualization, 2002)

Approximation algorithms for partial covering problems - Gandhi,R.; Khuller, Samir; Srinivasan, Aravind (Automata, Languages and Programming, 2001)
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-vertex cover) in polynomial time. In addition to its simplicity, this algorithm has the advantage of being parallelizable. For instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-vertex cover on planar graphs, and for covering points in R d by disks.

Automated design of sheet metal punches for bending multiple parts in a single setup - Alva,Ujval; Gupta, Satyandra K. (Robotics and Computer-Integrated Manufacturing, 2001)
Sheet metal bending is a process in which bends are formed using a combination of a punch and a die. A very large number of mechanical products such as furniture panels, shelves, cabinets, housing for electro-mechanical devices, etc. are created by using the sheet metal bending process. Bending tools need to satisfy the following two criteria: (1) tools should be able to withstand bending forces, and (2) tool shapes should be such that there is no tool-part interference. In this paper, we describe a methodology for automatically designing shapes of bending punches for bending multiple parts in a single setup. We create parametric geometric models of punches. These parametric models describe the family of possible punch shapes. Using the part geometry and parametric punch shape models, we automatically generated constraints on tool parameters that eliminate the possibility of part-tool interference. We use mixed-integer techniques to identify parameters of punch shapes that result in the maximum punch strength. Finally, we perform strength analysis of the designed punch shape using finite element analysis methods, to verify that the designed punch shape is capable of withstanding the bending forces.
Keywords: Praess planning; Punch design; Sheet metal bending

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

Cyclone User's Manual, Version 0.1. 3 - Grossman,D.; Morrisett,G.; Jim,T.; Hicks, Michael W.; Wang, Y.; Cheney,J. (Computer Science Technical Reports, 2001)
The current version of this manual should be available at http://www.cs.cornell.edu/projects/cyclone/ and http://www.research.att.com/projects/cyclone/. The version here describes Cyclone Version 0.1.3, although minor changes may have occurred before the release.

Dynamic resource allocation via video content and short-term traffic statistics - M. Wu; Joyce,R.A.; Wong,Hau-San; Guan,Long; Kung,Sun-Yuan (Multimedia, IEEE Transactions on, 2001)
The reliable and efficient transmission of high-quality variable bit rate (VBR) video through the Internet generally requires network resources be allocated in a dynamic fashion. This includes the determination of when to renegotiate for network resources, as well as how much to request at a given time. The accuracy of any resource request method depends critically on its prediction of future traffic patterns. Such a prediction can be performed using the content and traffic information of short video segments. This paper presents a systematic approach to select the best features for prediction, indicating that while content is important in predicting the bandwidth of a video hit stream, the use of both content and available short-term bandwidth statistics can yield significant improvements. A new framework for traffic prediction is proposed in this paper; experimental results show a smaller mean-square resource prediction error and higher overall link utilization
Keywords: allocation; link; allocation; multimedia; allocation; variable; bit; codes; content; bandwidth; error; short; Internet; dynamic; patterns; variable; prediction; rate; resource; segments; short-term; statistics; traffic; systems; resource; traffic; utilization; mean-square; video; video; video

Efficient evaluation of reverberant sound fields - Duraiswami, Ramani; Gumerov, Nail A.; Zotkin,Dmitry N; Davis, Larry S. (Applications of Signal Processing to Audio and Acoustics, 2001 IEEE Workshop on the, 2001)
An image method due to Allen and Berkley (1979) is often used to simulate the effect of reverberation in rooms. This method is relatively expensive computationally. We present a fast method for conducting such simulations using multipole expansions. For M real and image sources and N evaluation points, while the image method requires O(MN) operations, our method achieves the calculations in O(M + N) operations, resulting in a substantial speedup. Applications of our technique are also expected in simulation of virtual audio
Keywords: AB algorithm; acoustic signal processing; architectural acoustics; audio signal processing; Computational modeling; Computer interfaces; Computer simulation; Educational institutions; image method; image sources; Impedance; Laboratories; microphone arrays; multipole expansions; Nails; performance evaluation; reverberant sound fields; reverberation; room reverberation; simulation; Simulations; speedup; virtual audio

Efficient Model Checking Via Buchi Tableau Automata⋆ - Bhat,G. S; Cleaveland, Rance; Groce,A. (Computer aided verification: 13th International conference, CAV 2001, Paris, France, July 18-22, 2001: proceedings, 2001)

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

Efficient stepwise selection in decomposable models - Deshpande, Amol; Garofalakis,M. N; Jordan,M. I (Proc. UAI, 2001)

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

A feature-based approach to automated design of multi-piece sacrificial molds - Dhaliwal,S.; Gupta,S.K.; Huang,J.; Kumar,M. (Journal of Computing and Information Science in Engineering, 2001)

A geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects - Kumar,Malay; Gupta, Satyandra K. (ACM, 2001)
This paper describes a geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects. In multi-stage molding process, the desired multi-material object is produced by carrying out multiple molding operations in a sequence, adding one material in the target object in each mold-stage. We model multi-material objects as an assembly of single-material components. Each mold-stage can only add one type of material. Therefore, we need a sequence of mold-stages such that (1) each mold-stage only adds one single-material component either fully or partially, and (2) the molding sequence completely produces the desired object. In other to find a feasible mold-stage sequence, our algorithm decomposes the multi-material object into a number of homogeneous components to find a feasible sequence of homogeneous components that can be added in sequence to produce the desired multi-material object. Our algorithm starts with the final object assembly and considers removing components either completely or partially from the object one-at-a-time such that it results in the previous state of the object assembly. If the component can be removed from the target object leaving the previous state of the object assembly a connected solid then we consider such decomposition a valid step in the stage sequence. This step is recursively repeated on new states of the object assembly, until the object assembly reaches a state where it only consists of one component. When an object-decomposition has been found that leads to a feasible stage sequence, the gross mold for each stage is computed and decomposed into two or more pieces to facilitate the molding operation. We expect that our algorithm will provide a step towards automating the design of multi-stage molds and therefore will help in reducing the mold design lead-time for multi-stage molds.
Keywords: geometric reasoning; mold design; spatial partitioning

A geometric algorithm for selecting optimal set of cutters for multi-part milling - Yao,Zhiyang; Gupta, Satyandra K.; Nau, Dana S. (ACM, 2001)
For the manufacture of milled parts, it is well known that the size of the cutter significantly affects the machining time. However, for small-batch manufacturing, the time spent on loading tools into the tool magazine and establishing z-length compensation values is just as important. If we can select a set of milling tools that will produce good machining time on more than one type of parts, then several unnecessary machine-tool reconfiguration operations can be eliminated. This paper describes a geometric algorithm for finding an optimal set of cutters for machining a set of 2½D parts. In selecting milling cutters we consider both the tool loading time and the machining time and generate solutions that allow us to minimize the total machining time. Our problem formulation addresses the general problem of how to cover a target region to be milled with a cylindrical cutter without intersecting with the obstruction region; this definition allows us to handle both open and closed edges in the target region. Our algorithm improves upon previous work in the tool selection area in following ways: (1) in selecting cutters, it accounts for the tool loading time, and (2) it can simultaneously consider multiple different parts and select the optimal set of cutters to minimize the total manufacturing time.
Keywords: computer-aided process planning; milling cutter selection

Geometry of Eye Design: Biology and Technology - Fermüller, Cornelia; Aloimonos, J. (Multi-Image Analysis, 2001)
Natural or artificial vision systems process the images that they collect with their eyes or cameras in order to derive information for performing tasks related to navigation and recognition. Since the way images are acquired determines how dificult it is to perform a visual task, and since systems have to cope with limited resources, the eyes used by a specific system should be designed to optimize subsequent image processing as it relates to particular tasks. Different ways of sampling light, i.e., different eyes, may be less or more powerful with respect to particular competences. This seems intuitively evident in view of the variety of eye designs in the biological world. It is shown here that a spherical eye (an eye or system of eyes providing panoramic vision) is superior to a camera-type eye (an eye with restricted field of view) as regards the competence of three-dimensional motion estimation. This result is derived from a statistical analysis of all the possible computational models that can be used for estimating 3D motion from an image sequence. The findings explain biological design in a mathematical manner, by showing that systems that fly and thus need good estimates of 3D motion gain advantages from panoramic vision. Also, insights obtained from this study point to new ways of constructing powerful imaging devices that suit particular tasks in robotics, visualization and virtual reality better than conventional cameras, thus leading to a new camera technology.

Haptic and aural rendering of a virtual milling process - Chang,C. F; Varshney, Amitabh; Ge,Q. J (ASME 2001 Design Engineering Technical Conference and Computers and Information in Engineering Conference, Pittsburgh, PA, 2001)

Hierarchical image-based and polygon-based rendering for large-scale visualizations - Chang,C. F; Varshney, Amitabh; Ge,Q. J (Hierarchical and Geometrical Methods in Scientific VisualizationHierarchical and Geometrical Methods in Scientific Visualization, 2001)

Independence is good: dependency-based histogram synopses for high-dimensional data - Deshpande, Amol; Garofalakis,Minos; Rastogi,Rajeev (SIGMOD Rec., 2001)
Approximating the joint data distribution of a multi-dimensional data set through a compact and accurate histogram synopsis is a fundamental problem arising in numerous practical scenarios, including query optimization and approximate query answering. Existing solutions either rely on simplistic independence assumptions or try to directly approximate the full joint data distribution over the complete set of attributes. Unfortunately, both approaches are doomed to fail for high-dimensional data sets with complex correlation patterns between attributes. In this paper, we propose a novel approach to histogram-based synopses that employs the solid foundation of statistical interaction models to explicitly identify and exploit the statistical characteristics of the data. Abstractly, our key idea is to break the synopsis into (1) a statistical interaction model that accurately captures significant correlation and independence patterns in data, and (2) a collection of histograms on low-dimensional marginals that, based on the model, can provide accurate approximations of the overall joint data distribution. Extensive experimental results with several real-life data sets verify the effectiveness of our approach. An important aspect of our general, model-based methodology is that it can be used to enhance the performance of other synopsis techniques that are based on data-space partitioning (e.g., wavelets) by providing an effective tool to deal with the “dimensionality curse”.

Integrated Microelectromechanical System (MEMS) Inertial Measurement Unit (IMIMU) - Fedder,Gary K.; Blanton,Shawn; Carley,L. R.; Gupta, Satyandra K.; Koester,David (CARNEGIE-MELLON UNIVERSITY, 2001)
Processes, designs and design tools are developed to enable the monolithic integration of arrays of inertial microsensors with electronics. Accelerometers and gyroscopes, fabricated in a single CMOS process, are functional and demonstrate a single chip IMU. Two integrated post CMOS micro-machining processes are demonstrated. Thin-film microstructures are defined from the metal-dielectric stack of a conventional process. In the second process, a back-side silicon etch, followed by front-side DRIE produces bulk silicon microstructures. Accelerometer and gyroscope designs are developed with accompanying low noise electronic circuitry. Noise performance was limited to 1/f circuit noise. The chip output sensibility is set by the interface circuit design. A thermally stabilized accelerometer and circuit design is demonstrated using embedded polysilicon resistors as temperature sensors and heaters in a closed loop. Nested gyroscope topologies are demonstrated with a lateral MEMS accelerometer used as a coriolis acceleration sensor. Modeling and simulation tools that simultaneously consider the electromechanical transducer and the electronic circuit to predict system performance are developed. Electrical, electromechanical and mechanical parasitics required to enable predictive lumped parameter simulation are identified and can be extracted, enabling a designer to confidently estimate design performance prior to fabrication. Generic physics-based fault models for surface-micromachined actuators and sensors are developed that enable effective testing, diagnosis and design for manufacturability.
Keywords: *ELECTROMECHANICAL DEVICES; *GYROSCOPES; *INERTIAL MEASUREMENT UNITS; *INERTIAL NAVIGATION; *MICROELECTROMECHANICAL SYSTEMS; ACCELEROMETERS; BULK MATERIALS; CHIPS(ELECTRONICS); CIRCUITS; CLOSED LOOP SYSTEMS; CORIOLIS EFFECT; Detectors; DIELECTRICS; ELECTRICAL AND ELECTRONIC EQUIPMENT; EMBEDDING; METALS; MICROSENSORS.; MICROSTRUCTURE; MONOLITHIC STRUCTURES(ELECTRONICS); NAVIGATION AND GUIDANCE; PARASITES; PE63739E; PERFORMANCE(ENGINEERING); POLYSILICONS; RESISTORS; SILICON; TEMPERATURE SENSITIVE ELEMENTS; THERMAL STABILITY; THIN FILMS; tools; Topology; WUAFRLE1170030

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

Interpretation of Compound Nominals Using WordNet - Barrett,Leslie; Davis,Anthony; Dorr, Bonnie J (Computational Linguistics and Intelligent Text ProcessingComputational Linguistics and Intelligent Text Processing, 2001)
We describe an approach to interpreting noun-noun compounds within a question answering system. The system’s lexicon, based on WordNet, provides the basis for heuristics that group noun-noun compounds with seman- tically similar words. The semantic relationship between the nouns in a com- pound is determined by the choice of heuristic for the compound. We discuss procedures for selecting one heuristic in cases where several can apply to a compound, the effects of lexical ambiguity, and some initial results of our methods.

Learning probabilistic models of relational structure - Getoor, Lise; Friedman,N.; Koller,D.; Taskar,B. (MACHINE LEARNING-INTERNATIONAL WORKSHOP, 2001)
Most real-world data is stored in relational form. Incontrast, most statistical learning methods work with “flat” data representations, forcing us to convert our data into a form that loses much of the relational struc- ture. The recently introduced framework of proba- bilistic relational models (PRMs) allows us to repre- sent probabilistic models over multiple entities that utilize the relations between them. In this paper, we propose the use of probabilistic models not only for the attributes in a relational model, but for the rela- tional structure itself. We propose two mechanisms for modeling structural uncertainty: reference uncertainty and existence uncertainty. We describe the appropriate conditions for using each model and present learning algorithms for each. We present experimental results showing that the learned models can be used to pre- dict relational structure and, moreover, the observed relational structure can be used to provide better pre- dictions for the attributes in the model.

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

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

Modeling the effect of a nearby boundary on the HRTF - Gumerov, Nail A.; Duraiswami, Ramani (2001 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2001. Proceedings. (ICASSP '01), 2001)
Understanding and simplified modeling of the head related transfer function (HRTF) holds the key to many applications in spatial audio. We develop an analytical solution to the problem of scattering of sound from a sphere in the vicinity of an infinite plane. Using this solution we study the influence of a nearby scattering rigid surface, on a spherical model for the HRTF
Keywords: Acoustic scattering; acoustic signal processing; acoustic wave reflection; acoustic wave scattering; architectural acoustics; audio signal processing; Biological system modeling; boundary effect modeling; Computer interfaces; Ear; Educational institutions; Frequency; Head related transfer function; HRTF; HUMANS; infinite plane; Laboratories; Nails; Raman scattering; rigid surface; room environment; sound pressure level; sound scattering; spatial audio; sphere; spherical model; Transfer functions; wall influence

Multimodal localization of a flying bat - Ghose,K.; Zotkin,Dmitry N; Duraiswami, Ramani; Moss,C.F. (Acoustics, Speech, and Signal Processing, IEEE International Conference on, 2001)
We present a new multimodal system that combines stereoscopic and audio-based source localization to track the position of a flying bat. Also presented are novel algorithms for audio source localization. The bat was allowed to fly in an anechoic room and monitored by two high-speed video cameras. The vocalizations of the bat were simultaneously recorded from six microphones. The data was then processed offline to localize the source and reconstruct the trajectory of the bat. We compare the performance of the localization algorithm with the position data obtained from stereoscopic pictures of the bat. The results confirm that the stereoscopic analysis and the audio localization are in good agreement. This system opens up new possibilities for performing multimodal research, and developing more tightly integrated algorithms.

Multi-Relational Data Mining using Probabilistic Models Research Summary - Getoor, Lise (Proc. Of 1st workshop in MRDM, 2001)
We are often faced with the challenge of mining data represented inrelational form. Unfortunately, most statistical learning methods work only with “flat” data representations. Thus, to apply these methods, we are forced to con- vert the data into a flat form, thereby not only losing its compact representa- tion and structure but also potentially introducing statistical skew. These draw- backs severely limit the ability of current statistical methods to mine relational databases. Probabilistic models, in particular probabilistic relational models, al- low us to represent a statistical model over a relational domain. These models can represent correlations between attributes within a single table, and between attributes in multiple tables, when these tables are related via foreign key joins. In previous work [4, 6, 8], we have developed algorithms for automatically con- structing a probabilistic relational model directly from a relational database. We survey the results here and describe how the methods can be used to discover interesting dependencies the data. We show how this class of models and our construction algorithm are ideally suited to mining multi-relational data.

Multi-relational data mining using probabilistic relational models: research summary - Getoor, Lise (In Proceedings of the First Workshop in Multi-relational Data Mining, 2001)
We are often faced with the challenge of mining data represented in relational form. Unfortunately, most statistical learning methods work only with “flat ” data representations. Thus, to apply these methods, we are forced to convert the data into a flat form, thereby not only losing its compact representation and structure but also potentially introducing statistical skew. These drawbacks severely limit the ability of current statistical methods to mine relational databases. Probabilistic models, in particular probabilistic relational models, allow us to represent a statistical model over a relational domain. These models can represent correlations between attributes within a single table, and between attributes in multiple tables, when these tables are related via foreign key joins. In previous work [4, 6, 8], we have developed algorithms for automatically constructing a probabilistic relational model directly from a relational database. We survey the results here and describe how the methods can be used to discover interesting dependencies the data. We show how this class of models and our construction algorithm are ideally suited to mining multi-relational data.

Optimal Agent Selection - Ozcan,F.; V.S. Subrahmanian; Golubchik,L. (KI 2001: advances in artificial intelligence: Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001: proceedings, 2001)
The Internet contains a vast array of sources that provide identical or similar services. When an agent needs to solve a problem, it may split the problem into “subproblems” and find an agent to solve each of the subproblems. Later, it may combine the results of these subproblems to solve the original problem. In this case, the agent is faced with the task of determining to which agents to assign the subproblems.We call this the agent selection problem (ASP for short). Solving ASP is complex because it must take into account several different parameters. For instance, different agents might take different amounts of time to process a request. Different agents might provide varying “qualities” of answers. Network latencies associated with different agents might vary. In this paper, we first formalize the agent selection problem and show that it is NP-hard. We then propose a generic cost function that is general enough to take into account the costs of (i) network and server loads, (ii) source computations, and (iii) internal mediator costs. We then develop exact and heuristic based algorithms to solve the agent selection problem.

A point-placement strategy for conforming Delaunay tetrahedralization - Mount, Dave; Gable,C. W (International Journal of Computational Geometry & Applications, 2001)
A strategy is presented to find a set of points that yields a Conforming Delaunay tetrahedralization of a three-dimensional Piecewise-Linear complex (PLC). This algorithm is novel because it imposes no angle restrictions on the input PLC. In the process, an algorithm is described that computes a planar conforming Delaunay triangulation of a Planar Straight-Line Graph (PSLG) such that each triangle has a bounded circumradius, which may be of independent interest.

Probabilistic models of relational structure - Getoor, Lise; Friedman,N.; Taskar,B. (In Proc. ICML, 2001)
Most real-world data is stored in relational form. In contrast, most statistical learning methods work with “flat ” data representations, forcing us to convert our data into a form that loses much of the relational structure. The recently introduced framework of probabilistic relational models (PRMs) allows us to represent probabilistic models over multiple entities that utilize the relations between them. In this paper, we propose the use of probabilistic models not only for the attributes in a relational model, but for the relational structure itself. We propose two mechanisms for modeling structural uncertainty: reference uncertainty and existence uncertainty. We describe the appropriate conditions for using each model and present learning algorithms for each. We present experimental results showing that the learned models can be used to predict relational structure and, moreover, the observed relational structure can be used to provide better predictions for the attributes in the model.

Probabilistic models of text and link structure for hypertext classification - Getoor, Lise; Segal,E.; Taskar,B.; Koller,D. (IJCAI workshop on text learning: beyond supervision, 2001)
Most text classification methods treat each document as anindependent instance. However, in many text domains, doc- uments are linked and the topics of linked documents are cor- related. For example, web pages of related topics are often connected by hyperlinks and scientific papers from related fields are commonly linked by citations. We propose a unified probabilistic model for both the textual content and the link structure of a document collection. Our model is based on the recently introduced framework of Probabilistic Relational Models (PRMs), which allows us to capture cor- relations between linked documents. We show how to learn these models from data and use them efficiently for classifi- cation. Since exact methods for classification in these large models are intractable, we utilize belief propagation, an ap- proximate inference algorithm. Belief propagation automat- ically induces a very natural behavior, where our knowledge about one document helps us classify related ones, which in turn help us classify others. We present preliminary empiri- cal results on a dataset of university web pages.

Rescuing a destabilized protein fold through backbone cyclization - Camarero,Julio A; Fushman, David; Sato,Satoshi; Giriat,Izabela; Cowburn,David; Raleigh,Daniel P; Muir,Tom W (Journal of Molecular Biology, 2001)
We describe the physicochemical characterization of various circular and linear forms of the ∼60 residue N-terminal Src homology 3 (SH3) domain from the murine c-Crk adapter protein. Structural, dynamic, thermodynamic, kinetic and biochemical studies reveal that backbone circularization does not prevent the adoption of the natural folded structure in any of the circular proteins. Both the folding and unfolding rate of the protein increased slightly upon circularization. Circularization did not lead to a significant thermodynamic stabilization of the full-length protein, suggesting that destabilizing enthalpic effects (e.g. strain) negate the expected favorable entropic contribution to overall stability. In contrast, we find circularization results in a dramatic stabilization of a truncated version of the SH3 domain lacking a key glutamate residue. The ability to rescue the destabilized mutant indicates that circularization may be a useful tool in protein engineering programs geared towards generating minimized proteins.
Keywords: circular protein; ligation; SH3 domain

Robust matching of wavelet features for sub-pixel registration of Landsat data - Le Moigne,J.; Netanyahu,N. S; Masek,J. G; Mount, Dave; Goward, S.N. (Geoscience and Remote Sensing Symposium, 2001. IGARSS '01. IEEE 2001 International, 2001)
For many Earth and space science applications, automatic geo-registration at sub-pixel accuracy has become a necessity. In this work, we are focusing on building an operational system, which will provide a sub-pixel accuracy registration of Landsat-5 and Landsat-7 data. The input to our registration method consists of scenes that have been geometrically and radiometrically corrected. Such preprocessed scenes are then geo-registered relative to a database of Landsat chips. The method assumes a transformation composed of a rotation and a translation, and utilizes rotation- and translation-invariant wavelets to extract image features that are matched using statistically robust feature matching and a partial Hausdorff distance metric. The registration process is described and results on four Landsat input scenes of the Washington, D.C., area are presented
Keywords: Feature extraction; geo-registration; geophysical measurement technique; geophysical signal processing; geophysical techniques; Hausdorff distance metric; image registration; infrared; IR; land surface; Landsat; Landsat-5; Landsat-7; multispectral remote sensing; robust feature matching; robust matching; sub pixel registration; subpixel accuracy; terrain mapping; visible; wavelet feature; wavelet method; Wavelet transforms

Selectivity estimation using probabilistic models - Getoor, Lise; Taskar,Benjamin; Koller,Daphne (ACM SIGMOD Record, 2001)
Estimating the result size of complex queries that involve selection on multiple attributes and the join of several relations is a difficult but fundamental task in database query processing. It arises in cost-based query optimization, query profiling, and approximate query answering. In this paper, we show how probabilistic graphical models can be effectively used for this task as an accurate and compact approximation of the joint frequency distribution of multiple attributes across multiple relations. Probabilistic Relational Models (PRMs) are a recent development that extends graphical statistical models such as Bayesian Networks to relational domains. They represent the statistical dependencies between attributes within a table, and between attributes across foreign-key joins. We provide an efficient algorithm for constructing a PRM front a database, and show how a PRM can be used to compute selectivity estimates for a broad class of queries. One of the major contributions of this work is a unified framework for the estimation of queries involving both select and foreign-key join operations. Furthermore, our approach is not limited to answering a small set of predetermined queries; a single model can be used to effectively estimate the sizes of a wide collection of potential queries across multiple tables. We present results for our approach on several real-world databases. For both single-table multi-attribute queries and a general class of select-join queries, our approach produces more accurate estimates than standard approaches to selectivity estimation, using comparable space and time.

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

Web-based interactive design of freeform motions - Li,ST; Ge,Q. J; Varshney, Amitabh (Proceedings of the ASME 2001 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 2001)

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem - Guttmann-Beck,N.; Hassin,R.; Khuller, Samir; Raghavachari,B. (Algorithmica, 2000)
Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 , . . ., V k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.

Automated design of sheet metal bending tools - Alva,U.; Gupta,S.K.; Gupta,R. K. (2000)
Sheet metal bending is a process in which bends are formed using a combination of apunch and a die. Bending tools need to satisfy the following two criteria: (1) tools should be able to withstand bending forces, and (2) tool shapes should be such that there is no tool-part interference. In this paper, we describe a systematic methodology for automatically synthesizing a punch shape that can be used to produce more than one type of part. We create a parametric geometric model of possible punches. This parametric model describes a family of possible punch shapes. Using the geometric models of various given part types and a parametric punch model, we automatically generate constraints on punch parameters that eliminate the possibility of part-tool interference. We use mixed integer programming techniques to solve these constraints and identify parameters of a punch shape that can work for the given set of parts. Finally, we perform strength analysis of the designed punch to verify that the designed punch is capable of withstanding the bending forces.

Class representation and image retrieval with non-metric distances - Jacobs, David W.; Weinshall,D.; Gdalyahu,Y. (IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2000)
One of the key problems in appearance-based vision is understanding how to use a set oflabeled images to classify new images. Classification systems that can model human perfor- mance, or that use robust image matching methods, often make use of similarity judgments that are non-metric; but when the triangle inequality is not obeyed, most existing pattern recogni- tion techniques are not applicable. We note that exemplar-based (or nearest-neighbor) methods can be applied naturally when using a wide class of non-metric similarity functions. The key issue, however, is to find methods for choosing good representatives of a class that accurately characterize it. We show that existing condensing techniques for finding class representatives are ill-suited to deal with non-metric dataspaces. We then focus on developing techniques for solving this problem, emphasizing two points: First, we show that the distance between two images is not a good measure of how well one image can represent another in non-metric spaces. Instead, we use the vector correlation between the distances from each image to other previously seen images. Second, we show that in non-metric spaces, boundary points are less significant for capturing the structure of a class than they are in Euclidean spaces. We suggest that atypical points may be more important in describing classes. We demonstrate the importance of these ideas to learning that generalizes from experience by improving performance using both synthetic and real images.

Classification with nonmetric distances: image retrieval and class representation - Jacobs, David W.; Weinshall,D.; Gdalyahu,Y. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2000)
A key problem in appearance-based vision is understanding how to use a set of labeled images to classify new images. Systems that model human performance, or that use robust image matching methods, often use nonmetric similarity judgments; but when the triangle inequality is not obeyed, most pattern recognition techniques are not applicable. Exemplar-based (nearest-neighbor) methods can be applied to a wide class of nonmetric similarity functions. The key issue, however, is to find methods for choosing good representatives of a class that accurately characterize it. We show that existing condensing techniques are ill-suited to deal with nonmetric dataspaces. We develop techniques for solving this problem, emphasizing two points: First, we show that the distance between images is not a good measure of how well one image can represent another in nonmetric spaces. Instead, we use the vector correlation between the distances from each image to other previously seen images. Second, we show that in nonmetric spaces, boundary points are less significant for capturing the structure of a class than in Euclidean spaces. We suggest that atypical points may be more important in describing classes. We demonstrate the importance of these ideas to learning that generalizes from experience by improving performance. We also suggest ways of applying parametric techniques to supervised learning problems that involve a specific nonmetric distance functions, showing how to generalize the idea of linear discriminant functions in a way that may be more useful in nonmetric spaces
Keywords: appearance-based; by; classification; image; correlation; correlation; dataspaces; nonmetric; distances; nonmetric; example; functions; nonmetric; image; inequality; vector; judgments; robust; MATCHING; methods; image; methods; nonmetric; methods; triangle; points; boundary; points; class; representation; exemplar-based; representation; image; retrieval; learning; retrieval; nearest-neighbor; similarity; vision; atypical

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

Credit for computer crashes? - Gehl,J.; Shneiderman, Ben (Ubiquity, 2000)

Domain name based visualization of Web histories in a zoomable user interface - Gandhi,R.; Kumar,G.; Bederson, Benjamin B.; Shneiderman, Ben (11th International Workshop on Database and Expert Systems Applications, 2000. Proceedings, 2000)
Users of hypertext systems like the World Wide Web (WWW) often find themselves following hypertext links deeper and deeper, only to find themselves “lost” and unable to find their way back to the previously visited pages. We have implemented a Web browser companion called Domain Tree Browser (DTB) that builds a tree structured visual navigation history while browsing the Web. The Domain Tree Browser organizes the URLs visited based on the domain name of each URL and shows thumbnails of each page in a zoomable window
Keywords: Computer science; data visualisation; domain name; domain name based visualization; Domain Tree Browser; Educational institutions; History; hypermedia; hypertext links; hypertext systems; information resources; Navigation; online front-ends; thumbnails; Tree graphs; tree structured visual navigation history; Uniform resource locators; URLs; User interfaces; Visualization; Web browser companion; Web histories; Web pages; World Wide Web; zoomable user interface; zoomable window

Dynamics of vapor bubbles with nonequilibrium phase transitions in isotropic acoustic fields - Gumerov, Nail A. (Physics of Fluids, 2000)

Finding the maximal cutter for 2-D milling operations - Yao,Z.; Gupta,S.K.; Nau, Dana S. (2000)
In this paper, we describe a new geometricalgorithm to determine the biggest feasible cutter size for 2-D milling operations to be performed using a single cutter. In particular: • We give a general definition of the problem as the task of covering a target region without interfering with an obstruction region. This definition encompasses the task of milling a general 2-D profile that includes both open and closed edges. • We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of these definitions is most appropriate for the above problem. • We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we give an outline of a proof that our algorithm is correct.

From instances to classes in probabilistic relational models - Getoor, Lise; Koller,D.; Friedman,N. (Proc. ICML 2000 Workshop on Attribute-Value and Relational Learning, 2000)
Probabilistic graphical models, in particular Bayesian net-works, are useful models for representing statistical pat- terns in propositional domains. Recent work develops ef- fective techniques for learning these models directly from data. However these techniques apply only to attribute-value (i.e., flat) representations of the data. Probabilistic relational models (PRMs) allow us to represent much richer depen- dency structures, involving multiple entities and the rela- tions between them; they allow the properties of an entity to depend probabilistically on properties of related entities. PRMs represent a generic dependence, which is then instan- tiated for specific circumstances, i.e., for a particular set of entities and relations between them. Friedman et al. showed how to learn PRMs from relational data, and presented tech- niques for learning both parameters and probabilistic depen- dency structure for the attributes in a relational model. Here we examine the benefit that class hierarchies can provide PRMs. We show how the introduction of subclasses allows us to use inheritance and specialization to refine our models. We show how to learn PRMs with class hierarchies (PRM- CH) in two settings. In the first, the class hierarchy is pro- vided, as part of the input, in the relational schema for the domain. In the second setting, in addition to learning the PRM, we must learn the class hierarchy. Finally we dis- cuss how PRM-CHs allow us to build models that can repre- sent models for both particular instances in our domain, and classes of objects in our domain, bridging the gap between a class-based model and an attribute-value-based model.

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

A Geometric Algorithm for Finding the Largest Milling Cutter - Yao,Zhiyang; Gupta, Satyandra K.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 2000)
In this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for2-D milling operations to be performed using a single cutter. In particular: 1. We give a general definition of the problem as the task of covering a target region without interfering with anobstruction region. This definition encompasses the task of milling a general 2-D profile that includes bothopen and closed edges. 2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of thesedefinitions is most appropriate for the above problem. 3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show thatour algorithm is correct.
Keywords: algorithms; computational geometry; computer aided manufacturing CAM; cutter selection; Manufacturing; Next-Generation Product Realization Systems; path planning

A geometric algorithm for finding the maximal cutter for 2-D milling operations - Yao,Z.; Gupta,S.K.; Nau, Dana S. (2000)
In this paper, we present a geometric algorithm of finding the maximal cutter for 2-Dmilling operations. Our algorithm works not only for the common closed pocket problem, but also for the general 2-D milling problems with open edges. We define the general 2-D milling process in terms of a “target region” to be machined and an “obstruction region” that should not intersect with the cutter during machining. Our algorithm finds the largest cutter that can cover the target region without interfering with the obstruction region. Finding the biggest cutter is expected to help in the selection of the right sets of tools and the right type of cutter trajectories, and thereby ensure high production rate and meet the required quality level.

A Geometric Algorithm for Multi-Part Milling Cutter Selection - Yao,Zhiyang; Gupta, Satyandra K.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 2000)
Mass customization results in smaller batch sizes in manufacturing that require large numbers of setup and tool changes. The traditional process planning that generates plans for one part at a time is no longer applicable. In this paper, we propose the idea of process planning for small batch manufacturing, i.e., we simultaneously consider multiple parts and exploit opportunities for sharing manufacturing resources such that the process plan will be optimized over the entire set of parts. In particular, we discuss a geometric algorithm for multiple part cutter selection in 2-1/2D milling operations. We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we first discuss the lower and upper bond of cutter sizes that are feasible for given parts. Then we introduce the geometric algorithm to find the coverable area for a given cutter. Following that, we discuss the approach of considering cutter loading time and changing time in multiple cutter selection for multiple parts. We represent the cutter selection problem as shortest path problem and use Dijkstra's algorithm to solve it. By using this algorithm, a set of cutters is selected to achieve the optimum machining cost for multiple parts. Our research illustrates the multiple parts process planning approach that is suitable for small batch manufacturing. At the same time, the algorithm given in this paper clarifies the 2-1/2D milling problem and can also help in cutter path planning problem.
Keywords: algorithms; computer aided manufacturing CAM; cutter selection; Manufacturing; multi-part process planning; Next-Generation Product Realization Systems; OPTIMIZATION

Geo-registration of Landsat data by robust matching of wavelet features - Le Moigne,J.; Netanyahu,N. S; Masek,J. G; Mount, Dave; Goward,S.; Honzak,M. (Geoscience and Remote Sensing Symposium, 2000. Proceedings. IGARSS 2000. IEEE 2000 International, 2000)
The goal of our project is to build an operational system, which will provide a sub-pixel accuracy registration of Landsat-5 and Landsat-7 data. Integrated within an automated mass processing/analysis system for Landsat data (REALM), the input to our registration method consists of scenes that have been geometrically and radiometrically corrected, as well as pre-processed for the detection of clouds and cloud shadows. Such pre-processed scenes are then geo-registered relative to a database of Landsat chips. This paper describes our registration process, including the use of a database of landmark chips, a feature extraction performed by an overcomplete wavelet representation, and feature matching using statistically robust techniques. Knowing the approximate longitudes and latitudes of the four corners of the scene, a subset of chips which represent landmarks included in the scene are extracted from the database. For each of these selected landmark chips, a corresponding window is extracted from the scene, and each chip-window pair is registered using our robust wavelet feature matching. First results and future directions are presented in the paper
Keywords: atmospheric techniques; automated mass processing/analysis system; chip-window pair; cloud shadows; Clouds; Feature extraction; feature matching; geo-registration; geometrically corrected scene; geophysical signal processing; Image matching; image registration; landmark chips; Landsat chips; Landsat data; Landsat-5 data; Landsat-7 data; overcomplete wavelet representation; pre-processed scenes; radiometrically corrected scene; REALM; Remote sensing; robust matching; robust wavelet feature matching; scenes; statistically robust techniques; sub-pixel accuracy registration; wavelet features; Wavelet transforms; window

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

Jazz: an extensible zoomable user interface graphics toolkit in Java - Bederson, Benjamin B.; Meyer,J.; Good,L. (Proceedings of the 13th annual ACM symposium on User interface software and technology, 2000)

Learning probabilistic relational models - Getoor, Lise (Abstraction, Reformulation, and Approximation, 2000)
My work is on learning Probabilistic Relational Models (PRMs) from structured data (e.g., data in a relational database, an object-oriented database or a frame-based system). This work has as a starting point the framework of Probabilistic Relational Models, introduced in [5, 7]. We adapt and extend the machinery that has been developed over the years for learning Bayesian networks from data [1, 4, 6] to the task of learning PRMs from structured data. At the heart of this work is a search algorithm that explores the space of legal models using search operators that abstract or refine the model.

Learning response time for websources using query feedback and application in query optimization - Gruser,J. R; Raschid, Louiqa; Zadorozhny,V.; Zhan,T. (The VLDB Journal—The International Journal on Very Large Data Bases, 2000)

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

Logic-based query optimization for object databases - Grant,J.; Gryz,J.; Minker, Jack; Raschid, Louiqa (IEEE Transactions on Knowledge and Data Engineering, 2000)
We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method
Keywords: access scope; application domain; class hierarchy information; Constraint optimization; data integrity; Data models; Datalog; Datalog representation; deductive databases; equivalent logic query; integrity constraints; Lifting equipment; Logic; logic based query optimization; logic programming; logic queries; logic query; logical representation; object data model; object databases; object queries; object schema; object-oriented databases; ODL; ODMG database schemas; optimization technique; optimized OQL queries; OQL object query; query languages; Query optimization; query optimization techniques; Query processing; Relational databases; residue technique; semantic knowledge; semantic query optimization

A Neural Network Approach for Predicting Network Resource Requirements in Video Transmission Systems - Wong,H.S.; Wu,M.; Joyce,R.A.; Guan,L.; Kung, S.Y. (Proc. IEEE Pacific RIM Conference on Multimedia, Sydney, Australia, 2000)
Dynamic resource allocation is important for ensuring ef-ficient network utilization in Internet-based multimedia content delivery system. To allow accurate network traf- fic prediction in the case of video delivery, relevant infor- mation based on video contents and the short term traffic pattern has to be taken into account, while the inclusion of non-relevant features will deterioriate the prediction per- formance due to the "curse of dimensionality" problem. In this work, we propose a neural network-based predic- tion system and specifically address the determination of relevant input features for the system. Experiments have shown that the current system is capable of identifying a highly relevant subset of features for traffic prediction given a large number of video content and short-term net- work traffic descriptors.

Numerical simulation of small-signal microwave performance of 4H–SiC MESFET - Huang,Mingwei; Mayergoyz, Issak D; Goldsman,Neil (Solid-State Electronics, 2000)
Small-signal high frequency characteristics of 4H–SiC MESFET has been studied by using two-dimensional numerical drift-diffusion model in frequency domain. Non-ideal Schottky boundary conditions have been introduced that take into account a thin interfacial layer and interface energy states. It has been demonstrated that the 10 dB/dec small-signal current gain roll-off can be attributed to the existence of high density interface states at the metal–semiconductor interface. It has been found that as the gate length is reduced to 0.1 μm, fT and fmax may reach as high as 30 and 62 GHz, respectively.

Off-line Skilled Forgery Detection using Stroke and Substroke Features - Guo,K.; David Doermann; Rosenfeld, A. (ICPR, 2000)

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

A point-placement strategy for conforming Delaunay tetrahedralization - Murphy,Michael; Mount, Dave; Gable,Carl W. (Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 2000)

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

Rectified Heat Transfer to Vapor Bubbles in Standing Acoustic Waves - Gumerov, Nail A. (Microgravity fluid physics and heat transfer: proceedings of the International Conference on Microgravity Fluid Physics and Heat Transfer held at the Tutle Bay Hilton, Oahu, Hawaii, September 19-24, 1999, 2000)

Resolution enhancement by applying MFM under UHV conditions - Dreyer,M.; Gomez,R.D.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 2000)
The enhancement in signal-to-noise ratio and lateral resolution in MFM in going from ambient pressure to UHV is demonstrated. The performance of several cantilevers is evaluated using a patterned 50 nm thick permalloy film, with cross-tie as well as 90 deg; domain walls, and a 200 nm thick permalloy film with perpendicular magnetization. The increase in the quality factor of the cantilever oscillation in UHV improves the sensitivity, consequently allowing less magnetic material on the tip to achieve the same signal-to-noise ratio. This reduction in magnetic volume sharpens the lateral resolution. We also demonstrate that the magnetic interaction can be so weak that a magnetic contrast is visible only under UHV conditions
Keywords: conditions; cantilevers; domain; contrast; magnetic; domain; enhancement; Permalloy; magnetic; enhancement; signal-to-noise; film; perpendicular; films; magnetisation; force; magnetization; resolution; MFM; NiFe; UHV; microscopy; magnetic; ratio; resolution; magnetic; thin; volume; permalloy; walls; lateral; walls; magnetic

A Review of Current Routing Protocols for Ad Hoc - Royer,E.M.; Toh,C.K.; Hicks, Michael W.; Kakkar,P.; Moore,J. T; Hicks, Michael W.; Moore,J. T; Alexander,D. S; Gunter,C. A; Nettles,S.; others (IEEE Personal Communications, 2000)

Selecting Flat End Mills for 2-1/2D Milling Operations - Yao,Zhiyang; Gupta, Satyandra K.; Nau, Dana S. (Institute for Systems Research, University of Maryland, College Park, 2000)
The size of milling cutter significantly affects the machining time. Therefore, in order to perform milling operations efficiently, we need to select a set of milling cutters with optimal sizes. It is difficult for human process planners to select the optimal or near optimal set of milling cutters due to complex geometric interactions among tools size, part shapes, and tool trajectories. In this paper, we give a geometric algorithm to find the optimal cutters for 2-1/2D milling operations. We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we introduced the offsetting and inverse-offsetting algorithm to find the coverable area for a given cutter. Following that, we represent the cutter selection problem as shortest path problem and discuss the lower and upper bond of cutter sizes that are feasible for given parts. The Dijkstra's algorithm is used to solve the problem and thus a set of cutters is selected in order to achieve the optimum machining cost. We believe the selection of optimum cutter combination can not only save manufacturing time but also help automatic process planning.
Keywords: algorithms; computer aided manufacturing CAM; cutter selection; Manufacturing; Next-Generation Product Realization Systems

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

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

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

Advances in spherical harmonic device modeling: calibration and nanoscale electron dynamics - Lin,Chung-Kai; Goldsman,N.; Mayergoyz, Issak D; Aronowitz,S.; Belova,N. (Simulation of Semiconductor Processes and Devices, 1999. SISPAD '99. 1999 International Conference on, 1999)
Improvements in the Spherical Harmonic (SH) method for solving Boltzmann Transport Equation (BTE) are presented. The simulation results provide the same physical detail as analytical band Monte Carlo (MC) calculations, and are obtained approximately a thousand times faster. A new physical model for surface scattering has also been developed. As a result, the SHBTE model achieves calibration for a complete process of I-V characteristics and substrate current consistently for the first time
Keywords: Boltzmann; characteristics; SHBTE; current; surface; device; dynamics; spherical; electron; equation; calibration; semiconductor; equation; I-V; harmonic; model; substrate; models; surface; scattering; scattering; Boltzmann; simulation; calibration; nanoscale; transport

An architecture and implementation for a cooperative database system - Godfrey,P.; Minker, Jack (University of Maryland at College Park, 1999)

ARobust Method for Unknown Forms Analysis - Xingyuan,L.; David Doermann; Oh,W.; Gao,W. (ICDAR, 1999)

Automated punch shape synthesis for sheet metal bending operations - Alva,U.; Gupta,S.K. (1999)

Classification in non-metric spaces - Weinshall,Daphna; Jacobs, David W.; Gdalyahu,Yoram (Proceedings of the 1998 conference on Advances in neural information processing systems II, 1999)

Efficient learning using constrained sufficient statistics - Friedman,N.; Getoor, Lise (Proceedings of the 7th International Workshop on Artificial Intelligence and Statistics (AISTATS-99), 1999)
Learning Bayesian networks is a central prob-lem for pattern recognition, density estima- tion and classification. In this paper, we propose a new method for speeding up the computational process of learning Bayesian network structure. This approach uses con- straints imposed by the statistics already col- lected from the data to guide the learning al- gorithm. This allows us to reduce the num- ber of statistics collected during learning and thus speed up the learning time. We show that our method is capable of learning struc- ture from data more efficiently than tradi- tional approaches. Our technique is of partic- ular importance when the size of the datasets is large or when learning from incomplete data. The basic technique that we introduce is general and can be used to improve learn- ing performance in many settings where suf- ficient statistics must be computed. In ad- dition, our technique may be useful for al- ternate search strategies such as branch and bound algorithms.

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

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

Gate leakage current simulation by Boltzmann transport equation and its dependence on the gate oxide thickness - Han,Zhiyi; Lin,Chung-Kai; Goldsman,N.; Mayergoyz, Issak D; Yu,S.; Stettler,M. (Simulation of Semiconductor Processes and Devices, 1999. SISPAD '99. 1999 International Conference on, 1999)
As device dimensions shrink toward 0.1 mu;m, gate oxides are becoming so thin that MOSFET gate leakage current and oxide degradation are becoming limiting issues. We provide a more rigorous way to calculate gate leakage current. To achieve this we build upon the Spherical Harmonic Method of modeling, which deterministically solves the Boltzmann equation for an entire device. The method gives the distribution function and is 1000 times faster than MC. Once the distribution function is calculated, the tunneling probability is derived from the first principle WKB method. The barrier lowering effect is accounted for by the method of image charges. We calculate gate leakage current as a function of DC bias. The thermionic and tunneling components are compared at different DC bias points. The dependence of gate leakage current on gate oxide thickness is simulated
Keywords: 30; angstrom; 60; angstrom; Boltzmann; Bias; calculations; leakage; charges; spherical; component; tunneling; current; currents; semiconductor; dependence; method; dependence; MOSFET; barrier; device; effect; distribution; equation; DC; equation; MOSFET; WKB; function; first; harmonic; image; leakage; lowering; method; method; gate; model; thermionic; models; tunnelling; of; oxide; principle; probability; Boltzmann; simulation; gate; thickness; transport; WKB

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

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.

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.

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

More surprises from Kinetoplastida - Donelson,J. E; Gardner,M. J; El‐Sayed, Najib M. (Proceedings of the National Academy of Sciences of the United States of America, 1999)

Multi-level data hiding for digital image and video - Wu,M.; Yu,H.; Gelman,A. (SPIE Photonics East’99, 1999)
Previous works on data hiding generally targeted on a specific tradeoff between capacity and robustness. This results inoverestimation of the processing noise under some situations and/or underestimation under some other situations, hence limits the overall performance. In this paper, we propose a multi-level data hiding scheme which is able to convey secondary data in high rate when noise is not severe and can also convey some data reliably under heavy distortion. The proposed scheme is motivated by a two-category classification of embedding schemes and by a study on detection performance of spread spectrum watermarking. The multi-level data hiding has been successfully applied to both digital image and video, and can be used for applications such as copy control.

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.

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

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)

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.

PLANet: an active internetwork - Hicks, Michael W.; Moore,J. T; Alexander,D. S; Gunter,C. A; Nettles,S. M (IEEE INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 1999)
We present PLANet: an active network architecture and implementation. In addition to a standard suite of Internet-like services, PLANet has two key programmability features: (1) all packets contain programs; and (2) router functionality may be extended dynamically. Packet programs are written in our special purpose programming language PLAN, the Packet Language for Active Networks, while dynamic router extensions are written in OCaml, a dialect of ML. Currently, PLANet routers run as byte-code-interpreted Linux user-space applications, and support Ethernet and IP as link layers. PLANet achieves respectable performance on standard networking operations: on 300 MHz Pentium-II's attached to 100 Mbps Ethernet, PLANet can route 48 Mbps and switch over 5000 packets per second. We demonstrate the utility of PLANet's activeness by showing experimentally how it can nontrivially improve application and aggregate network performance in congested conditions
Keywords: 100 Mbit/s; 300 MHz; 48 Mbit/s; active internetwork; active network architecture; active network implementation; byte-code-interpreted applications; Computer architecture; Computer languages; Computer networks; congested conditions; dynamic programming; dynamic router extensions; Ethernet; Ethernet networks; INFORMATION SCIENCE; Internet; Internet-like services; internetworking; IP; IP networks; link layers; Linux user-space applications; Local area networks; ML dialect; Network performance; networking operations; OCaml; Packet Language for Active Networks; packet programs; packet switching; Pentium-II; performance; performance evaluation; PLAN; PLANet; Planets; programmability features; programming languages; router functionality; special purpose programming language; Switches; telecommunication network routing; Transport protocols; Web and internet services

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

Sheet metal bending: generating shared setups - Gupta,S.K.; Bourne,D. A. (TRANSACTIONS-AMERICAN SOCIETY OF MECHANICAL ENGINEERS JOURNAL OF MANUFACTURING SCIENCE AND ENGINEERING, 1999)
Contemporary process planners for sheet metal bending solve the process planning problemfor individual parts. Quite often, many different parts can be produced on shared setups. However, plans generated by current process planning systems fail to exploit this commonality between setups and try to generate optimal setups for individual parts. In this paper, we present an algorithm for multi-part setup planning for sheet metal bending. This algorithm takes a set of parts and operation sequences for these parts, and tries to find a shared setup plan that can work for every part in the set. Setup changes constitute a major portion of the production time in batch production environments. Therefore, multi-part setup planning techniques can be used to significantly cut down the total number of setups and increase the overall through-put.

Sheet metal bending operation planning: using virtual node generation to improve search efficiency - Gupta,S.K. (Journal of manufacturing systems, 1999)
A large number of manufacturing operation planning problems can be formulatedas state-space search problems. In case of sheet-metal bending operation planning, processing a search node involves extensive geometric reasoning. Such computation- intensive node-processing limits the number of search nodes that can be expanded in a reasonable amount of time, making it difficult to solve real-life operation planning problems. In this paper, we describe a scheme to speed up operation planning by virtual gen- eration of state-space nodes. In this scheme, we eliminate unnecessary computation at the time of node generation by extracting the required information from already generated nodes. Although generation of two different search nodes rarely involves identical computation steps, there is considerable overlap in node generation steps. We have divided the node generation step into a number of computation subproblems. When we need to generate a new node, we first try to see if any of the node gener- ation subproblems have been solved for any of the already generated nodes. If any subproblem has already been solved for some other node, then we use the solution of that subproblem to save computation time. In such cases, we do not perform node generation computation steps, and therefore we call such node generation virtual. The scheme presented in this paper increases the node generation capability and allows us to consider many more search nodes. The ability to consider more search nodes helps us in solving more complex problems and finding better operation plans.

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.

Tikhonov Regularization and Total Least Squares - Golub, Gene H.; Hansen,Per Christian; O'Leary, Dianne P. (SIAM Journal on Matrix Analysis and Applications, 1999)
Discretizations of inverse problems lead to systems of linear equations with a highly ill-conditioned coefficient matrix, and in order to computestable solutions to these systems it is necessary to apply regularization methods. We show how Tikhonov's regularization method, which in its original formulation involves a least squares problem, can be recast in a total least squares formulation suited for problems in which both the coefficient matrix and the right-hand side are known only approximately. We analyze the regularizing properties of this method and demonstrate by a numerical example that, in certain cases with large perturbations, the new method is superior to standard regularization methods.
Keywords: bidiagonalization; discrete ill-posed problems; regularization; total least squares

Trust me, I'm accountable: trust and accountability online - Friedman,Batya; Thomas,John C.; Grudin,Jonathan; Nass,Clifford; Nissenbaum,Helen; Schlager,Mark; Shneiderman, Ben (CHI '99 extended abstracts on Human factors in computing systems, 1999)
We live in an increasingly wired world. According to Robert Putnam, people are spending less time in persistent personal face to face interactions and more time in pursuits such as watching TV and using the Internet. At the same time, independently measured "social capital" -- the extent to which we trust and work for a common good -- is declining. In this panel, we explore: the impacts of electronic media on trust and accountability; whether and how electronic media can be designed and used to increase deserved trust and accountability; the relationship between protecting privacy and increasing the efficacy of communication; and how people's tendency to treat computers as social actors impacts these issues. In brief, how can modern technology enhance humanity's humanity?
Keywords: accountability; anonymity; Communication; computers and society; ethics; Internet; media effects; privacy; Reciprocity; repute; social actors; social capital; social impacts; trust; value-sensitive design; wired world; WWW

Using probabilistic relational models for collaborative filtering - Getoor, Lise; Sahami,M. (Proc. Workshop Web Usage Analysis and User Profiling (WEBKDD’99), 1999)
Recent projects in collaborative filtering and information filtering address the task of inferring user prefer-ence relationships for products or information. The data on which these inferences are based typically con- sists of pairs of people and items. The items may be information sources (such as web pages or newspaper articles) or products (such as books, software, movies or CDs). We are interested in making recommen- dations or predictions. Traditional approaches to the problem derive from classical algorithms in statistical pattern recognition and machine learning. The majority of these approaches assume a ”flat” data repre- sentation for each object, and focus on a single dyadic relationship between the objects. In this paper, we examine a richer model that allows us to reason about many different relations at the same time. We build on the recent work on probabilistic relational models (PRMs), and describe how PRMs can be applied to the task of collaborative filtering. PRMs allow us to represent uncertainty about the existence of relationships in the model and allow the properties of an object to depend probabilistically both on other properties of that object and on properties of related objects.

Zoom-Only Vs Overview-Detail Pair: A Study in Browsing Techniques as Applied to Patient Histories - Ghosh,P.; Shneiderman, Ben (University of Maryland Technical Report, CS-TR, 1999)

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

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

Benchmarking a network of PCs running parallel applications - Hollingsworth, Jeffrey K; Guven, E.; Akinlar, C. (Performance, Computing and Communications, 1998. IPCCC '98., IEEE International, 1998)
Presents a benchmarking study that compares the performance of a network of four PCs connected by a 100 Mbit/s fast Ethernet running three different system software configurations: TCP/IP on Windows NT, TCP/IP on Linux and a lightweight message-passing protocol (U-Net active messages) on Linux. For each configuration, we report results for communication micro-benchmarks and the NAS (Numerical Aerodynamics Simulation) parallel benchmarks. For the NAS benchmarks, the overall running time using Linux TCP/IP was 12-500% less than the Windows NT TCP/IP configuration. Likewise, the Linux U-Net based message-passing protocol outperformed the Linux TCP/IP version by 5-200%+. We also show that, by using Linux U-Net, we are able to achieve 125 μs latency between two processes using PVM. Finally, we report that the default mathematical libraries supplied with NT (for both gcc and Visual C++) are substantially slower than the one supplied with Linux
Keywords: 100 Mbit/s; 125 mus; Aerodynamics; Application software; communication micro-benchmarks; default mathematical libraries; Delay; Ethernet; Ethernet networks; gcc; latency; lightweight message-passing protocol; Linux; Local area networks; mathematics computing; Message passing; microcomputer applications; Microsoft Windows NT; NAS parallel benchmarks; network operating systems; Numerical simulation; parallel applications; PARALLEL PROCESSING; PC network benchmarking; performance comparison; performance evaluation; Personal communication networks; Protocols; PVM; running time; software libraries; System software; system software configurations; TCP/IP; TCPIP; Transport protocols; U-Net active messages; Visual C++

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.

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

Condensing image databases when retrieval is based on non-metric distances - Jacobs, David W.; Weinshall,D.; Gdalyahu,Y. (Computer Vision, 1998. Sixth International Conference on, 1998)
One of the key problems in appearance-based vision is understanding how to use a set of labeled images to classify new images. Classification systems that can model human performance, or that use robust image matching methods, often make use of similarity judgments that are non-metric but when the triangle inequality is not obeyed, most existing pattern recognition techniques are not applicable. We note that exemplar-based (or nearest-neighbor) methods can be applied naturally when using a wide class of non-metric similarity functions. The key issue, however, is to find methods for choosing good representatives of a class that accurately characterize it. We note that existing condensing techniques for finding class representatives are ill-suited to deal with non-metric dataspaces. We then focus on developing techniques for solving this problem, emphasizing two points: First, we show that the distance between two images is not a good measure of how well one image can represent another in non-metric spaces. Instead, we use the vector correlation between the distances from each image to other previously seen images. Second, we show that in non-metric spaces, boundary points are less significant for capturing the structure of a class than they are in Euclidean spaces. We suggest that atypical points may be more important in describing classes. We demonstrate the importance of these ideas to learning that generalizes from experience by improving performance using both synthetic and real images
Keywords: appearance-based; databases; databases; image; dataspaces; pattern; MATCHING; methods; non-metric; processing; visual; recognition; query; systems; image; vision; classification

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

Direction of Arrival and the Rank-Revealing URV Decomposition - Boman,E. C; Griffen,M. F; Stewart, G.W. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
In many practical direction-of-arrival (DOA) problems the numberof sources and their directions from an antenna array do not remain stationary. Hence a practical DOA algorithm must be able to track changes with a minimal number of snapshots. In this paper we describe DOA algorithms, based on a new decomposition, that are not expensive to compute or difficult to update. The algorithms are compared with algorithms based on the singular value decomposition (SVD). (Also cross-referenced as UMIACS-TR-91-166)
Keywords: Technical Report

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

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

Effect of acoustic radiation on the stability of spherical bubble oscillations - Gumerov, Nail A. (Physics of Fluids, 1998)

EFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION - Basri,Ronen; GROVE,ADAM J.; Jacobs, David W. (Pattern Recognition, 1998)
We consider the problem of reconstructing the shape of a 2-D object from multiple partial images related by scaled translations, in the presence of occlusion. Lindenbaum and Bruckstein have considered this problem in the specific case of a translating object seen by small sensors, for application to the understanding of insect vision. Their solution is limited by the fact that its run time is exponential in the number of images and sensors. We generalize the problem to allow for arbitrary types of occlusion of objects that translate and change scale. We show that this more general version of the problem can be solved in time that is polynomial in the number of sensors, but that even the original problem posed by Lindenbaum and Bruckstein is, in fact, NP-hard when the number of images is unbounded. Finally, we consider the case where the object is known to be convex. We show that Lindenbaum and Bruckstein’s version of the problem is then efficiently solvable even when many images are used, as is the general problem in certain more restricted cases.
Keywords: 2-D shape recovery from multiple images; NP-complete; Shape recovery with occlusion

Enhancing Automatic Acquisition of Thematic Structure in a Large-Scale Lexicon for Mandarin Chinese - Olsen,Mari; Dorr, Bonnie J; Thomas,Scott (Machine Translation and the Information SoupMachine Translation and the Information Soup, 1998)
This paper describes a refinement to our procedure for porting lexical conceptual structure (LCS) into new languages. Specifically we describe a two-step process for creating candidate thematic grids for Mandarin Chinese verbs, using the English verb heading the VP in the subde_nitions to separate senses, and roughly parsing the verb complement structure to match thematic structure templates. We accomplished a substantial reduction in manual effort, without substantive loss. The procedure is part of a larger process of creating a usable lexicon for interlingual machine translation from a large on-line resource with both too much and too little information.

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

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.

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

Feature-recognition for MEMS extraction - Baidya,B.; Gupta,S.K.; Mukherjee,T. (1998)

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

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.

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

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

Integrity constraints: Semantics and applications - Godfrey,P.; Grant,J.; Gryz,J.; Minker, Jack (Logics for databases and information systems, 1998)
Integrity constraints axe introduced in a logical framework. Examples are given to illustrate the expressiveness of integrity constraints. Various definitions for the semantics of integrity constraints are defined and compared. Additional types of constraints are also mentioned. Techniques of reasoning with integrity constraints, including model elimination and the residue method, are explained. Applications of integrity constraints considered in detail, including semantic query optimization, cooperative answering, combining databases, and view updates. Additional applications to order optimization, query folding, object-oriented databases, and database security are sketched. The conclusion lists areas of integrity constraints that need to be investigated.

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

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.

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

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

Modeling of particle motion in viscous swirl flow between two porous cylinders - Gumerov, Nail A.; Duraiswami, Ramani (Proc. ASME Fluids Engineering Division Summer Meeting, 1998)