bluuebunny/crossref_metadata_2025 huggingface dataset:
How to learn an unknown environment. I
Authors: Deng Xiaotie , Kameda Tiko , Papadimitriou Christos
Published: July 2002

We consider the problem faced by a robot that must explore and learn an unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map, if we had it in the beginning. The situation is complicated by the fact that the latter off-line problem (the problem of optimally verifying a map) is NP-hard. Although we show that there is no such “competitive” algorithm for general obstacle courses, we give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. We restrict ourselves to the rectilinear case, where each side of the obstacles and the room is parallel to one of the coordinates, and the robot must also move either parallel or perpendicular to the sides. (In a subsequent paper, we will discuss the extension to polygons of general shapes.)

We also discuss the off-line problem for simple rectilinear polygons and find an optimal solution (in the L
1
metric) in polynomial time, in the case where the entry and the exit are different points.
Version models for software configuration management
Authors: Conradi Reidar , Westfechtel Bernhard
Published: July 2002

After more than 20 years of research and practice in software configuration management (SCM), constructing consistent configurations of versioned software products still remains a challenge. This article focuses on the version models underlying both commercial systems and research prototypes. It provides an overview and classification of different versioning paradigms and defines and relates fundamental concepts such as revisions, variants, configurations, and changes. In particular, we focus on intensional versioning, that is, construction of versions based on configuration rules. Finally, we provide an overview of systems that have had significant impact on the development of the SCM discipline and classify them according to a detailed taxonomy.
Discovering models of software processes from event-based data
Authors: Cook Jonathan E. , Wolf Alexander L.
Published: July 2002

Many software process methods and tools presuppose the existence of a formal model of a process. Unfortunately, developing a formal model for an on-going, complex process can be difficult, costly, and error prone. This presents a practical barrier to the adoption of process technologies, which would be lowered by automated assistance in creating formal models. To this end, we have developed a data analysis technique that we term
process discovery.
Under this technique, data describing process events are first captured from an on-going process and then used to generate a formal model of the behavior of that process. In this article we describe a Markov method that we developed specifically for process discovery, as well as describe two additional methods that we adopted from other domains and augmented for our purposes. The three methods range from the purely algorithmic to the purely statistical. We compare the methods and discuss their application in an industrial case study.
A flexible authorization mechanism for relational data management systems
Authors: Bertino Elisa , Jajodia Sushil , Samarati Pierangela
Published: July 2002

In this article, we present an authorization model that can be used to express a number of discretionary access control policies for relational data management systems. The model permits both positive and negative authorizations and supports exceptions at the same time. The model is flexible in that the users can specify, for each authorization they grant, whether the authorization can allow for exceptions or whether it must be strongly obeyed. It provides authorization management for groups with exceptions at any level of the group hierarchy, and temporary suspension of authorizations. The model supports ownership together with decentralized administration of authorizations. Administrative privileges can also be restricted so that owners retain control over their tables.
Undirected single-source shortest paths with positive integer weights in linear time
Authors: Thorup Mikkel
Published: July 2002

The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph
G
with a source vertex
s
, find the shortest path from
s
to all other vertices in the graph.

Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from
s
. Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from
s
. However, we do not know how to sort in linear time.

Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.
An evaluation of retrieval effectiveness for a full-text document-retrieval system
Authors: Blair David C. , Maron M. E.
Published: July 2002

An evaluation of a large, operational full-text document-retrieval system (containing roughly 350,000 pages of text) shows the system to be retrieving less than 20 percent of the documents relevant to a particular search. The findings are discussed in terms of the theory and practice of full-text document retrieval.
A clustered search algorithm incorporating arbitrary term dependencies
Authors: Lam K. , Yu C. T.
Published: July 2002

The documents in a database are organized into clusters, where each cluster contains similar documents and a representative of these documents. A user query is compared with all the representatives of the clusters, and on the basis of such comparisons, those clusters having many
close neighbors
with respect to the query are selected for searching. This paper presents an estimation of the number of close neighbors in a cluster in relation to the given query. The estimation takes into consideration the dependencies between terms. It is demonstrated by experiments that the estimate is accurate and the time to generate the estimate is small.
Computational problems related to the design of normal form relational schemas
Authors: Beeri Catriel , Bernstein Philip A.
Published: July 2002

Problems related to functional dependencies and the algorithmic design of relational schemas are examined. Specifically, the following results are presented: (1) a tree model of derivations of functional dependencies from other functional dependencies; (2) a linear-time algorithm to test if a functional dependency is in the closure of a set of functional dependencies; (3) a quadratic-time implementation of Bernstein's third normal form schema synthesis algorithm.

Furthermore, it is shown that most interesting algorithmic questions about Boyce-Codd normal form and keys are
NP
-complete and are therefore probably not amenable to fast algorithmic solutions.
Locking granularity revisited
Authors: Ries Daniel R. , Stonebraker Michael R.
Published: July 2002

Locking granularity refers to the size and hence the number of locks used to ensure the consistency of a database during multiple concurrent updates. In an earlier simulation study we concluded that coarse granularity, such as area or file locking, is to be preferred to fine granularity such as individual page or record locking.

However, alternate assumptions than those used in the original paper can change that conclusion. First, we modified the assumptions concerning the placement of the locks on the database with respect to the accessing transactions. In the original model the locks were assumed to be well placed. Under worse case and random placement assumptions when only very small transactions access the database, fine granularity is preferable.

Second, we extended the simulation to model a lock hierarchy where large transactions use large locks and small transactions use small locks. In this scenario, again under the random and worse case lock placement assumptions, fine granularity is preferable if all transactions accessing more than 1 percent of the database use large locks.

Finally, the simulation was extended to model a “claim as needed” locking strategy together with the resultant possibility of deadlock. In the original study all locks were claimed in one atomic operation at the beginning of a transaction. The claim as needed strategy does not change the conclusions concerning the desired granularity.
The difficulty of optimum index selection
Authors: Comer Douglas
Published: July 2002

Given a file on a secondary store in which each record has several attributes, it is usually advantageous to build an index mechanism to decrease the cost of conducting transactions to the file. The problem of selecting attributes over which to index has been studied in the context of various storage structures and access assumptions. One algorithm to make an optimum index selection requires 2

k

steps in the worst case, where
k
is the number of attributes in the file. We examine the question of whether a more efficient algorithm might exist and show that even under a simple cost criterion the problem is computationally difficult in a precise sense. Our results extend directly to other related problems where the cost of the index depends on fixed values which are assigned to each attribute. Some practical implications are discussed.
A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable
Authors: Fraser W.
Published: July 2002

Methods are described for the derivation of minimax and near-minimax polynomial approximations. For minimax approximations techniques are considered for both analytically defined functions and functions defined by a table of values. For near-minimax approximations methods of determining the coefficients of the Fourier-Chebyshev expansion are first described. These consist of the rearrangement of the coefficients of a power polynomial, and also direct determination of the coefficients from the integral which defines them, or the differential equation which defines the function. Finally there is given a convenient modification of an interpolation scheme which finds coefficients of a near-minimax approximation without requiring numerical integration or the numerical solution of a system of equations.
Real-Time Definable Languages
Authors: Rosenberg Arnold L.
Published: July 2002

The closure properties of the class of languages defined by real-time, online, multi-tape Turing machines are proved. The results obtained are, for the most part, negative and, as one would expect, asymmetric. It is shown that the results remain valid for a broad class of real-time devices. Finally, the position of the class of real-time definable languages in the “classical” linguistic hierarchy is established.
An Analysis of Some Graph Theoretical Cluster Techniques
Authors: Augustson J. Gary , Minker Jack
Published: July 2002

Several graph theoretic cluster techniques aimed at the automatic generation of thesauri for information retrieval systems are explored. Experimental cluster analysis is performed on a sample corpus of 2267 documents. A term-term similarity matrix is constructed for the 3950 unique terms used to index the documents. Various threshold values,
T
, are applied to the similarity matrix to provide a series of binary threshold matrices. The corresponding graph of each binary threshold matrix is used to obtain the term clusters.

Three definitions of a cluster are analyzed: (1) the connected components of the threshold matrix; (2) the maximal complete subgraphs of the connected components of the threshold matrix; (3) clusters of the maximal complete subgraphs of the threshold matrix, as described by Gotlieb and Kumar.

Algorithms are described and analyzed for obtaining each cluster type. The algorithms are designed to be useful for large document and index collections. Two algorithms have been tested that find maximal complete subgraphs. An algorithm developed by Bierstone offers a significant time improvement over one suggested by Bonner.

For threshold levels
T
≥ 0.6, basically the same clusters are developed regardless of the cluster definition used. In such situations one need only find the connected components of the graph to develop the clusters.
Application of the Diffusion Approximation to Queueing Networks I: Equilibrium Queue Distributions
Authors: Kobayashi Hisashi
Published: July 2002

The practical value of queueing theory in engineering applications such as in computer modeling has been limited, since the interest in mathematical tractability has almost always led to an oversimplified model. The diffusion process approximation is an attempt to break away from the vogue in queueing theory.

The present paper introduces a vector-valued normal process and its diffusion equation in order to obtain an approximate solution to the joint distribution of queue lengths in a general network of queues. In this model, queueing processes of various service stations which interact with each other are approximated by a vector-valued Wiener process with some appropriate boundary conditions. Some numerical examples are presented and compared with Monte Carlo simulation results. A companion paper, Part II, discusses transient solutions via the diffusion approximation.
R
-Domination in Graphs
Authors: Slater Peter J.
Published: July 2002

The problem of finding a minimum
k
-basis of graph
G
is that of selecting as small a set
B
of vertices as possible such that every vertex of
G
is at distance
k
or less from some vertex in
B
. Cockayne, Goodman, and Hedetniemi previously developed a linear algorithm to find a minimum 1-basis (a minimum dominating set) when
G
is a tree. In this paper the
k
-basis problem is placed in a more general setting, and a linear algorithm is presented that solves the problem for any forest.
Using shape analysis to reduce finite-state models of concurrent Java programs
Authors: Corbett James C.
Published: July 2002

Finite-state verification (e.g., model checking) provides a powerful means to detect concurrency errors, which are often subtle and difficult to reproduce. Nevertheless, widespread use of this technology by developers is unlikely until tools provide automated support for extracting the required finite-state models directly from program source. Unfortunately, the dynamic features of modern languages such as Java complicate the construction of compact finite-state models for verification. In this article, we show how shape analysis, which has traditionally been used for computing alias information in optimizers, can be used to greatly reduce the size of finite-state models of concurrent Java programs by determining which heap-allocated variables are accessible only by a single thread, and which shared variables are protected by locks. We also provide several other state-space reductions based on the semantics of Java monitors. A prototype of the reductions demonstrates their effectiveness.
Shortest-substring retrieval and ranking
Authors: Clarke Charles L. A. , Cormack Gordon V.
Published: July 2002

We present a model for arbitrary passage retrieval using Boolean queries. The model is applied to the task of ranking documents, or other structural elements, in the order of their expected relevance. Features such as phrase matching, truncation, and stemming integrate naturally into the model. Properties of Boolean algebra are obeyed, and the exact-match semantics of Boolean retrieval are preserved. Simple inverted-list file structures provide an efficient implementation. Retrieval effectiveness is comparable to that of standard ranking techniques. Since global statistics are not used, the method is of particular value in distributed environments. Since ranking is based on arbitrary passages, the structural elements to be ranked may be specified at query time and do not need to be restricted to predefined elements.
Modeling and rendering waves: wave-tracing using beta-splines and reflective and refractive texture mapping.
Authors: Ts'o Pauline Y. , Barsky Brian A.
Published: July 2002

The graphical simulation of a certain subset of hydrodynamics phenomena is examined. New algorithms for both
modeling
and
rendering
these complex phenomena are presented.

The modeling algorithms deal with wave refraction in an ocean. Waves refract in much the same way as light. In both cases, the equation that controls the change in direction is Snell's law. Ocean waves are continuous but can be discretely decomposed into wave rays or
wave orthogonals
. These wave orthogonals are
wave-traced
in a manner similar to the rendering algorithm of ray-tracing. The refracted wave orthogonals are later traversed and their height contributions to the final surface are calculated using a sinusoidal shape approximation and the principle of wave superposition. The surface is then represented by
Beta-splines
, using the tension (or β2) shape parameter to easily add more complexity to the surface.

The rendering algorithms are based on the use of
texture maps
and Fresnel's law of reflection. In each algorithm, two texture maps are used to simulate
reflection
and
refraction
. Based on surface normal orientation and Fresnel's law, a weighting is calculated that determines what fractions of reflected color and refracted color are assigned to a point. These algorithms are more efficient, though less accurate, alternatives to standard ray-tracing techniques.
Algorithm 655
Authors: Elhay Sylvan , Kautsky Jaroslav
Published: July 2002

We present FORTRAN subroutines that implement the method described in [3] for the stable evaluation of the weights of interpolatory quadratures with prescribed simple or multiple knots. Given a set of knots and their multiplicities, the package generates the weights by using the zeroth moment μ
0
of
w
, the weight function in the integrand, and the (symmetric tridiagonal) Jacobi matrix
J
associated with the polynomials orthogonal on (
a, b
) with respect to
w
. There are utility routines that generate μ
0
and
J
for classical weight functions, but quadratures can be generated for any μ
0
and
J
supplied by the user. Utility routines are also provided that (1) evaluate a computed quadrature, applied to a user-supplied integrand, (2) check the polynomial order of precision of a quadrature formula, and (3) compute the knots and weights of simple Gaussian quadrature formula.
Data integration using similarity joins and a word-based information representation language
Authors: Cohen William W.
Published: July 2002

The integration of distributed, heterogeneous databases, such as those available on the World Wide Web, poses many problems. Herer we consider the problem of integrating data from sources that lack common object identifiers. A solution to this problem is proposed for databases that contain informal, natural-language “names” for objects; most Web-based databases satisfy this requirement, since they usually present their information to the end-user through a veneer of text. We describe WHIRL, a “soft” database management system which supports “similarity joins,” based on certain robust, general-purpose similarity metrics for text. This enables fragments of text (e.g., informal names of objects) to be used as keys. WHIRL includes textual objects as a built-in type, similarity reasoning as a built-in predicate, and answers every query with a list of answer substitutions that are ranked according to an overall score. Experiments show that WHIRL is much faster than naive inference methods, even for short queries, and efficient on typical queries to real-world databases with tens of thousands of tuples. Inferences made by WHIRL are also surprisingly accurate, equaling the accuracy of hand-coded normalization routines on one benchmark problem, and outerperforming exact matching with a plausible global domain on a second.
Human factors guidelines for terminal interface design
Authors: Morland D. Verne
Published: July 2002

This paper provides a set of guidelines for the design of software interfaces for video terminals. It describes how to optimize screen layouts, interactive data entry, and error handling, as well as many practical techniques for improving man-machine interaction. Emphasis is placed on factors relating to perceptual and cognitive psychology rather than on gross physiological concerns. Ways in which interfaces can be evaluated to improve their user friendliness are also suggested. The author summarizes many ideas that can be found in other, more comprehensive texts on the subject. These guidelines will provide practicing software designers with useful insights into some of today's principal terminal interface design considerations.
Operating system support for database management
Authors: Stonebraker Michael
Published: July 2002

Several operating system services are examined with a view toward their applicability to support of database management functions. These services include buffer pool management; the file system; scheduling, process management, and interprocess communication; and consistency control.
An effective way to represent quadtrees
Authors: Gargantini Irene
Published: July 2002

A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (
i
) encoding a pixel from a 2

n

× 2

>n

array (or screen) into its quaternary code; (
ii
) finding adjacent nodes; (
iii
) determining the color of a node; (
iv
) superposing two images. It is shown that algorithms (
i
)-(
iii
) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.
Effects of chargeout on user/manager attitutes
Authors: Nolan Richard L.
Published: July 2002

The relationship of internal pricing systems for computer services (chargeout systems) and user management attitudes about their computer-based information systems is investigated. Evidence is provided that the relationship conforms to a general pattern that would be expected from the hypothesis of the four stages of EDP growth [15]. The results also indicate that the chargeout systems characteristic of advanced EDP stage environments are associated with relatively high levels of positive user attitudes and marked increases in EDP training for users. Both factors are important to the user/manager involvement necessary for effective control of computer-based systems. Development and maintenance of computer-based systems is asserted to be a category of organizational change. A “felt need” for the change on the part of the user/manager is pre-requisite to any change taking place. The research methods of behavioral science are applied to investigate the user/manager environment and the effects of charge-out.
Value conflicts and social choice in electronic funds transfer system developments
Authors: Kling Rob
Published: July 2002

During the last few years, computer-based systems which automate the transfer and recording of debits and credits have begun to be implemented on a large scale. These systems promise both financial benefits for the institutions that use them and potential conveniences to their customers. However, they also raise significant social, legal, and technical questions that must be resolved if full scale systems for Electronic Funds Transfer (EFT) are not to cause more problems for the larger public than they solve. This paper examines the incentives for EFT developments and the social problems they raise in the context of conflicts between five different value positions that are often implicit in analyses of proposed EFT arrangements. These conflicts reflect the relative importance of certain problems for specific groups. The value positions implicit in EFT proposals help to organize analyses of market arrangements, system reliability, and privacy of transactions. These topics are analyzed in this article and related to the value positions held by concerned parties. Last, the ways in which the public can learn about the social qualities of different EFT arrangements and the pace of EFT developments are both discussed in the context of social choice.
A controlled experiment in program testing and code walkthroughs/inspections
Authors: Myers Glenford J.
Published: July 2002

This paper describes an experiment in program testing, employing 59 highly experienced data processing professionals using seven methods to test a small PL/I program. The results show that the popular code walkthrough/inspection method was as effective as other computer-based methods in finding errors and that the most effective methods (in terms of errors found and cost) employed pairs of subjects who tested the program independently and then pooled their findings. The study also shows that there is a tremendous amount of variability among subjects and that the ability to detect certain types of errors varies from method to method.
Some new upper bounds on the generation of prime numbers
Authors: Mairson Harry G.
Published: July 2002

Given an integer N, what is the computational complexity of finding all the primes less than N? A modified sieve of Eratosthenes using doubly linked lists yields an algorithm of O
A
(N) arithmetic complexity. This upper bound is shown to be equivalent to the theoretical lower bound for sieve methods without preprocessing. Use of preprocessing techniques involving space-time and additive-multiplicative tradeoffs reduces this upper bound to O
A
(N/log logN) and the bit complexity to O
B
(N logN log log logN). A storage requirement is described using O
B
(N logN/log logN) bits as well.
A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces
Authors: Levin Joshua
Published: July 2002

An algorithm for drawing pictures of three-dimensional objects, with surfaces made up of patches of quadric surfaces, is described. The emphasis of this algorithm is on calculating the intersections of quadric surfaces. A parameterization scheme is used. Each quadric surface intersection curve (QSIC) is represented as a set of coefficients and parameter limits. Each value of the parameter represents at most two points, and these may easily be distinguished. This scheme can find the coordinates of points of even quartic (fourth-order) intersection curves, using equations of no more than second order. Methods of parameterization for each type of QSIC are discussed, as well as surface bounding and hidden surface removal.
Glypnir—a programming language for Illiac IV
Authors: Lawrie D. H. , Layman T. , Baer D. , Randal J. M.
Published: July 2002

GLYPNIR is one of the earliest existing languages designed for programming the Illiac IV computer. The syntax of the language is based on ALGOL 60, but has been extended to allow the programmer explicitly to specify the parallelism of his algorithm in terms of 64-word vectors.

This paper describes the characteristics, goals, and philosophy of the language, and discusses some of the problems associated with parallel computer architectures.
On computing certain elements of the inverse of a sparse matrix
Authors: Erisman A. M. , Tinney W. F.
Published: July 2002

A recursive algorithm for computing the inverse of a matrix from the LU factors based on relationships in Takahashi, et al., is examined. The formulas for the algorithm are given; the dependency relationships are derived; the computational costs are developed; and some general comments on application and stability are made.
Mechanical program analysis
Authors: Wegbreit Ben
Published: July 2002

One means of analyzing program performance is by deriving closed-form expressions for their execution behavior. This paper discusses the mechanization of such analysis, and describes a system, Metric, which is able to analyze simple Lisp programs and produce, for example, closed-form expressions for their running time expressed in terms of size of input. This paper presents the reasons for mechanizing program analysis, describes the operation of Metric, explains its implementation, and discusses its limitations.
Political redistricting by computer
Authors: Helbig Robert E. , Orr Patrick K. , Roediger Robert R.
Published: July 2002

The problems of political redistricting are considered and a computer method for redistricting is presented. Criteria for acceptable redistricting are discussed, including population equality, compactness, contiguity, and preservation of natural and/or political boundaries. Only nonpartisan criteria are considered. Using 1970 Bureau of Census population data, specific results are given for the ten Congressional Districts in the state of Missouri and for the seven St. Louis County Council seats. Results from the use of the algorithm indicate the feasibility of political redistricting with the aid of a computer.
On an algorithm for nonlinear minimax approximation
Authors: Watson G. A.
Published: July 2002

Certain nonlinear minimax approximation problems are characterized by properties which permit the application of special algorithms, mainly based on the exchange algorithms of Remes (1934, 1935), for their solution. In this paper the application to problems of this type of a general nonlinear algorithm due to Osborne and Watson (1969) is considered. Examples are given to illustrate that this algorithm can give satisfactory results and, in particular, can successfully solve problems which lead to difficulties with the more conventional specialist method.
Algorithm 448: number of multiply-restricted partitions
Authors: Beyer Terry , Swinehart D. F.
Published: July 2002

Given a positiver integer
m
and an ordered
k
-tuple
c
= (
c
1
, ··· ,

c
k

) of not necessarily distinct positive integers, then any ordered
k
-tuple
s
= (
s
1
, ··· ,

s
k

) of nonnegative integers such that
m
= ∑

k

i
-1

s
i
c
i

is said to be a partition of
m
restricted to
c
. Let

P
c

(
m
) denote the number of distinct partitions of
m
restricted to
c
. The subroutine
COUNT
, when given a
k
-tuple
c
and an integer
n
, computes an array of the values of

P
c

(
m
) for
m
= 1 to
n
. Many combinatorial enumeration problems may be expressed in terms of the numbers

P
c

(
m
). We mention two below.
The AED free storage package
Authors: Ross Douglas T.
Published: July 2002

The most fundamental underlying problem in sophisticated software systems involving elaborate, changing data structure is dynamic storage allocation for flexible problem modeling. The Free Storage Package of the AED-1 Compiler System allows blocks of available storage to be obtained and returned for reuse. The total available space is partitioned into a hierarchy of free storage zones, each of which has its own characteristics. Blocks may be of any size, and special provisions allow efficient handling of selected sizes, control of shattering and garbage collection, and sharing of physical space between zones. The routines of the package perform high level functions automatically, but also allow access and control of fine internal details as well.
Information Retrieval: Recovery of disk contents after system failure
Authors: Lockemann Peter C. , Knutsen W. Dale
Published: July 2002

A method is discussed by which, after a system malfunction, the contents of disk files can be restored to their status at the time of the failure.
Partioning algorithms for finite sets
Authors: Hutchinson George
Published: July 2002

The partitions of a set with
n
elements are represented by certain
n
-tuples of positive integers. Algorithms are described which generate without repetitions the
n
-tuples corresponding to: (1) all partitions of the given set, (2) all partitions of the given set into
m
or fewer sets (1 ≨
m
≨
n
), and (3) all partitions of the given set into exactly
m
sets (1 ≨
m
≨
n
).
Techniques for obtaining high performance in Java programs
Authors: Kazi Iffat H. , Chen Howard H. , Stanley Berdenia , Lilja David J.
Published: July 2002

This survey describes research directions in techniques to improve the performance of programs written in the Java programming language. The standard technique for Java execution is interpretation, which provides for extensive portability of programs. A Java interpreter dynamically executes Java bytecodes, which comprise the instruction set of the Java Virtual Machine (JVM). Execution time performance of Java programs can be improved through compilation, possibly at the expense of portability. Various types of Java compilers have been proposed, including Just-In-Time (JIT) compilers that compile bytecode into native processor instructions on the fly; direct compilers that directly translate the Java source code into the target processor's native language; and bytecode-to-source translators that generate either native code or an intermediate language, such as C, from the bytecodes. Additional techniques, including bytecode optimization, dynamic compilation, and executing Java programs in parallel, attempt to improve Java run-time performance while maintaining Java's portability. Another alternative for executing Java programs is a Java processor that implements the JVM directly in hardware. In this survey, we discuss the basis features, and the advantages and disadvantages, of the various Java execution techniques. We also discuss the various Java benchmarks that are being used by the Java community for performance evaluation of the different techniques. Finally, we conclude with a comparison of the performance of the alternative Java execution techniques based on reported results.
On time and space decomposition of complex structures
Authors: Courtois P. J.
Published: July 2002

Models of large and complex systems can often be reduced to smaller sub-models, for easier analysis, by a process known as decomposition. Certain criteria for successful decompositions can be established.
Parallel changes in large-scale software development
Authors: Perry Dewayne E. , Siy Harvey P. , Votta Lawrence G.
Published: July 2002

An essential characteristic of large-scale software development is parallel development by teams of developers. How this parallel development is structured and supported has a profound effect on both the quality and timeliness of the product. We conduct an observational case study in which we collect and analyze the change and configuration management history of a legacy system to delineate the boundaries of, and to understand the nature of, the problems encountered in parallel development. The results of our studies are (1) that the degree of parallelism is very highhigher than considered by tool builders; (2) there are multiple levels of parallelism, and the data for some important aspects are uniform and consistent for all levels; (3) the tails of the distributions are long, indicating the tail, rather than the mean, must receive serious attention in providing solutions for these problems; and (4) there is a significant correlation between the degree of parallel work on a given component and the number of quality problems it has. Thus, the results of this study are important both for tool builders and for process and project engineers.
Strategic computing at DARPA: overview and assessment
Authors: Stefik Mark
Published: July 2002

Strategic Computing, a 10-year initiative to build faster and more intelligent systems, is ambitious, flawed by overscheduling perhaps and problems of definition, but basically sound.
Optimistic recovery in distributed systems
Authors: Strom Rob , Yemini Shaula
Published: July 2002

Optimistic Recovery
is a new technique supporting application-independent transparent recovery from processor failures in distributed systems. In optimistic recovery communication, computation and checkpointing proceed asynchronously. Synchronization is replaced by
causal dependency tracking
, which enables a posteriori reconstruction of a consistent distributed system state following a failure using
process rollback
and
message replay
.

Because there is no synchronization among computation, communication, and checkpointing, optimistic recovery can tolerate the failure of an arbitrary number of processors and yields better throughput and response time than other general recovery techniques whenever failures are infrequent.
Best “ordering” for floating-point addition
Authors: Robertazzi T. G. , Schwartz S. C.
Published: July 2002

This correspondence examines the influence of the summation order on the numerical accuracy of the resulting sum when the addition is performed using floating-point, finite-precision arithmetic. A simple statistical model is used to find the relative performance of various addition procedures. It is shown that phrasing the question in terms of finding a best ordering is overly restrictive since the most natural and accurate procedures for performing the addition utilize the storage of intermediate sums as well as performing orderings.
Managing risks in enterprise systems implementations
Authors: Scott Judy E. , Vessey Iris
Published: July 2002

What determines if a system implementation will be successful?
Description logics of minimal knowledge and negation as failure
Authors: Donini Francesco M. , Nardi Daniele , Rosati Riccardo
Published: July 2002

We present description logics of minimal knowledge and negation as failure (MKNF-DLs), which augment description logics with modal operators interpreted according to Lifschitz's nonmonotonic logic MKNF. We show the usefulness of MKNF-DLs for a formal characterization of a wide variety of nonmonotonic features that are both commonly available inframe-based systems, and needed in the development of practical knowledge-based applications: defaults, integrity constraints, role, and concept closure. In addition, we provide a correct and terminating calculus for query answering in a very expressive MKNF-DL.
Planar point location using persistent search trees
Authors: Sarnak Neil , Tarjan Robert E.
Published: July 2002

A classical problem in computational geometry is the planar point location problem. This problem calls for preprocessing a polygonal subdivision of the plane defined by n line segments so that, given a sequence of points, the polygon containing each point can be determined quickly on-line. Several ways of solving this problem in O(log n) query time and O(n) space are known, but they are all rather complicated. We propose a simple O(log n)-query-time, O(n)-space solution, using persistent search trees. A persistent search tree differs from an ordinary search tree in that after an insertion or deletion, the old version of the tree can still be accessed. We develop a persistent form of binary search tree that supports insertions and deletions in the present and queries in the past. The time per query or update is O(log m), where m is the total number of updates, and the space needed is O(1) per update. Our planar point location algorithm is an immediate application of this data structure. The structure also provides an alternative to Chazelle's "hive graph" structure, which has a variety of applications in geometric retrieval.
Buffer management in relational database systems
Authors: Sacco Giovanni Maria , Schkolnick Mario
Published: July 2002

The hot-set model, characterizing the buffer requirements of relational queries, is presented. This model allows the system to determine the optimal buffer space to be allocated to a query; it can also be used by the query optimizer to derive efficient execution plans accounting for the available buffer space, and by a query scheduler to prevent thrashing. The hot-set model is compared with the working-set model. A simulation study is presented.
Work at home for computer professionals: current attitudes and future prospects
Authors: Olson Margrethe H.
Published: July 2002

The subject of this paper is work performed in the home with computer and communications technology, also known as
telecommuting
. The article reports on two studies of work at home: a quasi-experimental field study of organizational telecommuting pilot programs, and an attitude survey comparing computer professionals who work at home to employees doing similar jobs in traditional office settings. The results of the field study demonstrated that working in the home had little impact on employee performance; however, supervisors were not comfortable with remote workers and preferred their employees to be on site. In the survey, work in the home was related to lower job satisfaction, lower organizational commitment, and higher role conflict. The survey also included computer professionals who worked at home in addition to the regular work day. The author suggests that performing additional unpaid work in the home after regular work hours may be an important trend that merits further investigation. The studies demonstrate that while computer and communications technology have the potential to relax constraints on information work in terms of space and time, in today's traditional work environments, corporate culture and management style limit acceptance of telecommuting as a substitute for office work.
A multisided generalization of Bézier surfaces
Authors: Loop Charles T. , DeRose Tony D.
Published: July 2002

In this paper we introduce a class of surface patch representations, called S-patches, that unify and generalize triangular and tensor product Bézier surfaces by allowing patches to be defined over any convex polygonal domain; hence, S-patches may have any number of boundary curves. Other properties of S-patches are geometrically meaningful control points, separate control over positions and derivatives along boundary curves, and a geometric construction algorithm based on de Casteljau's algorithm. Of special interest are the regular S-patches, that is, S-patches defined on regular domain polygons. Also presented is an algorithm for smoothly joining together these surfaces with

C
k

continuity.
A generalized Ball curve and its recursive algorithm
Authors: Said H. B.
Published: July 2002

The use of Bernstein polynomials as the basis functions in Bézier's UNISURF is well known. These basis functions possess the shape-preserving properties that are required in designing free form curves and surfaces. These curves and surfaces are computed efficiently using the de Casteljau Algorithm. Ball uses a similar approach in defining cubic curves and bicubic surfaces in his CONSURF program. The basis functions employed are slightly different from the Bernstein polynomials. However, they also possess the same shape-preserving properties. A generalization of these cubic basis functions of Ball, such that higher order curves and surfaces can be defined and a recursive algorithm for generating the generalized curve are presented. The algorithm could be extended to generate a generalized surface in much the same way that the de Casteljau Algorithm could be used to generate a Bézier surface.
Algorithm 682: Talbot's method of the Laplace inversion problems
Authors: Murli A. , Rizzardi M.
Published: July 2002

We describe a FORTRAN implementation, and some related problems, of Talbot's method which numerically solves the inversion problem of almost arbitrary Laplace transforms by means of special contour integration.

The basic idea is to take into account computer precision to derive a special contour where integration will be carried out.
Polynomial-time implication problems for unary inclusion dependencies
Authors: Cosmadakis Stavros S. , Kanellakis Paris C. , Vardi Moshe Y.
Published: July 2002

Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated. As shown by Casanova et al., the unrestricted and finite implication problems are different for the class of functional and unary inclusion dependencies; also, for this class and for any fixed
k
, finite implication has no
k
-ary complete axiomatization. For both of these problems, complete axiomatizations and polynomial-time decision procedures are provided: linear time for unrestricted implication and cubic time for finite implication. It follows that functional and unary inclusion dependencies form a semantically natural class of first-order sentences with equality, which although not finitely controllable, is efficiently solvable and docile. Generalizing from these results, it is shown that the interaction between functional
and inclusion dependencies characterizes: (1) unrestricted implication of unary inclusion and all embedded implicational dependencies; (2) finite implication of unary inclusion and all full implicational dependencies; (3) finite implication of unary inclusion and all embedded tuple-generating dependencies. As a direct consequence of this analysis, most of the applications of dependency implication are extended, within polynomial-time, to database design problems involving unary inclusion dependencies. Such examples are tests for lossless joins and tests for complementarity of projective views. Finally, if one additionally requires that
PLANT PROTEIN PHOSPHATASES
Authors: Smith Robert D. , Walker John C.
Published: July 2002

▪ Abstract  Posttranslational modification of proteins by phosphorylation is a universal mechanism for regulating diverse biological functions. Recognition that many cellular proteins are reversibly phosphorylated in response to external stimuli or intracellular signals has generated an ongoing interest in identifying and characterizing plant protein kinases and protein phosphatases that modulate the phosphorylation status of proteins. This review discusses recent advances in our understanding of the structure, regulation, and function of plant protein phosphatases. Three major classes of enzymes have been reported in plants that are homologues of the mammalian type-1, -2A, and -2C protein serine/threonine phosphatases. Molecular genetic and biochemical studies reveal a role for some of these enzymes in signal transduction, cell cycle progression, and hormonal regulation. Studies also point to the presence of additional phosphatases in plants that are unrelated to these major classes.
DEVELOPMENT OF SYMMETRY IN PLANTS
Authors: Hudson A.
Published: July 2002

▪ Abstract  Plant development involves specification and elaboration of axes of asymmetry. The apical-basal and inside-outside axes arise in embryogenesis, and are probably oriented maternally. They are maintained during growth post-germination and interact to establish novel axes of asymmetry in flowers and lateral organs (such as leaves). Whereas the genetic control of axis elaboration is now partially understood in embryos, floral meristems, and organs, the underlying mechanisms of axis specification remain largely obscure. Less functionally significant aspects of plant asymmetry (e.g. the handedness of spiral phyllotaxy) may originate in random events and therefore have no genetic control.
Far-Ultraviolet Radiation from Elliptical Galaxies
Authors: O'Connell Robert W.
Published: July 2002

▪ Abstract  Far-ultraviolet radiation is a ubiquitous, if unanticipated, phenomenon in elliptical galaxies and early-type spiral bulges. It is the most variable photometric feature associated with old stellar populations. Recent observational and theoretical evidence shows that it is produced mainly by low-mass, small-envelope, helium-burning stars in extreme horizontal branch and subsequent phases of evolution. These are probably descendants of the dominant, metal rich population of the galaxies. Their lifetime UV outputs are remarkably sensitive to their physical properties and hence to the age and the helium and metal abundances of their parents. UV spectra are therefore exceptionally promising diagnostics of old stellar populations, although their calibration requires a much improved understanding of giant branch mass loss, helium enrichment, and atmospheric diffusion.