Vision geometry XI(Seattle WA, 7-8 July 2002) - Latecki,L.J.; Mount, Dave; Wu,A. Y (SPIE proceedings series, 2002)

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

Your 802.11 network has no clothes - Mishra,A.; Shin,M.; Arbaugh, William A. (IEEE Communications Magazine, 2002)

Algorithms for facility location problems with outliers - Charikar,Moses; Khuller, Samir; Mount, Dave; Narasimhan,Giri (Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001)
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant clients, called outliers, can exert a disproportionately strong influence over the final solution. In this paper we explore a generalization of various facility location problems (K-center, K-median, uncapacitated facility location etc) to the case when only a specified fraction of the customers are to be served. What makes the problems harder is that we have to also select the subset that should get service. We provide generalizations of various approximation algorithms to deal with this added constraint.

The analysis of a probabilistic approach to nearest neighbor searching - Maneewongvatana,S.; Mount, Dave (Algorithms and Data Structures, 2001)
Given a set S of n data points in some metric space. Given a query point q in this space, a nearest neighbor query asks for the nearest point of S to q. Throughout we will assume that the space is real d-dimensional space Rd, and the metric is Euclidean distance. The goal is to preprocess S into a data structure so that such queries can be answered efficiently. Nearest neighbor searching has applications in many areas, including data mining [7], pattern classification [5], data compression [10].

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

Assessment of the k-epsilon turbulence model for compressible flows using direct simulation data - Sinha,K.; Candler,G. V; Martin, M.P (39th AIAA Aerospace Sciences Meeting and Exhibit, 2001)
We evaluate the k-epsilon turbulence model using direct numerical simulation (DNS) data of a Mach 4 boundary layer. We find that the low Reynolds number damping functions for the Reynolds stress must be corrected by the density ratio to match the DNS data. We present the budget of the k equation and assess the modeling of the various source terms. The models for all the source terms, except for the production and dilatational dissipation terms, are found to be adequate. Finally, we present the solenoidal dissipation rate equation and compute its budget using the boundary layer data. We compare this equation with the dissipation rate equation in an incompressible flow to show the equivalence between the two equations. This is the basis for modeling the solenoidal dissipation equation. However, an additional term in the equation due to variation of fluid viscosity needs to be modeled.

Becoming a Scholar in the Digital Age - Duderstadt,James; Arms,William; Messina,Paul; Ellisman,Mark; Atkins,Daniel; Fox,Edward; Shneiderman, Ben; Nissenbaum,Helen; Lederberg,Joshua (National Research Council, 2001)
Keywords: bibtex-import; digital-library; dlbook

Compiling PLAN to SNAP - Hicks, Michael W.; Moore,Jonathan; Nettles,Scott (Active NetworksActive Networks, 2001)
PLAN (Packet Language for Active Networks) [ 3 ] is a highly flexible and usable active packet language, whereas SNAP (Safe and Nimble Active Packets) [ 12 ] offers significant resource usage safety and achieves much higher performance compared to PLAN, but at the cost of flexibility and usability. Ideally, we would like to combine the good properties of PLAN with those of SNAP. We have achieved this end by developing a compiler that translates PLANi nto SNAP. The compiler allows us to achieve the flexibility and usability of PLAN, but with the safety and efficiency of SNAP. In this paper, we describe both languages, highlighting the features that require special compilation techniques. We then present the details of our compiler and experimental results to evaluate our compiler with respect to code size.

A comprehensive framework for testing graphical user interfaces - Memon, Atif M. (University of Pittsburgh, 2001)

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

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

Cryptographic counters and applications to electronic voting - Katz, Jonathan; Myers,S.; Ostrovsky,R. (Advances in Cryptology—Eurocrypt 2001, 2001)
We formalize the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately and robustly. The value of the counter can only be determined by a trusted authority (or group of authorities, which may include participants themselves), and participants cannot determine any information about the increment/decrement operations performed by other parties.Previous efficient implementations of such counters have relied on fully-homomorphic encryption schemes; this is a relatively strong requirement which not all encryption schemes satisfy. We provide an alternate approach, starting with any encryption scheme homomorphic over the additive group ℤ2 (i.e., 1-bit XOR). As our main result, we show a general and efficient reduction from any such encryption scheme to a general cryptographic counter. Our main reduction does not use additional assumptions, is efficient, and gives a novel implementation of a general counter. The result can also be viewed as an efficient construction of a general n-bit cryptographic counter from any 1-bit counter which has the additional property that counters can be added securely. As an example of the applicability of our construction, we present a cryptographic counter based on the quadratic residuosity assumption and use it to construct an efficient voting scheme which satisfies universal verifiability, privacy, and robustness. Work done while the author was at Telcordia Technologies.

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 software updating - Hicks, Michael W.; Moore,Jonathan T.; Nettles,Scott (Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, 2001)
Many important applications must run continuously and without interruption, yet must be changed to fix bugs or upgrade functionality. No prior general-purpose methodology for dynamic updating achieves a practical balance between flexibility, robustness, low overhead, and ease of use.We present a new approach for C-like languages that provides type-safe dynamic updating of native code in an extremely flexible manner (code, data, and types may be updated, at programmer-determined times) and permits the use of automated tools to aid the programmer in the updating process. Our system is based on dynamic patches that both contain the updated code and the code needed to transition from the old version to the new. A novel aspect of our patches is that they consist of verifiable native code (e.g. Proof-Carrying Code [17] or Typed Assembly Language [16]), which is native code accompanied by annotations that allow on-line verification of the code's safety. We discuss how patches are generated mostly automatically, how they are applied using dynamic-linking technology, and how code is compiled to make it updateable. To concretely illustrate our system, we have implemented a dynamically-updateable web server, FlashEd. We discuss our experience building and maintaining FlashEd. Performance experiments show that for FlashEd, the overhead due to updating is typically less than 1%.

On the efficiency of nearest neighbor searching with data clustered in lower dimensions - Maneewongvatana,S.; Mount, Dave (Computational Science—ICCS 2001, 2001)
Nearest neighbor searching is an important and fundamental problem in the field of geometric data structures. Given a set S of n data points in real d-dimensional space, R d, we wish to preprocess these points so that, given any query point q ∈ R d, the data point nearest to q can be reported quickly. We assume that distances are measured using any Minkowski distance metric, including the Euclidean, Manhattan, and max metrics. Nearest neighbor searching has numerous applications in diverse areas of science.

Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses - Mount, Dave; Netanyahu,Nathan S. (Computational Geometry, 2001)
Fitting two-dimensional conic sections (e.g., circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil–Sen and repeated median (RM) variants for estimating the center and radius of a circular arc, and for estimating the center and horizontal and vertical radii of an axis-aligned ellipse. The circular arc estimators have breakdown points of ≈ 21% and 50%, respectively, and the ellipse estimators have breakdown points of ≈ 16% and 50%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n2logn) for the circular case and O(n3logn) for the elliptical case. All algorithms use O(n) space in the worst case.
Keywords: Aligned ellipse fitting; Arrangements; Circular arc fitting; computational geometry; randomized algorithms; Range searching; RM estimator; robust estimation; Theil–Sen estimator

An empirical study of a new approach to nearest neighbor searching - Maneewongvatana,S.; Mount, Dave (Algorithm Engineering and Experimentation, 2001)
In nearest neighbor searching we are given a set of n data points in real d-dimensional space, ℜd, and the problem is to preprocess these points into a data structure, so that given a query point, the nearest data point to the query point can be reported efficiently. Because data sets can be quite large, we are interested in data structures that use optimal O(dn) storage.In this paper we consider a novel approach to nearest neighbor searching, in which the search returns the correct nearest neighbor with a given probability assuming that the queries are drawn from some known distribution. The query distribution is represented by providing a set of training query points at preprocessing time. The data structure, called the overlapped split tree, is an augmented BSP-tree in which each node is associated with a cover region, which is used to determine whether the search should visit this node. We use principal component analysis and support vector machines to analyze the structure of the data and training points in order to better adapt the tree structure to the data sets. We show empirically that this new approach provides improved predictability over the kd-tree in average query performance.

Entropy-preserving cuttings and space-efficient planar point location - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001)
Point location is the problem of preprocessing a planar polygonal subdivision S into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. Given the probabilities pz that the query point lies within each cell z ∈ S, a natural question is how to design such a structure so as to minimize the expected-case query time. The entropy H of the probability distribution is the dominant term in the lower bound on the expected-case search time. Clearly the number of edges n of the subdivision is a lower bound on the space required. There is no known approach that simultaneously achieves the goals of H + &Ogr;(H) query time and &Ogr;(n) space. In this paper we introduce entropy-preserving cuttings and show how to use them to achieve query time H + &Ogr;(H), using only &Ogr;(n log* n) space.

E-tables: Non-specialist use and understanding of statistical data - Marchionini,G.; Hert,C.; Shneiderman, Ben; Liddy,L. (SURFACE, the Syracuse University Research Facility And Collaborative Environment, 2001)
This paper provides a progress report on a project that aims to understand how people think about and understand statistical data presented in tables. The focus is on people who are not statistical specialists. To this end, studies of various user populations were conducted, underlying data enrichment and explanation was investigated, and interactive user interface prototypes were developed and tested.

An experience management system for a software engineering research organization - Basili, Victor R.; Costa,P.; Lindvall,M.; Mendonca,M.; Seaman,C.; Tesoriero,R.; Zelkowitz, Marvin V (Software Engineering Workshop, 2001. Proceedings. 26th Annual NASA Goddard, 2001)
Most businesses rely on the fact that their employees possess relevant knowledge and that they can apply it to the task at hand. The problem is that this knowledge is not owned by the organization. It is owned and controlled by its employees. Maintaining an appropriate level of knowledge in the organization is a very important issue. It is, however, not an easy task for most organizations, and it is particularly problematic for software organizations, which are human- and knowledge-intensive. Knowledge management is a relatively new area that has attempted to address these problems. This paper introduces an approach called the "knowledge dust-to-pearls" approach. This approach addresses some of the issues with knowledge management by providing low-barrier mechanisms to "jump start" the experience base. This approach allows the experience base to become more useful more quickly than traditional approaches. This paper describes the approach and gives an example of its use at the Fraunhofer Center for Experimental Software Engineering, Maryland, USA
Keywords: and; approach; knowledge; base; experience; Center; control; knowledge; data; development; dust-to-pearls; engineering; Engineering; business; engineering; software; experimental; for; Fraunhofer; houses; knowledge; employee; knowledge; experience; level; maintenance; knowledge; management; management; knowledge; management; software; mechanisms; software; organization; software; organizational; organizations; administrative; organizations; knowledge; organizations; low-barrier; ownership; knowledge-intensive; processing; personnel; research; research; software; system; human-intensive

Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry - Barrett,Chris; Cook,Doug; Hicks,Gregory; Faber,Vance; Marathe,Achla; Marathe,Madhav; Srinivasan, Aravind; Sussmann,Yoram; Thornquist,Heidi (Algorithm EngineeringAlgorithm Engineering, 2001)
We consider the bilateral contract satisfaction problem arising from electrical power networks due to the proposed deregulation of the electric utility industry in the USA. Given a network and a (multi)set of pairs of vertices (contracts) with associated demands, the goal is to find the maximum number of simultaneously satisfiable contracts. We study how four different algorithms perform in fairly realistic settings; we use an approximate electrical power network from Colorado. Our experiments show that three heuristics outperform a theoretically better algorithm. We also test the algorithms on four types of scenarios that are likely to occur in a deregulated marketplace. Our results show that the networks that are adequate in a regulated marketplace might be inadequate for satisfying all the bilateral contracts in a deregulated industry.

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

Integrating distributed scientific data sources with MOCHA and XRoaster - Rodriguez-Martinez,M.; Roussopoulos, Nick; McGann,J. M; Kelley,S.; Mokwa,J.; White,B.; Jala,J. (Thirteenth International Conference on Scientific and Statistical Database Management, 2001. SSDBM 2001. Proceedings, 2001)
MOCHA is a novel middleware system for integrating distributed data sources that we have developed at the University of Maryland. MOCHA is based on the idea that the code that implements user-defined types and functions should be automatically deployed to remote sites by the middleware system itself. To this end, we have developed an XML-based framework to specify metadata about data sites, data sets, and user-defined types and functions. XRoaster is a graphical tool that we have developed to help the user create all the XML metadata elements to be used in MOCHA
Keywords: client-server systems; data sets; data sites; Databases; Distributed computing; distributed databases; distributed scientific data source integration; Educational institutions; graphical tool; hypermedia markup languages; IP networks; java; Large-scale systems; Maintenance engineering; meta data; metadata; Middleware; middleware system; MOCHA; Query processing; remote sites; scientific information systems; user-defined types; visual programming; XML; XML metadata elements; XML-based framework; XRoaster

Mandarin-English Information (MEI): investigating translingual speech retrieval - Meng,Helen; Chen,Berlin; Khudanpur,Sanjeev; Levow,Gina-Anne; Lo,Wai-Kit; Oard, Douglas; Schone,Patrick; Tang,Karen; Wang,Hsin-Min; Wang,Jianqiang (Proceedings of the first international conference on Human language technology research, 2001)
This paper describes the Mandarin-English Information (MEI) project, where we investigated the problem of cross-language spoken document retrieval (CL-SDR), and developed one of the first English-Chinese CL-SDR systems. Our system accepts an entire English news story (text) as query, and retrieves relevant Chinese broadcast news stories (audio) from the document collection. Hence this is a cross-language and cross-media retrieval task. We applied a multi-scale approach to our problem, which unifies the use of phrases, words and subwords in retrieval. The English queries are translated into Chinese by means of a dictionary-based approach, where we have integrated phrase-based translation with word-by-word translation. Untranslatable named entities are transliterated by a novel subword translation technique. The multi-scale approach can be divided into three subtasks -- multi-scale query formulation, multi-scale audio indexing (by speech recognition) and multi-scale retrieval. Experimental results demonstrate that the use of phrase-based translation and subword translation gave performance gains, and multi-scale retrieval outperforms word-based retrieval.
Keywords: cross-language; English-Chinese; spoken document retrieval

Messenger RNA Splicing Signals - Mount, Stephen M. (eLS, 2001)
Splicing signals are elements in the DNA sequence of a gene that specify the accurate splicing of its primary RNA transcript to generate its mature RNA product.
Keywords: consensus sequences; exon definition; small nuclear ribonucleoprotein particles (snRNPs); splice site selection; splicing enhancers

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.

Near-optimal design of MP S tunnels with shared recovery - Fleischer,L.; Meyerson,A.; Saniee,I.; Shepherd,FB; Srinivasan, Aravind (DIMACS Mini-Workshop on Quality of Service Issues in the Internet, 2001)
We describe the optimization problem associ-ated with the concurrent routing of demands with guar- anteed shared recovery in case of network failures. This problem arises in routing with protection in meshes and is known to be hard. We describe the problem in the context of the efficient design of restorable MP S tunnels in optical networks. The underlying design gives rise to a stochastic optimization problem that is equivalent to a (very) large- scale linear programming (LP) problem that explicitly in- corporates the network failure scenarios. The feasible re- gion for this LP is given by combined packing and cover- ing constraints for concurrent and optimal multicommodity flows. We develop a novel -approximation procedure for this problem and demonstrate its performance for a variety of real network sizes. An attraction of our approach is that its main computation consists of routing flow along a pair of short paths and these paths are easily found. Commer- cial general-purpose LP solvers are typically unable to solve these problems once they become large enough, while our approach scales for large networks. We conclude that the proposed scheme provides guaranteed approximation to the design of restorable MP S tunnels with shared protection within realistic network settings.

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.

Practical programmable packets - Moore,J. T; Hicks, Michael W.; Nettles,S. (IEEE INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2001)
We present SNAP (safe and nimble active packets), a new scheme for programmable (or active) packets centered around a new low-level packet language. Unlike previous active packet approaches, SNAP is practical: namely, adding significant flexibility over IP without compromising safety and security or efficiency. In this paper we show how to compile from the well-known active picket language PLAN to SNAP, showing that SNAP retains PLAN's flexibility; give proof sketches of its novel approach to resource control; and present experimental data showing SNAP attains performance very close to that of a software IP router
Keywords: active picket language; Application software; complier; Contracts; Data security; efficiency; Explosives; INFORMATION SCIENCE; Internet; IP; IP networks; low-level packet language; packet switching; performance; PLAN; practical programmable packets; program compilers; Protection; resource control; Resource management; safe and nimble active packets; Safety; Security; SNAP; software IP router; Software performance; telecommunication security; Transport protocols

The price of safety in an active network - Alexander,D. S; Menage,P. B; Keromytis,A. D; Arbaugh, William A.; Anagnostakis,K. G; Smith,J. M (Journal of Communications and Networks, 2001)

A prototype experience management system for a software consulting organization - Mendonça Neto,M. G.; Seaman,C.; Basili, Victor R.; Kim,Y. M (Thirteenth International Conference on Software Engineering and Knowledge Engineering, 2001)
The Experience Management System (EMS) is aimed atsupporting the capture and reuse of software-related experience, based on the Experience Factory concept. It is being developed for use in a multinational software engineering consultancy, Q-Labs. Currently, a prototype EMS exists and has been evaluated. This paper focuses on the EMS architecture, underlying data model, implementation, and user interface.

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

Rotation, scale, and translation resilient public watermarking for images using a log-polar fourier transform - Bloom,Jeffrey A.; Cox,Ingemar J.; Miller,Matthew L.; M. Wu; Lin,Ching-Yung; Lui,Yui Man (2001)
A method for detecting a watermark signal in digital image data. The detecting method includes the steps of: computing a log-polar Fourier transform of the image data to obtain a log-polar Fourier spectrum; projecting the log-polar Fourier spectrum down to a lower dimensional space to obtain an extracted signal; comparing the extracted signal to a target watermark signal; and declaring the presence or absence of the target watermark signal in the image data based on the comparison. Also provided is a method for inserting a watermark signal in digital image data to obtain a watermarked image. The inserting method includes the steps of: computing a log-polar Fourier transform of the image data to obtain a log-polar Fourier spectrum; projecting the log-polar Fourier spectrum down to a lower dimensional space to obtain an extracted signal; modifying the extracted signal such that it is similar to a target watermark; performing a one-to-many mapping of the modified signal back to...

Rotation, scale, and translation resilient watermarking for images - Lin,C.-Y.; Wu,M.; Bloom,J.A.; Cox,I.J.; Miller,M.L.; Lui,Y.M. (Image Processing, IEEE Transactions on, 2001)
Many electronic watermarks for still images and video content are sensitive to geometric distortions. For example, simple rotation, scaling, and/or translation (RST) of an image can prevent blind detection of a public watermark. In this paper, we propose a watermarking algorithm that is robust to RST distortions. The watermark is embedded into a one-dimensional (1-D) signal obtained by taking the Fourier transform of the image, resampling the Fourier magnitudes into log-polar coordinates, and then summing a function of those magnitudes along the log-radius axis. Rotation of the image results in a cyclical shift of the extracted signal. Scaling of the image results in amplification of the extracted signal, and translation of the image has no effect on the extracted signal. We can therefore compensate for rotation with a simple search, and compensate for scaling by using the correlation coefficient as the detection measure. False positive results on a database of 10 000 images are reported. Robustness results on a database of 2000 images are described. It is shown that the watermark is robust to rotation, scale, and translation. In addition, we describe tests examining the watermarks resistance to cropping and JPEG compression
Keywords: axis; one-dimensional; coding; security; coefficient; cropping; cyclical; compression; RST; coordinates; log-radius; data; detection; correlation; distortions; blind; distortions; images; log-polar; encapsulation; image; Fourier; images; translation; magnitudes; Fourier; measure; geometric; of; protection; data; resilient; shift; detection; signal; public; transform; JPEG; transforms; copy; watermark; resampling; rotation; scale; search; still; watermarking; video; Fourier

Secure Health Information Sharing System: SHARE - M. Wu; Mui,Lik; Mohtashemi,Mojdeh; Szolovits,Peter (Proceedings of the AMIA SymposiumProc AMIA Symp, 2001)

A simple entropy-based algorithm for planar point location - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, 2001)
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. This problem has been considered before, but existing data structures are all quite complicated. In this paper, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point location queries in &Ogr;(H) average time. We also present empirical evidence for the practical efficiency of this approach.

Source Selection and Ranking in the WebSemantics Architecture Using Quality of Data Metadata-1 Introduction - Mihaila,G. A; Raschid, Louiqa; Vidal,M. E (Advances in Computers, 2001)

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

Translation lexicon acquisition from bilingual dictionaries - David Doermann; Ma,H.; Karagol-Ayan,B.; Oard, Douglas (Proceedings of SPIE, 2001)

Transmission Lines and Lumped Circuits. Academic Press Series in Electromagnetism - Maffucci,A.; Mayergoyz, Issak D (Elsevier Science & Technology, 2001)

A trend analysis of exploitations - Browne,H. K; Arbaugh, William A.; McHugh,J.; Fithen,W. L (2001 IEEE Symposium on Security and Privacy, 2001. S&P 2001. Proceedings, 2001)
We have conducted an empirical study of a number of computer security exploits and determined that the rates at which incidents involving the exploit are reported to CERT can be modeled using a common mathematical framework. Data associated with three significant exploits involving vulnerabilities in phf, imap, and bind can all be modeled using the formula C=I+S×√M where C is the cumulative count of reported incidents, M is the time since the start of the exploit cycle, and I and S are the regression coefficients determined by analysis of the incident report data. Further analysis of two additional exploits involving vulnerabilities in mountd and statd confirm the model. We believe that the models will aid in predicting the severity of subsequent vulnerability exploitations, based on the rate of early incident reports
Keywords: Computer science; computer security exploits; Data analysis; data mining; Educational institutions; exploitations; Performance analysis; Predictive models; Regression analysis; Risk management; security of data; software engineering; system intrusions; System software; trend analysis; vulnerabilities; vulnerability exploitation

Vision Geometry X - Latecki,L.J.; Mount, Dave; Wu,A. Y; Melter,R.A. (Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2001)

Adaptive query processing: Technology in evolution - Hellerstein,J. M; Franklin,M.J.; Chandrasekaran,S.; Deshpande, Amol; Hildrum,K.; Madden,S.; Raman,V.; Shah,M. A (IEEE Data Engineering Bulletin, 2000)
As query engines are scaled and federated, they must cope with highly unpredictable and changeableenvironments. In the Telegraph project, we are attempting to architect and implement a continuously adaptive query engine suitable for global-area systems, massive parallelism, and sensor networks. To set the stage for our research, we present a survey of prior work on adaptive query processing, focusing on three characterizations of adaptivity: the frequency of adaptivity, the effects of adaptivity, and the extent of adaptivity. Given this survey, we sketch directions for research in the Telegraph project.

The African trypanosome genome - El‐Sayed, Najib M.; Hegde,Priti; Quackenbush,John; Melville,Sara E.; Donelson,John E. (International Journal for Parasitology, 2000)
The haploid nuclear genome of the African trypanosome, Trypanosoma brucei, is about 35 Mb and varies in size among different trypanosome isolates by as much as 25%. The nuclear DNA of this diploid organism is distributed among three size classes of chromosomes: the megabase chromosomes of which there are at least 11 pairs ranging from 1 Mb to more than 6 Mb (numbered I-XI from smallest to largest); several intermediate chromosomes of 200-900 kb and uncertain ploidy; and about 100 linear minichromosomes of 50-150 kb. Size differences of as much as four-fold can occur, both between the two homologues of a megabase chromosome pair in a specific trypanosome isolate and among chromosome pairs in different isolates. The genomic DNA sequences determined to date indicated that about 50% of the genome is coding sequence. The chromosomal telomeres possess TTAGGG repeats and many, if not all, of the telomeres of the megabase and intermediate chromosomes are linked to expression sites for genes encoding variant surface glycoproteins (VSGs). The minichromosomes serve as repositories for VSG genes since some but not all of their telomeres are linked to unexpressed VSG genes. A gene discovery program, based on sequencing the ends of cloned genomic DNA fragments, has generated more than 20 Mb of discontinuous single-pass genomic sequence data during the past year, and the complete sequences of chromosomes I and II (about 1 Mb each) in T. brucei GUTat 10.1 are currently being determined. It is anticipated that the entire genomic sequence of this organism will be known in a few years. Analysis of a test microarray of 400 cDNAs and small random genomic DNA fragments probed with RNAs from two developmental stages of T. brucei demonstrates that the microarray technology can be used to identify batteries of genes differentially expressed during the various life cycle stages of this parasite.

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

Approximate range searching - Arya,Sunil; Mount, Dave (Computational Geometry, 2000)
The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and ε>0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance εw of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in Rd can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/ε)d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/ε)d−1) time. We also present a lower bound for approximate range searching based on partition trees of Ω(logn+(1/ε)d−1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.
Keywords: Approximation algorithms; Box-decomposition trees; Partition trees; Range searching

Assessment of Temperature Fluctuation Models for RANS Simulations of Hypersonic Reacting Flows - Sinha,K.; Martin, M.P; Candler,G. V (38th AIAA Aerospace Sciences Meeting and Exhibit, 2000)
Turbulence-chemistry interactions play an important role in various fluid flow problems. In a hypersonic boundary layer, these interactions can alter the surface heating rate of the vehicle by modifying the temperature profile across the layer. The effect of these interactions is accounted for in a Reynolds-averaged Navier Stokes (RANS) simulation using a probability density function (PDF) of the temperature distribution. In this paper, two presumed PDF models are considered, namely, the Martin and Candler model and the Gaffney et al. model, and their accuracy is assessed by comparing to direct numerical simulation (DNS) of homogeneous isotropic turbulence. TheMartin and Candler model reproduces the turbulence-chemistry interactions in the flow correctly whereas the Gaffney model overpredicts the temperature fluctuations.

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

Breakout Session Report: Principles and Methods - Jacobs, David W.; Malik,J.; Nevatia, R. (Perceptual Organization for Artificial Vision Systems, 2000)
This report will present a summary of views presented during a discussion at the 1999 Workshop on Perceptual Organization in Computer Vision. Our goal is to present diverse views, informally expressed on principles and algorithms of perceptual organization. Naturally, such a discussion must be somewhat limited both by the time available and by the specific set of researchers who could be present. Still, we hope to describe some interesting ideas expressed and to note the number of areas of apparent consensus among a fairly broad group. In particular, we will describe views on the state of the art in perceptual grouping, and what seem to be key open questions and promising directions for addressing them.

Chromatic nearest neighbor searching: A query sensitive approach - Mount, Dave; Netanyahu,Nathan S.; Silverman,Ruth; Wu,Angela Y. (Computational Geometry, 2000)
The nearest neighbor problem is that of preprocessing a set P of n data points in Rd so that, given any query point q, the closest point in P to q can be determined efficiently. In the chromatic nearest neighbor problem, each point of P is assigned a color, and the problem is to determine the color of the nearest point to the query point. More generally, given k⩾1, the problem is to determine the color occurring most frequently among the k nearest neighbors. The chromatic version of the nearest neighbor problem is used in many applications in pattern recognition and learning. In this paper we present a simple algorithm for solving the chromatic k nearest neighbor problem. We provide a query sensitive analysis, which shows that if the color classes form spatially well separated clusters (as often happens in practice), then queries can be answered quite efficiently. We also allow the user to specify an error bound ε⩾0, and consider the same problem in the context of approximate nearest neighbor searching. We present empirical evidence that for well clustered data sets, this approach leads to significant improvements in efficiency.
Keywords: BBD trees; Branch-and-bound search; Chromatic nearest neighbors; Classification algorithms; Multidimensional searching; pattern recognition; Query sensitive analysis

Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions - Cook,D.; Hicks,G.; Faber,V.; Marathe,M. V; Srinivasan, Aravind; Sussmann,Y. J; Thornquist,H. (NONCONVEX OPTIMIZATION AND ITS APPLICATIONS, 2000)

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

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

DNS of a Mach 4 boundary layer with chemical reactions - Martin, M.P (AIAA, Aerospace Sciences Meeting and Exhibit, 38 th, Reno, NV, 2000)

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

Evaluation of sense disambiguation given hierarchical tag sets - Melamed,I.D.; Resnik, Philip (Computers and the Humanities, 2000)

Extending understanding of federal statistics in tables - Marchionini,Gary; Hert,Carol; Liddy,Liz; Shneiderman, Ben (Proceedings of the 2000 annual national conference on Digital government research, 2000)
This paper describes progress toward improving user interfaces for US Federal government statistics that are presented in tables. Based on studies of user behaviors and needs related to statistical tables, we describe interfaces to assist diverse users with a range of statistical literacy to explore, find, understand, and use US Federal government statistics.
Keywords: data exploration; dynamic queries; Statistics; tablular data; User interfaces

Genomic Sequence, Splicing, and Gene Annotation - Mount, Stephen M. (American Journal of Human GeneticsAm J Hum Genet, 2000)

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

Introduction to logic-based artificial intelligence - Minker, Jack (Logic-based artificial intelligenceLogic-based artificial intelligence, 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)

Logic-Based Artificial Intelligence - Minker, Jack (Springer, 2000)
This landmark volume represents the culmination of over 40 years of research in the use of logic as a basis for representing and manipulating problems in the field of artificial intelligence. The use of logic as a basis for commonsense reasoning was started by John McCarthy in 1959. The collection consists of both original research and surveys of almost every subject that uses logic in AI, contributed by leading scientists, and grew out of preliminary work presented at the Workshop on Logic-Based Artificial Intelligence held in Washington, DC, June 1999. All papers have been extensively refereed and revised. The introductory article presents background on research that has transpired since 1959 and discusses the significance of each chapter in this context. The topics covered in the book are commonsense reasoning, knowledge representation, nonmonotonic reasoning, logic for causation and actions, planning and problem solving, cognitive robotics, logic for agents and actions, inductive reasoning, possibilistic logic, logic and beliefs, logic and language, computational logic, knowledge base system implementations, and applications of theorem proving and logic programming. Logic-Based Artificial Intelligence is invaluable to graduate students and researchers in artificial intelligence, and advanced methods for database and knowledge base systems. Logic-Based Artificial Intelligence will also be of interest to those applying theorem proving methods to problems in program and hardware verification, to those who deal with large knowledge base systems, those developing cognitive robotics, and for those interested in the solution of McCarthy's 1959 "oldest planning problem in AI: getting from home to the airport".
Keywords: Artificial intelligence; COMPUTER LOGIC; Computers / Computer Science; Computers / Intelligence (AI) & Semantics; Logic, Symbolic and mathematical; Mathematics / Logic; Medical / General

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

MOCHA: a database middleware system featuring automatic deployment of application-specific functionality - Rodrıguez-Martinez,M.; Roussopoulos, Nick; McGann,J. M; Keyley,S.; Katz,V.; Song,Z.; JaJa, Joseph F. (Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, 2000)

A model for magnetic aftereffect in the presence of time varying demagnetizing fields - Korman,C.E.; Adly,A.A.; Mayergoyz, Issak D; Rugkwamsook,P. (Magnetics, IEEE Transactions on, 2000)
Preisach models driven by stochastic inputs are employed to model magnetic aftereffect in the presence of demagnetizing fields. As a result of thermal relaxation, the magnetization and, consequently, the demagnetizing field vary in time. The new model generalizes earlier work and self-consistently accounts for the effect of time varying demagnetizing fields on the relaxation process. Three practical numerical techniques are proposed to compute the time variation in the magnetic field and the state of the Preisach plane
Keywords: aftereffect; aftereffect; magnetization; numerical; demagnetizing; field; demagnetisation; magnetic; model; magnetic; Preisach; relaxation; time; simulation; thermal; varying

Nearly optimal expected-case planar point location - Arya,S.; Malamatos,T.; Mount, Dave (Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, 2000)
We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell
Keywords: computational geometry; convex cells; data structure; expected search time; nearly optimal expected-case planar point location; optimal binary search tree; planar point location; planar polygonal subdivision; polygonal cells; polygonal subdivision; probability; search problems; search structure; subdivision; trees (mathematics)

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.

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

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)

Pre-Messenger RNA Processing Factors in the Drosophila Genome - Mount, Stephen M.; Salz,Helen K. (The Journal of Cell BiologyJ Cell Biol, 2000)
In eukaryotes, messenger RNAs are generated by a process that includes coordinated splicing and 3′ end formation. Factors essential for the splicing of mRNA precursors (pre-mRNA) in eukaryotes have been identified primarily through the study of nuclear extracts derived from mammalian cells and Saccharomyces cerevisiae genetics. Here, we identify homologues of most known pre-mRNA processing factors in the recently completed sequence of the Drosophila genome. The set of proteins required for RNA processing shows remarkably little variation among eukaryotic species, and individual proteins are highly conserved. In general, proteins involved in the mechanics of RNA processing are even more conserved than proteins involved in the interpretation of RNA processing signals. The genome does not appear to contain a gene for the U11 RNA, or for a protein unique to the U11 snRNP, which raises the possibility that the U12-dependent spliceosome functions without U11 in Drosophila.

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

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

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)

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

Secure quality of service handling: SQoSH - Alexander,D. S; Arbaugh, William A.; Keromytis,A. D; Muir,S.; Smith,J. M (IEEE Communications Magazine, 2000)
Proposals for programmable network infrastructures, such as active networks and open signaling, provide programmers with access to network resources and data structures. The motivation for providing these interfaces is accelerated introduction of new services, but exposure of the interfaces introduces many new security risks. We describe some of the security issues raised by active networks. We then describe our secure active network environment (SANE) architecture. SANE was designed as a security infrastructure for active networks, and was implemented in the SwitchWare architecture. SANE restricts the actions that loaded modules can perform by restricting the resources that can be named; this is further extended to remote invocation by means of cryptographic credentials. SANE can be extended to support restricted control of quality of service in a programmable network element. The Piglet lightweight device kernel provides a “virtual clock” type of scheduling discipline for network traffic, and exports several tuning knobs with which the clock can be adjusted. The ALIEN active loader provides safe access to these knobs to modules that operate on the network element. Thus, the proposed SQoSH architecture is able to provide safe, secure access to network resources, while allowing these resources to be managed by end users needing customized networking services. A desirable consequence of SQoSH's integration of access control and resource control is that a large class of denial-of-service attacks, unaddressed solely with access control and cryptographic protocols, can now be prevented
Keywords: Acceleration; Access control; active networks; ALIEN active loader; Clocks; Computer network management; cryptographic credentials; cryptography; customized networking services; Data security; Data structures; denial-of-service attacks; interfaces; Kernel; loaded modules; network resources; network traffic; open signaling; packet switching; Piglet lightweight device kernel; programmable network element; programmable network infrastructures; Programming profession; Proposals; quality of service; remote invocation; resource control; restricted control of quality of service; SANE; scheduling; scheduling discipline; secure active network environment architecture; secure quality of service handling; security infrastructure; security risks; SQoSH; SwitchWare architecture; telecommunication security; tuning knobs; virtual clock

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

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

Systematic consolidation of input and output buffers in synchronous dataflow specifications - Murthy,P. K; Bhattacharyya, Shuvra S. (Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on, 2000)

Tools and Techniques for Video Performances Evaluation - David Doermann; Mihalcik,D. (ICPR, 2000)

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

Using quality of data metadata for source selection and ranking - Mihaila,G. A; Raschid, Louiqa; Vidal,M. E (Proceedings of the Third International Workshop on the Web and Databases, WebDB, 2000)

Visibility stabs and depth-first spiralling on line segments in output sensitive time - Keil,M.; Mount, Dave; Wismath,S.K. (International Journal of Computational Geometry and Applications, 2000)
Given a set S of n non-intersecting line segments in the plane, we present a newtechnique for e ciently traversing the endpoint visibility graph of S to solve a variety of visibility problems in output sensitive time. In particular, we develop two techniques to compute the 2n visibility polygons of the endpoints of S, in output sensitive time. Depth- rst spiralling is a technique that relies on the ordered endpoint visibility graph information to traverse the endpoints of S in a spiral-like manner using a combination of Jarvis' March and depth- rst search. It is a practical method and has been implemented in C++ using LEDA.

Vision geometry IX:(San Diego CA, 30-31 July 2000) - Latecki,L.J.; Mount, Dave; Wu,A. Y (SPIE proceedings series, 2000)

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

Web based progressive transmission for browsing remotely sensed imagery - Mareboyana,M.; Srivastava,S.; JaJa, Joseph F. (Geoscience and Remote Sensing Symposium, 2000. Proceedings. IGARSS 2000. IEEE 2000 International, 2000)
This paper describes an image representation technique that entails progressive refinement of user specified regions of interest (ROI) of large images. Progressive refinement to original quality can be accomplished in theory. However, due to heavy burden on storage resources for the authors' applications, they restrict the refinement to about 25% of the original data resolution. A wavelet decomposition of the data combined with scalar and vector quantization (VQ) of the high frequency components and JPEG/DCT compression of low frequency component is used as representation framework. Their software will reconstruct the region selected by the user from its wavelet decomposition such that it fills up the preview window with the appropriate subimages at the desired resolution, including full resolution stored for preview. Further refinement from the first preview can be obtained progressively by transmitting high frequency coefficients from low resolution to high resolution which are compressed by variant of vector quantization called model-based VQ (MVQ). The user will have an option for progressive build up of the ROIs until full resolution stored or terminate the transmission at any time during the progressive refinement
Keywords: based; decomposition; geophysical; image; model-based; interest; remote; interest; vector; mapping; user; mapping; vector; measurement; of; processing; geophysical; processing; image; Progressive; quantisation; wavelet; quantization; wavelet; refinement; region; regions; representation; land; representation; remote; sensing; scalar; terrain; sensing; terrain; signal; specified; specified; user; surface; large; technique; image; techniques; image; transforms; transmission; browsing; geophysical; VQ; progressive; Web

Windows of Vulnerability: A Case Study Analysis - Arbaugh, William A.; Fithen,William L.; McHugh,John (Computer, 2000)
The authors propose a life-cycle model for system vulnerabilities, applying to three case studies to show how systems remain vulnerable long after security fixes are available. Complex information and communication systems give rise to design, implementation, and management errors, leading to a vulnerability in an information technology product that can allow security policy violations. Using their vulnerability life-cycle model, the authors present a case study analysis of specific computer vulnerabilities. For each case, the authors provide background information about the vulnerability, such as how attackers exploited it and which systems were affected. They tie the case to the life-cycle model by identifying the dates for each state within the model. Finally, they use a histogram of reported intrusions to show the life of the vulnerability and conclude with an analysis specific to the particular vulnerability.

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

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

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

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

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

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

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

Binary version management for computational grids - Hollingsworth, Jeffrey K; Miller, E. L; Akala, K. (Parallel processing letters, 1999)

The budgeted maximum coverage problem - Khuller, Samir; Moss,A.; Naor,J. S (Information Processing Letters, 1999)

Chunks in PLAN: Language support for programs as packets - Moore,J. T; Hicks, Michael W.; Nettles,S. (PROCEEDINGS OF THE ANNUAL ALLERTON CONFERENCE ON COMMUNICATION CONTROL AND COMPUTING, 1999)

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

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

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

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

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

Efficient algorithms for robust feature matching - Mount, Dave; Netanyahu,N. S; Le Moigne,J. (Pattern Recognition, 1999)
One of the basic building blocks in any point-based registration scheme involves matching feature points that areextracted from a sensed image to their counterparts in a reference image. This leads to the fundamental problem of point matching: Given two sets of points, find the (affine) transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between the two point sets be robust to these effects. We measure distances using the partial Hausdorff distance. Point matching can be a computationally intensive task, and a number of theoretical and applied approaches have been proposed for solving this problem. In this paper, we present two algorithmic approaches to the point matching problem, in an attempt to reduce its computational complexity, while still providing a guarantee of the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and- bound approach due to Huttenlocher and Rucklidge, (Technical Report 1321, Dept. of Computer Science, Cornell University, Ithaca, 1992; Proc. IEEE Conf. on Computer vision and Pattern Recognition, New York, 1993, pp. 705—706). We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. This algorithm operates within the framework of a branch-and-bound procedure, but employs point-to-point alignments to accelerate the search. We show that this combination retains many of the strengths of branch-and-bound search, but provides significantly faster search times by exploiting alignments. With high probability, this method succeeds in finding an approximately optimal match. We demonstrate the algorithms’ performances on both synthetically generated data points and actual satellite images.

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.

End-to-end request handling in distributed Video-on-Demand systems - Mundur, Padma; Simon,R.; Sood,A. (Proceedings of the CNDS Conference (Society for Computer Simulation), 1999)

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

An Exploratory Study of Video Browsing, User Interface Designs and Research Methodologies: Effectiveness in Information Seeking Tasks - Tse,T.; Vegh,S.; Shneiderman, Ben; Marchionini,G. (PROCEEDINGS OF THE ANNUAL MEETING-AMERICAN SOCIETY FOR INFORMATION SCIENCE, 1999)
The purpose of this exploratory study is to develop research methods to compare the effectiveness of two video browsing interface designs, or surrogates one static (storyboard) and one dynamic (slide show) on two distinct information seeking tasks (gist determination and object recognition). Although video data is multimodal, potentially consisting of images, speech, sound, and text, the surrogates tested depend on image data only and use key frames or stills extracted from source video. A test system was developed to determine the effects of different key frame displays on user performance in specified information seeking tasks. The independent variables were interface display and task type. The dependent variables were task accuracy and subjective satisfaction. Covariates included spatial visual ability and time-to-completion. The study used a repeated block factorial 2x2 design; each of 20 participants interacted with all four interface-task combinations. No statistically significant results for task accuracy were found. Statistically significant differences were found, however, for user satisfaction with the display types: users assessed the static display to be "easier" to use than the dynamic display for both task types, even though there were no performance differences. This methodological approach provides a useful way to learn about the relationship between surrogate types and user tasks during video browsing.

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

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

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

Imprecise Calendars: an Approach to Scheduling Computational Grids - Hollingsworth, Jeffrey K; Maneewongvatana, Songrit (Distributed Computing Systems, International Conference on, 1999)
We describe imprecise calendars, a way to organize and schedule clusters of nodes in a computation grid. Imprecise calendars permit the easy and efficient sharing of resources between different clusters of computers that are part of a computational grid. In addition, they can be used to provide specific time reservations for applications. We describe the algorithms and policies for manipulation of imprecise calendars. We also include a series of simulation studies that compare our approach to previous batch scheduling systems for both a single cluster and collection of clusters up to over 3,000 nodes.
Keywords: parallel computing distributed scheduling computational grid batch scheduler meta computing

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

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

Integrated admission control in hierarchical video-on-demand systems - Mundur, Padma; Simon,R.; Sood,A. (IEEE International Conference on Multimedia Computing and Systems, 1999, 1999)
We develop a unified model of a hierarchical video-on-demand (VoD) system by integrating the storage and the network subsystems. Rather than restricting the analysis to an isolated subsystem the performance of the VoD system is analyzed as an end-to-end system. On a system-wide basis, request handling and admission control policies are designed to minimize global performance metrics. Through our simulation, we compare different request handling policies and show that a hierarchical VoD architecture with request handling that allows retrials at more than one resource will minimize overall blocking
Keywords: Admission control; Bandwidth; blocking; Computer science; Design methodology; end-to-end system; hierarchical video-on-demand systems; integrated admission control; Intelligent networks; Load management; Motion pictures; Network servers; network subsystem; performance; Performance analysis; performance evaluation; quality of service; request handling; resource allocation; Resource management; simulation; storage subsystem; video on demand; video servers

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

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

An international SIGCHI research agenda - Scholtz,Jean C.; Muller,Michael; Novick,David; Olsen,Jr.,Dan R.; Shneiderman, Ben; Wharton,Cathleen (CHI '99 extended abstracts on Human factors in computing systems, 1999)
The goal of this workshop is to articulate an HCI research agenda statement, along with plans for continued refinement with the greater CHI community and plans for disseminating the information beyond the CHI community. There are been several similar prior efforts, including:• 1998 Universal Access program [2]• European community report, "Building the European Information Society for Us All" [1];• CHI 97 workshop [5] and paper [6], "HCI Research and Practice Agenda based on Human Needs …";• CHI 96 Workshop, "CHI Ten-Year View…" [3];• 1995 US National Science Foundation report, "New Directions in Human-Computer Interaction …" [9];• 1995 report from the US National Research Council [7];• 1991 report, "…HCI… Serving Human Needs" [4]
Keywords: agenda; human-computer; interaction; research

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

It’s okay to be skinny, if your friends are fat - Maneewongvatana,S.; Mount, Dave (Center for Geometric Computing 4th Annual Workshop on Computational Geometry, 1999)
The kd-tree is a popular and simple data structure for range searching and nearest neighborsearching. Such a tree subdivides space into rectangular cells through the recursive application of some splitting rule. The choice of splitting rule affects the shape of cells and the structure of the resulting tree. It has been shown that an important element in achieving efficient query times for approximate queries is that each cell should be fat, meaning that the ratio of its longest side to shortest side (its aspect ratio) should be bounded. Subdivisions with fat cells satisfy a property called the packing constraint, which bounds the number of disjoint cells of a given size that can overlap a ball of a given radius. We consider a splitting rule called the sliding-midpoint rule. It has been shown to provide efficient search times for approximate nearest neighbor and range searching, both in practice and in terms of expected case query time. However it has not been possible to prove results about this tree because it can produce cells of unbounded aspect ratio. We show that in spite of this, the sliding-midpoint rule generates subdivisions that satisfy the packing constraint, thus explaining their good performance.

Logic and databases: a 20 year retrospective-updated in honor of Ray Reiter - Minker, Jack (Logical Foundations for Cognitive Agents: Contributions in Honor of Ray Reiter, 1999)

Machine Translation - Bel,N.; Dorr, Bonnie J; Hovy,E.; Knight,K.; Iida,H.; Boitet,C.; Maegaard,B.; Wilks,Y. (Multilingual Information Management: Current Levels and Future Abilities, 1999)

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

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.

Network service selection for distributed multimedia applications - Simon,R.; Sood,A.; Mundur, Padma (Third International Conference on Computational Intelligence and Multimedia Applications, 1999. ICCIMA '99. Proceedings, 1999)
An important question in the development of system support for distributed multimedia is the type of network service offered to applications. This paper compares two network service disciplines: weighted fair queueing (WFQ) and non-preemptive earliest deadline first (NEDF). We show that, for a broad class of high-bandwidth distributed multimedia applications, WFQ outperforms NEDF in terms of network throughput while still providing an application-adequate end-to-end service. This result holds despite the fact that NEDF offers applications far greater flexibility in terms of control over end-to-end delivery delay
Keywords: Admission control; Application software; application-adequate end-to-end service; Bandwidth; Communication system traffic control; Computer science; Delay; distributed processing; end-to-end delivery delay control; flexibility; high-bandwidth distributed multimedia applications; interactive multimedia; multimedia systems; network service selection; network throughput; nonpreemptive earliest deadline first; queueing theory; Regulators; system support; telecommunication services; Throughput; Traffic control; weighted fair queueing

Overview+ detail - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualizationReadings in information visualization, 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)

Physical data - Card,S.K.; Mackinlay,J.D.; Shneiderman, Ben (Readings in information visualization, 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

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

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

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

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

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

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

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.

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

Synthesis of embedded software from synchronous dataflow specifications - Bhattacharyya, Shuvra S.; Murthy,P. K; Lee,E. A (The Journal of VLSI Signal Processing, 1999)

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

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

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

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

Trade-offs between communication throughput and parallel time - Mansour,Y.; Nisan,N.; Vishkin, Uzi (Journal of Complexity, 1999)

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

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

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

Vision geometry VIII(Denver CO, 19-20 July 1999) - Latecki,L.J.; Melter,R.A.; Mount, Dave; Wu,A. Y (SPIE proceedings series, 1999)

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

The Workshop on Logic-Based Artificial Intelligence - Minker, Jack (AI Magazine, 1999)
The Workshop on Logic-Based Artificial Intelligence

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

Access Policies for Distributed Video-on-Demand Systems - Simon,R.; Mundur, Padma; Sood,A. (Journal of the WAS, Special Issue on Communications, 85 (2), 1998)

ANN programming manual - Mount, Dave (Deptartment of Computer Science, University of Maryland, College Park, 1998)

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

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

On the Area of Overlap of Translated Polygons - Mount, Dave; Silverman,Ruth; Wu,Angela Y. (Department of Computer Science, University of Maryland, College Park, 1998)
(Also cross-referenced as CAR-TR-699) Given two simple polygons P and Q in the plane and a translation vector t E R2, the area-oJ-overlap function of P and Q is the function Ar(t) = Area(P n (t + Q)), where t + Q denotes Q translated by t. This function has a number of applications in areas such as motion planning and object recognition. We present a number of mathematical results regarding this function. We also provide efficient algorithms for computing a representation of this function, and for tracing contour curves of constant area of o verlap.
Keywords: Technical Report

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

Computational Electromagnetism: Variational Formulations, Complementarity, Edge Elements. - Mayergoyz, Issak D (Elsevier Science & Technology, 1998)

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

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

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

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

Efficient randomized algorithms for the repeated median line estimator - Matoušek,J.; Mount, Dave; Netanyahu,N. S (Algorithmica, 1998)
The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Recently there has been a great deal of interest is robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. One problem with robust estimators is that achieving high breakdown points (near 50%) has proved to be computationally demanding. In this paper we present the best known theoretical algorithm and a practical subquadratic algorithm for computing a 50% breakdown point line estimator, the Siegel or repeated median line estimator. We first present an O(n\log n) randomized expected-time algorithm, where n is the number of given points. This algorithm relies, however, on sophisticated data structures. We also present a very simple O(n log 2 n) randomized algorithm for this problem, which uses no complex data structures. We provide empirical evidence that, for many realistic input distributions, the running time of this second algorithm is actually O(n log n) expected time.

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

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

Feature-recognition for MEMS extraction - Baidya,B.; Gupta,S.K.; Mukherjee,T. (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.

Implementing a zooming User Interface: experience building Pad++ - Bederson, Benjamin B.; Meyer,Jon (Software: Practice and Experience, 1998)
We are investigating a novel user interface paradigm based on zooming, in which users are presented with a zooming view of a huge planar information surface. We have developed a system called Pad++ to explore this approach. The implementation of Pad++ is related to real-time 3D graphics systems and to 2D windowing systems. However, the zooming nature of Pad++ requires new approaches to rendering, screen management, and spatial indexing. In this paper, we describe the design and implementation of the Pad++ engine, focusing in particular on rendering and data structure issues. Our goal is to present useful techniques that can be adopted in other real-time graphical systems, and also to discuss how 2D zooming systems differ from other graphical systems. © 1998 John Wiley & Sons, Ltd.
Keywords: 3D graphics; animation; Pad++; real‐time computer graphics; User Interface Management Systems (UIMS); windowing systems; zooming User Interfaces (ZUIs)

Improved algorithms for robust point pattern matching and applications to image registration - Mount, Dave; Netanyahu,Nathan S.; LeMoigne,Jacqueline (Proceedings of the fourteenth annual symposium on Computational geometry, 1998)

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

Instrumentation and measurement - Hollingsworth, Jeffrey K; Miller, B. (The grid, 1998)

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.

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

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

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

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

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

Minimum Enclosures with Specified Angles - Mount, Dave; Silverman,Ruth (Department of Computer Science, University of Maryland, College Park, 1998)
Given a convex polygon P, an m-envelope is a convex m-sidedpolygon that contains P. Given any convex polygon P, and any sequence of m > 3 angles A = ((11Xct2X@..ckm) we consider the problem of computing the minimum area m-envelope for P whose counte rclockwise sequence of exterior angles is given by A. We show that such envelopes can be computed in O(nm log m) time. The main result on which the correctness of the algorithm rests is a flushness condition stating that for any locally minimum enclosure with specified angles, one of its sides must be collinear with one of the sides of P. (Also cross-referenced as CAR-TR-701)
Keywords: Technical Report

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

An optimal algorithm for approximate nearest neighbor searching fixed dimensions - Arya,Sunil; Mount, Dave; Netanyahu,Nathan S.; Silverman,Ruth; Wu,Angela Y. (Journal of the ACM (JACM), 1998)
Consider a set of S of n data points in real d-dimensional space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ Rd, is the closest point of S to q can be reported quickly. Given any positive real &egr;, data point p is a (1 +&egr;)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + &egr;) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in Rd in O(dn log n) time and O(dn) space, so that given a query point q ∈ Rd, and &egr; > 0, a (1 + &egr;)-approximate nearest neighbor of q can be computed in O(cd, &egr; log n) time, where cd,&egr;≤d 1 + 6d/e;d is a factor depending only on dimension and &egr;. In general, we show that given an integer k ≥ 1, (1 + &egr;)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n) time.
Keywords: Approximation algorithms; Box-decomposition trees; closet-point queries; nearest neighbor searching; post-office problem; priority search

An overview of cooperative answering in databases - Minker, Jack (Flexible Query Answering Systems, 1998)
The field of cooperative answering goes back to work started by Joshi and Webber [12] in natural language processing in the early 1980s at the University of Pennsylvania. The work was applied to databases and information systems at the University of Pennsylvania by Kaplan [14, 15] and Mays [17]. Other early work at the University of Pennsylvania and at other universities is discussed in [25, 13, 26, 16, 18, 24]. Databases and knowledge base systems are often difficult to use because they do not attempt to cooperate with their users. A database or a knowledge base query system provides literal answers to queries posed to them. Such answers to queries may not always be the best answers. Instead, an answer with extra or alternative information may be more useful and less misleading to a user.This lecture surveys foundational work that has been done toward developing database and knowledge base systems with the ability to exhibit cooperative behavior. In the 1970s, Grice [11] proposed maxims of cooperative conversation. These maxims provide the starting point for the field of cooperative answering.

Performance measurement using low perturbation and high precision hardware assists - Mink, A.; Salamon, W.; Hollingsworth, Jeffrey K; Arunachalam, R. (, The 19th IEEE Real-Time Systems Symposium, 1998. Proceedings, 1998)
We present the design and implementation of MultiKron PCI, a hardware performance monitor that can be plugged into any computer with a free PCI bus slot. The monitor provides a series of high-resolution timers, and the ability to monitor the utilization of the PCI bus. We also demonstrate how the monitor can be integrated with online performance monitoring tools such as the Paradyn parallel performance measurement tools to improve the overhead of key timer operations by a factor of 25. In addition, we present a series of case studies using the MultiKron hardware performance monitor to measure and tune high-performance parallel completing applications. By using the monitor, we were able to find and correct a performance bug in a popular implementation of the MPI message passing library that caused some communication primitives to run at one half their potential speed
Keywords: Clocks; Computerized monitoring; Counting circuits; Debugging; Hardware; hardware performance monitor; high precision hardware assists; low perturbation; measurement; MPI message passing library; MultiKron hardware performance monitor; MultiKron PCI; NIST; online performance monitoring tools; Paradyn parallel performance measurement tools; PCI bus slot; performance bug; performance evaluation; performance measurement; program debugging; program testing; real-time systems; Runtime; Timing

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

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

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

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

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

A study of large object spaces - Hicks, Michael W.; Hornof,Luke; Moore,Jonathan T.; Nettles,Scott M. (Proceedings of the 1st international symposium on Memory management, 1998)
This paper examines the design space for copying garbage collectors (GCs) in which "large objects" are managed in a separate, non-copy-collected space. We focus on two main issues:1. how to set the policy for classifying objects as "large"2. how to manage the large object spaceWe explore these issues experimentally using the Oscar GC testbed. In particular, we vary the threshold size of large objects and also whether the objects may contain pointers. Furthermore, we compare the performance of treadmill collection to that of mark-and-sweep collection for managing the large object space.We find that for some heaps there is a minimum cutoff size below which adding objects to the large object space does not result in a performance improvement, while for others no such cutoff exists. In general, including pointer-containing objects in the large object space seems beneficial. Finally, the exact method used to collect the large object space does not significantly influence overall performance.

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

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

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

Threshold-based admission control for multi-class video-on-demand systems - Mundur, Padma; Sood,A.; Simon,R. (Performance, Computing and Communications, 1998. IPCCC '98., IEEE International, 1998)
The next generation of distributed digital video-on-demand (VoD) systems will use admission control tests to ensure that users receive predictable and guaranteed service. If the system cannot support a new request then that request is blocked This paper presents an analytical model to evaluate unified admission control strategies for distributed VoD systems with multiple video classes. We prove that there exists a computationally efficient technique to determine the blocking probabilities for newly arriving requests. Through numerical analysis we show the effect of different admission control policies on overall system blocking rates
Keywords: Admission control; admission control tests; analytical model; Analytical models; blocking probabilities; buffer storage; Computer architecture; distributed digital VoD systems; File servers; guaranteed service; High-speed networks; interactive video; Motion pictures; multi-class video-on-demand systems; multimedia systems; Network servers; newly arriving requests; numerical analysis; Predictive models; probability; recursive algorithm; system blocking rates; telecommunication congestion control; threshold-based admission control; unified admission control

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

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

The Video Yardstick - Brodský,Tomáš; Fermüller, Cornelia; Aloimonos, J. (Modelling and Motion Capture Techniques for Virtual EnvironmentsModelling and Motion Capture Techniques for Virtual Environments, 1998)
Given uncalibrated video sequences, how can we recover rich descriptions of the scene content, beyond two-dimensional (2D) measurements such as color/texture or motion fields — descriptions of shape and three-dimensional (3D) motion? This is the well known structure from motion (SFM) problem. Up to now, SFM algorithms proceeded in two well defined steps, where the first and most important step is recovering the rigid transformation between two views, and the subsequent step is using this transformation to compute the structure of the scene in view. This paper introduces a novel approach to structure from motion in which both steps are accomplished in a synergistic manner. It deals with the classical structure from motion problem considering a calibrated camera as well as the extension to an uncalibrated optical device. Existing approaches to estimation of the viewing geometry are mostly based on the use of optic flow, which, however, poses a problem at the locations of depth discontinuities. If we knew where depth discontinuities were, we could (using a multitude of approaches based on smoothness constraints) accurately estimate flow values for image patches corresponding to smooth scene patches; but to know the discontinuities requires solving the structure from motion problem first. In the past this dilemma has been addressed by improving the estimation of flow through sophisticated optimization techniques, whose performance often depends on the scene in view. In this paper we follow a different approach. We directly utilize the image derivatives and employ constraints which involve the 3D motion and shape of the scene, leading to a geometric and statistical estimation problem. The main idea is based on the interaction between 3D motion and shape which allows us to estimate the 3D motion while at the same time segmenting the scene. If we use a wrong 3D motion estimate to compute depth, we obtain a distorted version of the depth function. The distortion, however, is such that the worse the motion estimate, the more likely we are to obtain depth estimates that are locally unsmooth, i.e., they vary more than the correct ones. Since local variability of depth is due either to the existence of a discontinuity or to a wrong 3D motion estimate, being able to differentiate between these two cases provides the correct motion, which yields the “smoothest” estimated depth as well as the image locations of scene discontinuities. We analyze the new constraints introduced by our approach and show their relationship to the minimization of the epipolar constraint, which becomes a special case of our theory. Finally, we present a number of experimental results with real image sequences indicating the robustness of our method and the improvement over traditional methods. The resulting system is a video yardstick that can be applied to any video sequence to recover first the calibration parameters of the camera that captured the video and, subsequently, the structure of the scene.

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

2-D MOSFET modeling including surface effects and impact ionization by self-consistent solution of the Boltzmann, Poisson, and hole-continuity equations - Liang,Wenchao; Goldsman,N.; Mayergoyz, Issak D; Oldiges,P.J. (Electron Devices, IEEE Transactions on, 1997)
We present a new two-dimensional (2-D) MOSFET simulation method achieved by directly solving the Boltzmann transport equation for electrons, the hole-current continuity equation, and the Poisson equation self-consistently. The spherical harmonic method is used for the solution of the Boltzmann equation. The solution directly gives the electron distribution function, electrostatic potential, and the hole concentration for the entire 2-D MOSFET. Average quantities such as electron concentration and electron temperature are obtained directly from the integration of the distribution function. The collision integral is formulated to arbitrarily high spherical harmonic order, and new collision terms are included that incorporate effects of surface scattering and electron-hole pair recombination/generation. I-V characteristics, which agree with experiment, are calculated directly from the distribution function for an LDD submicron MOSFET. Electron-hole pair generation due to impact ionization is also included by direct application of the collision integral. The calculations are efficient enough for day-to-day engineering design on workstation-type computers
Keywords: 2D; characteristics; LDD; concentration; electron; concentration; hole-continuity; density; electron-hole; density; impact; device; distribution; effects; surface; equation; collision; equation; I-V; equation; MOSFET; electron; equations; impact; equations; semiconductor; function; electron; generation; electron-hole; harmonic; integral; electron; ionisation; integral; ionization; self-consistent; method; Boltzmann; method; surface; modeling; Boltzmann; models; surface; MOSFET; MOSFET; Poisson; pair; potential; hole; recombination; electrostatic; recombination; hole; scattering; scattering; two-dimensional; simulation; solution; spherical; submicron; temperature; electron-hole; transport

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