bluuebunny/crossref_metadata_2025 huggingface dataset:
Analysis of retrieval performance for records and objects using optical disk technology
Authors: Christodoulakis Stavros
Published: July 2002

In this paper we examine the problem of object and record retrieval from optical disks. General objects (such as images, documents, etc.) may be long and their length may have high variance. We assume that all the components of an object are stored consecutively in storage to speed-up retrieval performance. We first present an optical disk model and an optimal schedule for retrieval of records and objects which qualify in a single query on a file stored on an optical disk device. We then provide
exact
and
approximate
analytic results for evaluating the retrieval performance for objects from an optical disk. The analysis provides some basic analytic tools for studying the performance of various file and database organizations for optical disks. The results involve probability distribution of block accesses, probability distributions of span accesses, and probability distribution of seek times. Record retrieval is an important special case. This analysis differs from similar ones in database environments in the following respects: (1) the large size and large variance of the size of objects; (2) crossing of track boundaries by objects; (3) the capability for span access that optical disks provide (e.g., when the optical assembly is located in a given position, information can be read from a number of consecutive tracks (span) with a small additional cost).
From VHDL to efficient and first-time-right designs
Authors: Middelhoek Peter F. A. , Rajan Sreeranga P.
Published: July 2002

In this article we provide a practical transformational approach to the synthesis of correct synchronous digital hardware designs from high-level specifications. We do this while taking into account the complete life cycle of a design from early prototype to full custom implementation. Besides time-to-market, both flexibility with respect to target architecture and efficiency issues are addressed by the methodology. The utilization of user-selected behavior-preserving transformation steps ensures first-time-right design while exploiting the experience, flexibility, and creativity of the designer.

To ensure that design transformations are indeed behavior-preserving a novel mechanized approach to the specification and verification of design transformations on control data flow graphs which is independent of a specific behavioral model or graph size has been developed.

As a demonstration of an industrial application we use a video processing algorithm needed for the conversion from a line-interlaced to progressively scanned video format. Both a video signal processor-based prototype implementation as well as a very efficient full custom implementation are developed starting from a single high-level behavioral specification of the algorithm in VHDL. Results are compared with those previously obtained using different tools and methodologies.
How to share concurrent wait-free variables
Authors: Li Ming , Tromp John , Vitányi Paul M. B.
Published: July 2002

Sharing data between multiple asynchronous users—each of which can atomically read and write the data—is a feature that may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of ann-user atomic variable directly from single-writer, single-reader atomic variables usesO(n)control bits andO(n)accesses per Read/Write running inO(1)parallel time.
Event propagation conditions in circuit delay computation
Authors: Yalcin Hakan , Hayes John P.
Published: July 2002

Accurate and efficient computation of delays is a central problem in computer-aided design of complex VLSI circuits. Delays are determined by events (signal transitions) propagated from the inputs of a circuit to its outputs, so precise characterization of event propagation is required for accurate delay computation. Although many different propagation conditions (PCs) have been proposed for delay computation, their properties and relationships have been far from clear. We present a systematic analysis of delay computation based on a series of waveform models that capture signal behavior rigorously at different levels of details. The most general model, called the exact of W0 model, specifies each event occurring in a circuit signal. A novel method is presented that generates approximate waveforms by progressively eliminating signal values from the exact model. For each waveform model, we drive the PCs that correctly capture the requirements under which an event propagates along a path. The waveform models and their PCs are shown to form a well-defined hierarchy, which provides a means to trade accuracy for computational effort. The relationships among the derived PCs and existing ones are analyzed in depth. It is proven that though many PCs, such as the popular floating mode condition, produce a correct upper bound on the circuit delay, they can fail to recognize event propagation in some instances. This analysis further enables us to derive new and useful PCs. We describe such a PC, called safe static. Experimental results demonstrate that safe static provides an excellent accuracy/efficiency tradeoff.
Formal verification of complex coherence protocols using symbolic state models
Authors: Pong Fong , Dubois Michel
Published: July 2002

Directory-based coherence protocols in shared-memory multiprocessors are so complex that verification techniques based on automated procedures are required to establish their correctness. State enumeration approaches are well-suited to the verification of cache protocols but they face the problem of state space explosion, leading to unacceptable verification time and memory consumption even for small system configurations. One way to manage this complexity and make the verification feasible is to map the system model to verify onto a symbolic state model (SSM). Since the number of symbolic states is considerably less than the number of system states, an exhaustive state search becomes possible, even for large-scale sytems and complex protocols.

In this paper, we develop the concepts and notations to verifiy some properties of a directory-based protocol designed for non-FIFO interconnection networks. We compare the verification of the protocol with SSM and with the Stanford Mur φ, a verification tool enumerating system states. We show that SSM is much more efficient in terms of verification time and memory consumption and therefore holds that promise of verifying much more complex protocols. A unique feature of SSM is that it verifies protocols for any system size and therefore provides reliable verification results in one run of the tool.
Object identity as a query language primitive
Authors: Abiteboul Serge , Kanellakis Paris C.
Published: July 2002

We demonstrate the power of object identities (oids) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. Our main contribution is the operational part of the data model, the query language IQL, which uses oids for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets, and (3) to express any computable database query. IQL can be type checked, can be evaluated bottom-up, and naturally generalizes most popular rule-based languages. The model can also be extended to incorporate type inheritance, without changes to IQL. Finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinte trees and whose operational part is IQL.
The automatic generation of sparse primitives
Authors: Bik Aart J. C. , Brinkhaus Peter J. H. , Knijnenburg Peter M. W. , Wijshoff Harry A. G.
Published: July 2002

Primitives in mathematical software are usually written and optimized by hand. With the implementation of a “sparse compiler” that is capable of automatically converting a dense program into sparse code, however, a completely different approach to the generation of sparse primitives can be taken. A
dense
implementation of a particular primitive is supplied to the sparse compiler, after which it can be converted into many different
sparse
versions of this primitive. Each version is specifically tailored to a class of sparse matrices having a specific nonzero structure. In this article, we discuss some of our experiences with this new approach.
An access control model supporting periodicity constraints and temporal reasoning
Authors: Bertino Elisa , Bettini Claudio , Ferrari Elena , Samarati Pierangela
Published: July 2002

Access control models, such as the ones supported by commercial DBMSs, are not yet able to fully meet many application needs. An important requirement derives from the temporal dimension that permissions have in many real-world situations. Permissions are often limited in time or may hold only for specific periods of time. In this article, we present an access control model in which periodic temporal intervals are associated with authorizations. An authorization is automatically granted in the specified intervals and revoked when such intervals expire. Deductive temporal rules with periodicity and order constraints are provided to derive new authorizations based on the presence or absence of other authorizations in specific periods of time. We provide a solution to the problem of ensuring the uniqueness of the global set of valid authorizations derivable at each instant, and we propose an algorithm to compute this set. Moreover, we address issues related to the efficiency of access control by adopting a materialization approach. The resulting model provides a high degree of flexibility and supports the specification of several protection requirements that cannot be expressed in traditional access control models.
Checking safety properties using compositional reachability analysis
Authors: Cheung Shing Chi , Kramer Jeff
Published: July 2002

The software architecture of a distributed program can be represented by a hierarchical composition of subsystems, with interacting processes at the leaves of the hierarchy. Compositional reachability analysis (CRA) is a promising state reduction technique which can be automated and used in stages to derive the overall behavior of a distributed program based on its architecture. CRA is particularly suitable for the analysis of programs that are subject to evolutionary change. When a program evolves, only the behaviors of those subsystems affected by the change need be reevaluated. The technique however has a limitation. The properties available for analysis are constrained by the set of actions that remain globally observable. Properties involving actions encapsulated by subsystems may therefore not be analyzed. In this article, we enhance the CRA technique to check safety properties which may contain actions that are not globally observable. To achieve this, the state machine model is augmented with a special trap state labeled as π. We propose a scheme to transform, in stages, a property that involves hidden actions to one that involves only globally observable actions. The enhanced technique also includes a mechanism aiming at reducing the debugging effort. The technique is illustrated using a gas station system example.
Footprints in the cache
Authors: Thiebaut Dominique , Stone Harold S.
Published: July 2002

This paper develops an analytical model for cache-reload transients and compares the model to observations based on several address traces. The cache-reload transient is the set of cache misses that occur when a process is reinitiated after being suspended temporarily. For example, an interrupt program that runs periodically experiences a reload transient at each initiation. The reload transient depends on the cache size and on the sizes of the footprints in the cache of the competing programs, where a program footprint is defined to be the set of lines in the cache in active use by the program. The model shows that the size of the transient is related to the normal distribution function. A simulation based on program-address traces shows excellent agreement between the model and the observations.
“Is this document relevant?…probably”
Authors: Crestani Fabio , Lalmas Mounia , Van Rijsbergen Cornelis J. , Campbell Iain
Published: July 2002

This article surveys probablistic approaches to modeling information retrieval. The basic concepts of probabilistic approaches to information retrieval are outlined and the principles and assumptions upon which the approaches are based are presented. The various models proposed in the development of IR are described, classified, and compared using a common formalism. New approaches that constitute the basis of future research are described.
Fully dynamic planarity testing with applications
Authors: Galil Zvi , Italiano Giuseppe F. , Sarnak Neil
Published: July 2002

This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and proves many structural properties of certificates in planar graphs. As an application of our compressed certificates, we develop efficient dynamic planar algorithms. In particular, we consider the following three operations on a planar graph
G
: (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in
O
(
n
2/3
) time, where
n
is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time, and it affirmatively answers a question posed in Epstein et al. [1992]. We use our compressed certificates for biconnectivity and triconnectivity to maintain the biconnected and triconnected components of a dynamic planar graph. The time bounds are the same:
O
(
n
2/3
) worst-case time per edge deletion,
O
(
n
2/3
) amortized time per edge insertion, and
O
(
n
2/3
) amortized time per edge insertion, and
O
(
n
2/3
)worst-case time to check whether two vertices are either biconnected or triconnected.
Modeling mobile IP in mobile UNITY
Authors: McCann Peter J. , Roman Gruia-Catalin
Published: July 2002

With recent advances in wireless communication technology, mobile computing is an increasingly important area of research. A mobile system is one where independently executing components may migrate through some space during the course of the computation, and where the pattern of connectivity among the components changes as they move in and out of proximity. Mobile UNITY is a notation and proof logic for specifying and reasoning about mobile systems. In this article it is argued that Mobile UNITY contributes to the modular development of system specifications because of the declarative fashion in which coordination among components is specified. The packet-fowarding mechanism at the core of the Mobile IP protocol for routing to mobile hosts is taken as an example. A Mobile UNITY model of packet forwarding and the mobile system in which it must operate is developed. Proofs of correctness properties, including important real-time properties, are outlined, and the role of formal verification in the development of protocols such as Mobile IP is discussed.
Algorithm 792
Authors: Renka Robert J. , Brown Ron
Published: July 2002

We present results of accuracy tests on scattered-data fitting methods that have been published as ACM algorithms. The algorithms include seven triangulation-based methods and three modified Shepard methods, two of which are new algorithms. Our purpose is twofold: to guide potential users in the selection of an appropriate algorithm and to provide a test suite for assessing the accuracy of new methods (or existing methods that are not included in this survey). Our test suite consists of five sets of nodes, with nodes counts ranging from 25 to 100, and 10 test functions. These are made available in the form of three Fortran subroutines: TESTDT returns one of the node sets; TSTFN1 returns a value and, optionally, a gradient value, of one of the test funciton; and TSTFN2 returns a value, first partials, and second partial derivatives of one of the test functions.
A software model and specification language for non-WIMP user interfaces
Authors: Jacob Robert J. K. , Deligiannidis Leonidas , Morrison Stephen
Published: July 2002

We present a software model and language for describing and programming the fine-grained aspects of interaction in a non-WIMP user interface, such as a virtual environment. Our approach is based on our view that the essence of a non-WIMP dialogue is a set of continuous relationships—most of which are temporary. The model combines a data-flow or constraint-like component for the continuous relationships with an event-based component for discrete interactions, which can enable or diable individual continuous relationships. To demonstrate our approach, we present the PMIW user interface management system for non-WIMP interactions, a set of examples running under it, a visual editor for our user interface description language, and a discussion of our implemantation and our restricted use of constraints for a performance-driven interactive situation. Our goal is to provide a model and language that captures the formal structure of non-WIMP interactions in the way that various previous techniques have captured command-based, textual, and event-based styles and to suggest that using it need and not compromise real-time performance.
Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback
Authors: Diniz Pedro C. , Rinard Martin C.
Published: July 2002

This article presents dynamic feedback, a technique that enables
computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generted code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.
A new local basis for designing with tensioned splines
Authors: Cohen Elaine
Published: July 2002

Recently there has been a great deal of interest in the use of “tension” parameters to augment control mesh vertices as design handles for piecewise polynomials. A particular local cubic basis called B-splines, which has been termed a “generalization of B-splines, v has been proposed as an appropriate basis. These functions are defined only for floating knot sequences. This paper uses the known property of B-splines that with appropriate knot vectors span what are called here spaces of tensioned splines, and that particular combinations of them, called LT-splines, form bases for the spaces of tensioned splines. In addition, this paper shows that these new proposed bases have the variation diminishing property, the convex hull property, and straightforward knot insertion algorithms, and that both curves and individual basis functions can be easily computed. Sometimes it is desirable to interpolate points and also use these tension parameters, so interpolation methods using the LT-spline bases are presented. Finally, the above properties are established for uniform and nonuniform knot vectors, open and floating end conditions, and homogeneous and nonhomogeneous tension parameter pairs.
A weighted voting algorithm for replicated directories
Authors: Bloch Joshua J. , Daniels Dean S. , Spector Alfred Z.
Published: July 2002

Weighted voting is used as the basis for a replication technique for directories. This technique affords arbitrarily high data availability as well as high concurrency. Efficient algorithms are presented for all of the standard directory operations. A structural property of the replicated directory that permits the construction of an efficient algorithm for deletion is proven. Simulation results are presented and the system is modeled and analyzed. The analysis agrees well with the simulation, and the space and time performance are shown to be good for all configurations of the system.
Asymptotic expansions of the sojourn time distribution functions of jobs in closed, product-form queuing networks
Authors: McKenna James
Published: July 2002

Striking progress has been made recently in obtaining expressions for the sojourn time distribution function (STDF) of a job at a
c
-server, first-come, first-serve (FCFS) center in a closed, product-form queuing network. These results have more recently been extended, and expressions have been obtained for the joint distribution function (DF) of the sojourn times of a job at a sequence of single-server, FCFS centers lying on an “overtake-free” path. However, these formulas present considerable computational problems in the case of large, closed queuing networks. In this paper, asymptotic techniques developed by Mitra and McKenna for the calculation of the partition function of large, product-form closed queuing networks are applied to the sojourn time problem. Asymptotic expansions are obtained for the STDF of a job at
c
-server, FCFS center in closed, product-form queuing networks. Similar expansions are obtained for the joint DF of the sojourn times of a job at a sequence of single server, FCFS centers lying on an “overtake-free” path. In addition, integral expressions are obtained for the STDF of a job at a single server, FCPS center in a closed, product-form queuing network in which all the centers are load independent. These integral expressions also yield useful asymptotic expansions. Finally, integral expressions are also obtained for the joint DF of the sojourn times of a job at the centers of an “overtake-free” path in such a network.
On database systems development through logic
Authors: Dahl Veronica
Published: July 2002

The use of logic as a single tool for formalizing and implementing different aspects of database systems in a uniform manner is discussed. The discussion focuses on relational databases with deductive capabilities and very high-level querying and defining features. The computational interpretation of logic is briefly reviewed, and then several pros and cons concerning the description of data, programs, queries, and language parser in terms of logic programs are examined. The inadequacies are discussed, and it is shown that they can be overcome by the introduction of convenient extensions into logic programming. Finally, an experimental database query system with a natural language front end, implemented in PROLOG, is presented as an illustration of these concepts. A description of the latter from the user's point of view and a sample consultation session in Spanish are included.
Propeties of storage hierarchy systems with multiple page sizes and redundant data
Authors: Lam Chat-Yu , Madnick Stuart E.
Published: July 2002

The need for high performance, highly reliable storage for very large on-line databases, coupled with rapid advances in storage device technology, has made the study of generalized storage hierarchies an important area of research.

This paper analyzes properties of a data storage hierarchy system specifically designed for handling very large on-line databases. To attain high performance and high reliability, the data storage hierarchy makes use of multiple page sizes in different storage levels and maintains multiple copies of the same information across the storage levels. Such a storage hierarchy system is currently being designed as part of the INFOPLEX database computer project. Previous studies of storage hierarchies have primarily focused on virtual memories for program storage and hierarchies with a single page size across all storage levels and/or a single copy of information in the hierarchy.

In the INFOPLEX design, extensions to the least recently used (LRU) algorithm are used to manage the storage levels. The read-through technique is used to initially load a referenced page of the appropriate size into all storage levels above the one in which the page is found. Since each storage level is viewed as an extension of the immediate higher level, an overflow page from level
i
is always placed in level
i
+ 1. Important properties of these algorithms are derived. It is shown that depending on the types of algorithms used and the relative sizes of the storage levels, it is not always possible to guarantee that the contents of a given storage level
i
is always a superset of the contents of its immediate higher storage level
i
- 1. The necessary and sufficient conditions for this property to hold are identified and proved. Furthermore, it is possible that increasing the size of intermediate storage levels may actually increase the number of references to lower storage levels, resulting in reduced performance. Conditions necessary to avoid such an anomaly are also identified and proved.
The entity-relationship model—toward a unified view of data
Authors: Chen Peter Pin-Shan
Published: July 2002

A data model, called the entity-relationship model, is proposed. This model incorporates some of the important semantic information about the real world. A special diagrammatic technique is introduced as a tool for database design. An example of database design and description using the model and the diagrammatic technique is given. Some implications for data integrity, information retrieval, and data manipulation are discussed.

The entity-relationship model can be used as a basis for unification of different views of data: the network model, the relational model, and the entity set model. Semantic ambiguities in these models are analyzed. Possible ways to derive their views of data from the entity-relationship model are presented.
A Uniform Random Number Generator Based on the Combination of Two Congruential Generators
Authors: Westlake W. J.
Published: July 2002

A method of generating pseudo-random uniform numbers based on the combination of two congruential generators is described. It retains two of the desirable features of congruential generators, namely, the long cycle and the case of implementation on a digital computer. Furthermore, unlike the method of combining congruential generators recently proposed by MacLaren and Marsaglia, it does not require the retention in computer memory of a table of generated numbers. The generator gave completely satisfactory results on a fairly stringent series of statistical tests.
Application of Parallel Processing to Numerical Weather Prediction
Authors: Carroll A. B. , Wetherald R. T.
Published: July 2002

The purpose of this study is to illustrate the application of a parallel network processing computing system to an important class of problems in hydrodynamics. The computing system selected for this study is a prototype of the SOLOMON parallel processing system (cited as SOLOMON II) which was developed at the Westinghouse Defense and Space Center, Baltimore, Maryland.

Emphasis is placed on the problem of numerical weather prediction mainly because of the large data storage and manipulation required, plus the extensive numerical analysis that is involved. The mathematical basis for numerical weather forecasting lies in the principles of conservation of mass, momentum, and energy. From these principles, research meteorologists have devised equations which express the physical laws governing the atmosphere. These basic equations are nonlinear partial differential equations and are well suited for solution by the SOLOMON II system. The computational method is to replace the region of interest by a grid system and replace the continuous equations by their finite difference approximations. In this representation, the programmer can take maximum advantage of mode control, neighboring connections, variable geometry, and simultaneous operation of a network of processing elements.

Another topic discussed is the numerical solution of elliptic partial differential equations by the parallel processing network. It is felt by the authors that a parallel processing system of this type will offer a significant increase in computational speed over that of a sequentially organized computing system in the field of fluid dynamics as well as in other scientific fields.
On Decompositions of Regular Events
Authors: Brzozowski J. A. , Cohen Rina
Published: July 2002

Decompositions of regular events into star events, i.e. events of the form
W
=
V
*, are studied. Mathematically, the structure of a star event is that of a monoid. First it is shown that every regular event contains a finite number of maximal star events, which are shown to be regular and can be effectively computed. Necessary and sufficient conditions for a regular event to be the union of its maximal star events are found. Next, star events are factored out from arbitrary events, yielding the form
W
-
V
*
T
. For each
W
there exists a unique largest
V
* and a unique smallest
T
; an algorithm for finding suitable regular expressions for
V
and
T
is developed. Finally, an open problem of Paz and Peleg is answered: Every regular event is decomposable as a finite product of star events and prime events.
Toward a Theory of Enumerations
Authors: Young Paul R.
Published: July 2002

An attempt is made to show that there is much work in pure recursion theory which implicitly treats computational complexity of algorithmic devices which enumerate sets. The emphasis is on obtaining results which are independent of the particular model one uses for the enumeration technique and which can be obtained easily from known results and known proofs in pure recursion theory.

First, it is shown that it is usually impossible to define operators on sets by examining the structure of the enumerating devices unless the same operator can be defined merely by examining the behavior of the devices. However, an example is given of an operator which can be defined by examining the structure but which cannot be obtained merely by examining the behavior.

Next, an example is given of a set which cannot be enumerated quickly because there is no way of quickly obtaining large parts of it (perhaps with extraneous elements). By way of contrast, sets are constructed whose elements can be obtained rapidly in conjunction with the enumeration of a second set, but which themselves cannot be enumerated rapidly because there is no easy way to eliminate the members of the second set.

Finally, it is shown how some of the elementary parts of the Hartmanis-Stearns theory can be obtained in a general setting.
Bernstein-Bézier Methods for the Computer-Aided Design of Free-Form Curves and Surfaces
Authors: Gordon William J. , Riesenfeld Richard F.
Published: July 2002

The
m
th degree Bernstein polynomial approximation to a function ƒ defined over [0, 1] is Σ

m

μ

=0 ƒ(
μ
/
m
)

φ
μ

(
s
), where the weights

φ
μ

(
s
) are binomial density functions. The Bernstein approximations inherit many of the
global
characteristics of ƒ, like monotonicity and convexity, and they always are at least as
“smooth”
as ƒ, where “smooth” refers to the number of undulations, the total variation, and the differentiability class of ƒ.

Historically, their relatively slow convergence in the L
∞
-norm has tended to discourage their use in practical applications.

However, in a large class of problems the smoothness of an approximating function is of greater importance than closeness of fit. This is especially true in connection with problems of computer-aided
geometric design
of curves and surfaces where aesthetic criteria and the
intrinsic properties of shape
are major considerations. For this latter class of problems, P. Bézier of Renault has successfully exploited the properties of parametric Bernstein polynomials. The purpose of this paper is to analyze the Bézier techniques and to explore various extensions and generalizations. In a sequel, the authors consider the extension of the results contained herein to free-form curve and surface design using polynomial
splines
. These B-spline methods have several advantages over the techniques described in the present paper.
A General Model for the Performance of Disk Systems
Authors: Wilhelm Neil C.
Published: July 2002

The performance of a disk system is often measured in terms of the length of the waiting line or queue of requests for each of the system's spindles. Thus it is natural to formulate and analyze queueing models of disk systems. While most disk systems have certain characteristics, such as channel interference and concurrent seeks, in common, previous analyses have always been begun from scratch, without exploiting this commonality. We introduce a general queueing model for disk systems, which incorporates the characteristics common to most disk systems, and use it in the approximate analyses of models of the IBM 2314 and 3330 disk systems. Comparisons with simulation statistics show that the approximations made are very good over a wide range of arrival rates and system parameters. We also show how to use the analytic results to investigate performance differences between devices.
ARIADNE: pattern-directed inference and hierarchical abstraction in protein structure recognition
Authors: Lathrop Richard H. , Webster Teresa A. , Smith Temple F.
Published: July 2002

The macro-molecular structural conformations of proteins exhibit higher order regularities whose recognition is complicated by many factors. ARIADNE searches for similarities between structural descriptors and hypothesized protein structure at levels more abstract than the primary sequence.
Algorithm 798
Authors: Berry Michael W. , Minser Karen S.
Published: July 2002

A new implementation of the Modified Quadratic Shepard Method for the interpolation of scattered data is presented. QSHEP5D is a C++ translation of the original Fortran 77 program QSHEP3D developed by Renka (for 2D and 3D interpolation) which has been upgraded for 5D interpolation. This software development was motivated by the need for interpolated 5D hypervolumes of environmental response variables produced by forest growth and production models.
Multiway FPGA partitioning by fully exploiting design hierarchy
Authors: Fang Wen-Jong , Wu Allen C.-H.
Published: July 2002

In this paper, we present a new integrated synthesis and partitioning method for multiple-FPGA applications. Our approach bridges the gap between HDL synthesis and physical partitioning by fully exploiting the design hierarchy. We propose a novel multiple-FPGA synthesis and partitioning method which is performed in three phases: (1) fine-grained synthesis, (2) functional-based clustering, and (3) hierarchical set-covering partitioning. This method first synthesizes a design specification in a fine-grained way so that functional clusters can be preserved based on the structural nature of the design specification. Then, it applies a hierarchical set-covering partitioning method to form the final FPGA partitions. Experimental results on a number of benchmarks and industrial designs demonstrate that I/O limits are the bottleneck for CLB utilization when applying a traditional multiple-FPGA synthesis method on flattened netlists. In contrast, by fully exploiting the design structural hierarchy during the multiple-FPGA partitioning, our proposed method produces fewer FPGA partitions with higher CLB and lower I/O-pin utilizations.
Data clustering
Authors: Jain A. K. , Murty M. N. , Flynn P. J.
Published: July 2002

Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appeal and usefulness as one of the steps in exploratory data analysis. However, clustering is a difficult problem combinatorially, and differences in assumptions and contexts in different communities has made the transfer of useful generic concepts and methodologies slow to occur. This paper presents an overview of pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval.
Variations on UNIX for parallel-processing computers
Authors: Russell Channing H. , Waterman Pamela J.
Published: July 2002

Porting a familiar UNIX environment to today's parallel-processing computers is challenging, but options abound.
Past, present, and future of user interface software tools
Authors: Myers Brad , Hudson Scott E. , Pausch Randy
Published: July 2002

A user interface software tool helps developers design and implement the user interface. Research on past tools has had enormous impact on today's developers—virtually all applications today are built using some form of user interface tool. In this article, we consider cases of both success and failure in past user interface tools. From these cases we extract a set of themes which can serve as lessons for future work. Using these themes, past tools can be characterized by what aspects of the user interface they addressed, their threshold and ceiling, what path of least resistance they offer, how predictable they are to use, and whether they addressed a target that became irrelevant. We believe the lessons of these past themes are particularly important now, because increasingly rapid technological changes are likely to significantly change user interfaces. We are at the dawn of an era where user interfaces are about to break out of the “desktop” box where they have been stuck for the past 15 years. The next millenium will open with an increasing diversity of user interface on an increasing diversity of computerized devices. These devices include hand-held personal digital assistants (PDAs), cell phones, pages, computerized pens, computerized notepads, and various kinds of desk and wall size-computers, as well as devices in everyday objects (such as mounted on refridgerators, or even embedded in truck tires). The increased connectivity of computers, initially evidenced by the World Wide Web, but spreading also with technologies such as personal-area networks, will also have a profound effect on the user interface to computers. Another important force will be recognition-based user interfaces, especially speech, and camera-based vision systems. Other changes we see are an increasing need for 3D and end-user customization, programming, and scripting. All of these changes will require significant support from the underlying user interface sofware tools.
Anatomy of a compact user interface development tool
Authors: Stott Jack W. , Kottemann Jeffrey E.
Published: July 2002

Many contemporary user oriented applications require a combination of attributes from both window and forms management systems. PANES was developed as a tool to fill this niche by providing a simple, yet flexible tool for both the moderately trained, as well as the more sophisticated programmer, while allowing the development of user friendly, modeless application software.
The maximum entropy approach and probabilistic IR models
Authors: Greiff Warren R. , Ponte Jay M.
Published: July 2002

This paper takes a fresh look at modeling approaches to information retrieval that have been the basis of much of the probabilistically motivated IR research over the last 20 years. We shall adopt a subjectivist Bayesian view of probabilities and argue that classical work on probabilistic retrieval is best understood from this perspective. The main focus of the paper will be the ranking formulas corresponding to the Binary Independence Model (BIM), presented originally by Roberston and Sparck Jones [1977] and the Combination Match Model (CMM), developed shortly thereafter by Croft and Harper [1979]. We will show how these same ranking formulas can result from a probabilistic methodology commonly known as Maximum Entropy (MAXENT).
Soft timers
Authors: Aron Mohit , Druschel Peter
Published: July 2002

This paper proposes and evaluates soft timers, a new operating system facility that allows the efficient scheduling of software events at agranularity down to tens of microseconds. Soft timers can be used to avoid interrupts and reduce context switches associated with network processing, without sacrificing low communication delays. More specifically, soft timers enable transport protocols like TCP to efficiently perform rate-based clocking of packet transmissions. Experiments indicate that soft timers allow a server to employ rate-based clocking with little CPU overhead (2-6%) at high aggregate bandwidths. Soft timers can also be used to perform network polling, which eliminates network interrupts and increases the memory access locality of the network subsystem without sacrificing delay. Experiments show that this technique can improve the throughput of a Web server by up to 25%.
Cellular disco
Authors: Govil Kinshuk , Teodosiu Dan , Huang Yongqiang , Rosenblum Mendel
Published: July 2002

Despite the fact that large-scale shared-memory multiprocessors have been commercially available for several years, system software that fully utilizes all their features is still not available, mostly due to the complexity and cost of making the required changes to the operating system. A recently proposed approach, called Disco, substantially reduces this development cost by using a virtual machine monitor that laverages the existing operating system technology. In this paper we present a system called Cellular Disco that extends the Disco work to provide all the advantages of the hardware partitioning and scalable operating system approaches. We argue that Cellular Disco can achieve these benefits at only a small fraction of the development cost of modifying the operating system. Cellular Disco effectively turns a large-scale shared-memory multiprocessor into a virtual cluster that supports fault containment and heterogeneity, while avoiding operating system scalability bottlenecks. Yet at the same time, Cellular Disco preserves the benefits of a shared-memory multiprocessor by implementing dynamic, fine-grained resource sharing, and by allowing users to overcommit resources such as processors and memory. This hybrid approach requires a scalable resource manager that makes local decisions with limited information while still providing good global performance and fault containment. In this paper we describe our experience with a Cellular Disco prototype on a 32-processor SGI Origin 2000 system. We show that the execution time penalty for this approach is low, typically within 10% of the best available commercial operating system formost workloads, and that it can manage the CPU and memory resources of the machine significantly better than the hardware partitioning approach.
A lower bound on the average-case complexity of shellsort
Authors: Jiang Tao , Li Ming , Vitányi Paul
Published: July 2002

We demonstrate an Ω(
pn

1+1/
p

) lower bound on the average-case running time (uniform distribution) of
p
-pass Shellsort. This is the first nontrivial general lower bound for average-case Shellsort.
Experiment with an automatic theorem-prover having partial ordering inference rules
Authors: Slagle James R. , Norton Lewis M.
Published: July 2002

Automatic theorem-provers need to be made much more efficient. With this in mind, Slagle has shown how the axioms for partial ordering can be replaced by built-in inference rules when using a particular theorem-proving algorithm based upon hyper-resolution and paramodulation. The new rules embody the transitivity of partial orderings and the close relationship between the ⊂ and ⊆ predicates. A program has been developed using a modified version of these rules. This new theorem-prover has been found to be very powerful for solving problems involving partial orderings. This paper presents a detailed description of the program and a comprehensive account of the experiments that have been performed with it.
A hierarchical data structure for multidimensional digital images
Authors: Yau Mann-May , Srihari Sargur N.
Published: July 2002

A tree data structure for representing multidimensional digital binary images is described. The method is based on recursive subdivision of the d-dimensional space into 2
d
hyperoctants. An algorithm for constructing the tree of a d-dimensional binary image from the trees of its (d - 1 )-dimensional cross sections is given. The computational advantages of the data structure and the algorithm are demonstrated both theoretically and in application to a three-dimensional reconstruction of a human brain.
Programming pearls: Aha algorithms
Authors: Bentley Jon
Published: July 2002

The study of algorithms has much to offer the practicing programmer. After just a course or two on the subject, students take away algorithms for solving many important tasks and design techniques for attacking new problems. Advanced algorithmic tools can have a substantial impact on software systems. Next month, for instance, we'll study a system in which algorithm design helped reduce development time by 170 staff-years.

As important as such tools are, algorithms can have an impact on a more common level of programming. In his book
aha! Insight
(from which I shamelessly stole my title), Martin Gardner describes the type of contribution I have in mind: “a problem that seems difficult may have a simple, unexpected solution.” Unlike the advanced methods of the field, the
aha!
insights of algorithms don't come only after extensive study; they're available to any programmer willing to think seriously before, during, and after coding. But enough generalities, on to the problems!
Accommodating uncertainty in software design
Authors: Giddings Richard V.
Published: July 2002

Recognition that most software is domain dependent (DD) is extremely important because the most commonly used software life-cycle models are not adequate for DD software. The nature of DD software, and the need to manage its life cycle effectively, calls for a new approach to software design and the implementation of software development environments.
The EAS-E application development system
Authors: Markowitz Harry M. , Malhotra Ashok , Pazel Donald P.
Published: July 2002

EAS-E is based on the entity-attribute-set view of system description—a useful formalism for system modeling and planning even when programming is done in languages other than EAS-E.
Parallel programs
Authors: Andrews Gregory R.
Published: July 2002

Several principles are identified from work on the verification of parallel programs. Concrete examples of the ways these principles can be applied, even when formal verification is not the goal, are then described. The purpose of this paper is to demonstrate ways in which the
concepts
of program verification yield insight into the programming process, programming languages, and program properties.